ABC115-D Christmasを救いたい - OxOmisosiruのブログ

Christmas　聞け

かの有名な（？）ABC(AtCoder Beginner Contest)115-D Christmas。

全僕を苦しめた問題の一つです。

↓問題リンク

https://atcoder.jp/contests/abc115/tasks/abc115_d

その問題設定は「ダックスフンドのルンルンくんがintに収まらないほどのハンバーガーを食べる」という正気の沙汰ではないものです。

実際実験してみるとレベル1のハンバーガーはたったの5段（本当に「たった」か？）ですが制約上最大であるレベル $50$ はなんと $4503599627370493$ 段ものハンバーガーからなっています。ねずみ算怖すぎ。ありえねえ。

これだけでくそなぞなぞができそうです。

Q.レベル50のハンバーガーは4503599627370493段あるよ。これなーんだ？

A.そんなもの、あったらやばいだろ・・・

はい。

ところで、そんな問題ですが最近ようやくACすることができました。非常に嬉しかったです。

そこで自分なりの考察と解説をここにのこそうと思います。（この記事より優れた解説記事は多くあるので、それらを参考にした方がいいと思います。）

【ぱっと見の方針】

レベル $50$ のハンバーガー、やばいのでハンバーガーの層をしたから全て見ることはまず不可能です。

そこで以下のようなことを考えます。

f:id:OxOmisosiru:20200616200251p:plain

右上のルンルンくん、かわいいですね。

非常に明瞭な絵なので解説は不要でしょう。（は？）

結局何が言いたいかというと、

レベル $N$ バーガーは、レベル $N-1$ バーガーを、

レベル $N-1$ バーガーは、レベル $N-2$ バーガーを、

・・・

レベル $2$ バーガーは、レベル $1$ バーガーを、

含んでいるということです。

よって、$X$ 段目までのパティの数を求めたいのに、位置が特定できない時は、今見ているレベルより下のレベルのバーガーに注目することで位置を絞り込むことができ、最終的には位置が特定でき、何枚パティを食べるかも特定することができる。ということになります。

ここまでくればあとは再帰なりで解くことができますね！ようやく光が見えました！（僕は再帰で解きましたが他の解き方もあるかもしれません。）

さて、本番はここからです。

前提として各レベルのバーガーの層の数、パティの数は事前に計算しているものとします。

f:id:OxOmisosiru:20200616202250p:plain

この絵も非常にわかりやすいですね！（は？）

$(1),(2),(3),(4),(5)$ はそれぞれ下からX層目まで食べるときの、$X$ の値による場合分けを表しています。

それぞれ、以下のような状況です。

(1) $X == 1$
(2) $1 < X <$ (レベルN-1バーガーの層の数)$+2$
(3) $X ==$ (レベルN-1バーガーの層の数)$+2$
(4) (レベルN-1バーガーの層の数)$+2 < X < $(レベルNバーガーの層の数)
(5) $X == $(レベルNバーガーの層の数)

なんとなくわかりやすくなった感がありますね。

この中で一発でパティの数を特定できるものは、$(1)と(3)と(5)$ です。

$(1)$ についてはレベル $0$ バーガーを見ている時ならば $1$ 枚パティを食べることができます。

それ以外では食べることができません。

$(3)$ についてはレベル $N－1$ バーガーに含まれるパティ $+1$ 枚を食べることができます。

$(5)$ についてはレベル $N$ バーガーに含まれるパティ全てを食べることができます。

これは以下の様に実装できます。

//level.at(L)はレベルLバーガーの層の数
//paty.at(L)はレベルLバーガーに含まれるパティの数

if(L == 0){
if(X == 1) ans++;
return ans;
}
else if(1+level.at(L-1) == X){
//真ん中のパティ一枚手前まで=レベルL-1バーガーのパティを全て取れる
ans += paty.at(L-1);
return ans;
}
else if(X == level.at(L-1)+2){
//真ん中のパティまでちょうど取れる
ans += paty.at(L-1)+1;
return ans;
}
else if(X == level.at(L)){
//レベルLバーガーのパティを全て食べられる
ans += paty.at(L);
return ans;
}

さて、$(2)$ と $(4)$ の場合が少し大変です。

$(2)$ の場合から考えてみましょう。

$(2) 1 < X < $(レベルN-1バーガーの層の数)$+2$

という条件を言い換えてみます。

$(2)$ の条件下において $X$ はレベル $N-1$ バーガーの層の数以下に収まります。

今見ているレベル $N$ バーガーの前半部分の層の数は $1+$ (レベルN-1バーガーの層の数)として表せるので、レベルを一つ下げて、さらに、$X$ を $X-1$ として再帰関数を呼べば、レベル $N-1$ バーガーを純粋に考えることができます。

これで $(2)$ の場合は考えることができました。

最後に $(4)$ の場合です。

$(4)$ (レベルN-1バーガーの層の数)$+2 < X < $(レベルNバーガーの層の数)

(2)と同様に考えます。

Xは、今見ているレベル $N$ バーガーの前半部分を完全にカバーしています。よって、前半部分の、(レベル $N-1$ バーガーのパティの個数)+(真ん中の $1$ パティ)は確実に取ることができます。

後半部分の層の数は前半部分と同じく(レベル $N-1$ バーガーの層の数)$+1$ として表せます。よって、レベルを一つ下げて、さらに、$X$ を $X-$ (レベル $N-1$ バーガーの層の数)$-2$として再帰関数を呼べば、後半部分のレベル $N－1$ バーガーを純粋に考えることができます。

あとは実装です。$(2),(4)$ は以下の様に実装できます。