2019-01-31

CODE THANKS FESTIVAL 2018-G:Sum of cards

詰め切るのが大変。本番で通した人たちすごい。

問題

解法

カード $i$ について， $A_i,B_i$ どちらか一方のスコアを獲得できるという状況だ。こういう状況は，グラフにしてみたくなる。 $1$ から $N$ の数字が頂点，辺を $A_i,B_i$ の間に結んだグラフを考えよう。このグラフは，どの頂点も次数が $2$ であり，円形のグラフの集まりになる。 $A_i,B_i$ のどちらを表にするかということを辺の向きで表現しよう。 $A_i,B_i$ のうち，辺が入る方を表にする，ということにする。するとこの問題は以下のように書ける。

$N$ 頂点の，円形のグラフが集まったグラフがある。各頂点には $1$ から $N$ の数字が書いてある。このグラフの各辺に向きをつけ，各辺について，その辺が入る頂点に書いてある数字だけスコアを得る。少なくとも1本は辺が入ってくる頂点が $K$ 個以上あるという条件のもとで，スコアの最大値を求めよ。

この問題を解いていこう。

円形のグラフが1つのとき

まずは円形のグラフが1つのときを考えよう。これをどう解くかで既に難しく思えるが，なんとここでdpをする(初見厳しくないか...)。どのような状態を持つべきかを考えよう。まず，便宜的に頂点番号を $0,1,n-1$ とする。 $n$ は円形を構成する頂点の数とする。今どの頂点をみているかということは当然必要だろう。また，辺が入ってくる頂点の数に制約があるので，これも状態としてもっておきたい。さらに，この「辺が入ってくる頂点の数」をカウントするために重要な情報がある。それは，頂点 $i-1$ 頂点 $i$ の間の辺の向きである。この頂点の向き次第で，頂点 $i-1$ から頂点 $i$ に移るときに，辺が入ってくる頂点の数が変わってくる。では

$dp[i][j][k]$ :頂点 $i$ までで辺が入る頂点の数が $j$ 個， $k$ は頂点 $i-1$ と頂点 $i$ 間の辺の向きを表す。 $k=0$ のときに頂点 $i$ から頂点 $i-1$ に辺が入る。 $k=1$ のときはその逆とする。

で十分だろうか？とりあえずこの場合の状態遷移について考えてみよう。便宜上， $i=1$ から始め， $i=n-1$ まで見た後， $i=0$ をみることにする。

$k=0$ のとき

$i-1$ で $k=0$ のときは以下の図のようになる。 $i-1$ には辺が入っていなかったが， $i$ から出る辺で入ってくるようになるので， $j$ の添え字が1増える。
f:id:sigma1113:20190130234314p:plain
また， $i-1$ で $k=1$ のときは以下の図のようになる。 $i-1$ にもともと辺が入っていたので， $j$ の添え字は増えない。
f:id:sigma1113:20190130234332p:plain

$k=1$ のとき

同様に考えればよい。
$i-1$ で $k=0$
f:id:sigma1113:20190130234637p:plain
$i-1$ で $k=1$
f:id:sigma1113:20190130234702p:plain

というわけで遷移が書けた。めでたしめでたし...と言いたいのだが，ここには罠がある。そう，いま考えているグラフは円形であったから，頂点 $0$ と頂点 $1$ の間から順に見ていって，最後に頂点 $n-1$ と頂点 $0$ の間を見ることになるが，このときに，上で述べた遷移にはならないパターンがある。以下の2つの図を見比べてみよう。
頂点 $0$ から頂点 $1$ に辺が出ているとき
f:id:sigma1113:20190131000413p:plain
頂点 $1$ から頂点 $0$ に辺が出ているとき
f:id:sigma1113:20190131000423p:plain
$i-1$ から $i$ に辺を伸ばすときは基本的に辺が入る頂点の数は増えるはずであったが，一周して戻ってくるときだけは，そうならないのである。よって，この3次元DPを素直にやるだけではうまくいかないのだ。ではどうするか？答えはシンプルで，「 $0$ から $1$ に辺が出ているか」それとも「 $1$ から $0$ に辺が出ているか」ということを状態としてもてばよい。そうすれば $n-1$ から $0$ の遷移の際にのみ気をつけることで，この問題を回避できる。つまり

$dp[i][j][k][l]$ :頂点 $i$ までで辺が入る頂点の数が $j$ 個， $k$ は頂点 $i-1$ と頂点 $i$ 間の辺の向きを表す。 $k=0$ のときに頂点 $i$ から頂点 $i-1$ に辺が入る。 $k=1$ のときはその逆とする。 $l$ は頂点 $0$ と頂点 $1$ の間の辺の向きを表す。 $l=0$ のときに頂点 $1$ から頂点 $0$ に辺が入る。 $l=1$ のときはその逆とする。

これで円形1つのときの問題を解くことができた。頂点が1つのみのときに注意。

円形のグラフが複数あるとき

さて，この問題でグラフを作ったときに， $N$ 個の頂点すべてが連結になるとは限らない。よって，上のようにして各円について問題を解くことはできるが，その結果をまとめてやる必要がある。しかしこれは難しくない。円が全部で $M$ 個あるとしよう。各円について，辺が入る頂点が $k$ 個あるときのスコアの最大値がわかっている。このとき， $floor(\frac{M+1}{2})\leq k \leq M$ であることに注意しよう。それならば

$dp2[i][j][k]$ : $i$ 個目の円の $j$ 番目のありえる辺が入る頂点の個数まで考えたときに，合計で辺の入る頂点の個数が $k$ のときのスコアの最大値

「 $j$ 番目のありえる辺が入る頂点の個数」というのは， $t=floor(\frac{M+1}{2})$ とすると， $t,t+1,\cdots,M$ に新たに $1,2,\cdots m$ という番号を振りなおしたと考えればよい。遷移はナップサック問題のような形になる。このうち， $k$ が $K$ より大きいものの最大値が答えとなる。

この解法全体の計算量は $O(NK)$ である。

実装

Submission #4129625 - CODE THANKS FESTIVAL 2018
これが参考になるかわからないが，上で述べたことを書くとこんな感じになる。各円の結果をまとめる部分で，前の円の大きさを保存しておかないといけなかったりなど，実装上面倒なことは多い。もう少し楽な実装方針があるかもしれない。

大変だが，勉強になる問題であった。ちなみにうまくやると最大費用流になるらしい。

2019-01-30

CODE THANKS FESTIVAL 2018 F-Coins on the tree

本番は誤読をした...。

問題

F - Coins on the tree

解法

　辞書順最小を作れという指示がある。辞書順最小ということは，前の数字が小さいことが正義である。ならば，先頭から「1にできるか？」を判定し，できるなら確定，できないなら「2にできるか？」ということを判定，というように貪欲に試していこうという方針は自然である。

　それでは，試しに $1$ 番目のコインを頂点 $v$ に置けるかということを判定することを考えよう。まず，コインを頂点 $v$ に置いたのだから，木の根からの距離を $d_v$ (ただし， $d_{根}=1$ とする)とすると，手数を $d_v$ だけ消費する。ここから，残りの $M-1$ 枚を， $K-d_v$ 手でピッタリ置ききる必要がある。このようなことが可能である $v$ の条件がわかればよい。
　まず， $v$ に置くと決めたら， $v$ の子孫たちはもう使えないことに注意しよう。つまり，1番目のコイン以後に使える頂点の数が減るのである。このとき，もし使える頂点の数が $M-1$ を下回るようなことがあれば，1番目のコインを $v$ に置くことはできない。
　使える頂点の数はクリアしたとして，手数の問題を考える。残り手数をピッタリ消費する，という条件は扱いにくいが，このような場合は可能な手数の上限と下限を考えるとうまくいくことがある。まず，手数の上限は，到達可能な頂点のうち， $d_u$ を大きい順に $M-1$ 個取ったときの和である。消費する手数をできるだけ多くするには，できるだけ根から深いところにコインを置くようにすればよいので，このことがわかる。同様に，手数の下限は， $d_u$ を小さい順に $M-1$ 個取ったときの和である。理由は上限と同様である。そして，この上限と下限の間の手数の消費は必ず可能である。手数の下限の状態から，手数の上限の状態までコインを順番に動かすことを考えれば，このことがわかる。以上より， $K-d_v$ がこの上限と下限の間にあれば，コインを頂点 $v$ に置くことが可能となる。
　この判定は高速にできるだろうか。高速といっても，本問では $O(N)$ くらいかけてよい。それならば，到達可能な頂点をすべて訪問し， $d_u$ のリストを作る。リストのサイズが $M-1$ より大きいことを確認した後，これらの大きいほう，そして小さいほうから $M-1$ の和をそれぞれとり， $K-d_v$ と比較すればよい。sortを使っても $O(N\log N)$ でできる。
　1番目のコインを $v$ に置くことが可能だとわかったら， $K$ を $d_v$ だけ減らし，2枚目のコインについても同様にどの頂点に置けるかを番号の小さい順に調べる。このようなことを繰り返せば，辞書順最小のコインの置き方が求まる。もし，あるコインがどの頂点にも置けないということであれば， $-1$ を出力すればよい。

以上をまとめて，次のようにすればこの問題が解ける。

最初に，各頂点 $v$ について $d_v$ を求める。
$i$ 番目のコインを頂点 $v$ に置けるか，ということを $v$ が小さい順に試す。到達可能な頂点を訪問しながら， $d_u$ のリストを作って，判定を行う。置ける条件は，① $d_u$ のリストのサイズが $M-i$ 以上であることかつ ② $d_u$ の小さいほうから $M-i$ 個の和を $sum1$ ，大きいほうから $M-i$ 個の和を $sum2$ とすると， $sum1 \leq K-d_v \leq sum2$ であることの2つ。ただし，この $K$ は $i$ 番目のコインを置こうとしている時点での残り手数を表している。頂点 $v$ に置けるとわかれば， $K$ を $d_v$ だけ減らして，次のコインに進む。置けないなら，次の頂点を試す。どの頂点にも置けないとなれば， $-1$ を出力して終わり。
$M$ 枚目のコインまで置けたら，結果を出力して終わり。

全体の計算量は $O(MN^2\log N)$ である。

実装

Submission #4123308 - CODE THANKS FESTIVAL 2018
dfsが3つあるが，それぞれの役割は以下にようになる。

$dfs(n)$ : $d_n$ を計算する関数。
$dfs2(n,m)$ :判定パートで，到達可能な点を訪問する関数。 $used_n$ というのは，それがtrueのときに頂点 $n$ にはコインを置けないということを表してる。頂点 $n$ を訪問したら判定用のリストに $d_n$ を追加する。 $n$ の子が $m$ または $used_n$ がtrueなら，その子孫はもうコインが置けない頂点なので，その先には訪問しない。
$dfs3(n,m)$ :ある頂点 $v$ にコインを置くと決まった後， $v$ の子孫にはもうコインは置けないということを記録しに行く関数。頂点番号の小さい順から試すということをするため，この作業を怠ってはいけない。

判定パートが若干混乱するが，整理すると綺麗な問題だなあと思う。

2019-01-28

NIKKEI Programing Contest-E:Weights on Vertices and Edges

良問だと思ったので記事にすることにした。Cさえなければ....。

問題

E - Weights on Vertices and Edges

解法

こういう重み付きの辺を追加/削除して連結成分が...という問題は，辺が一本もない状態から，一定の順番で辺を追加していくことを考えることで道が開けることがある。
$N$ 頂点の辺が0本のグラフから，辺の重みが小さい順に辺を追加していくことを考えてみる。このときに，連結成分の重みをもちながら連結していく必要があるが，これはUnion-Findにちょっと書き足せばできる(コード参照)。さて，ある辺 $e$ を追加したときにできた連結成分 $S_e$ が，問題の条件を満たしたとしよう。すると，辺の重みが小さい順に追加していったという仮定から，この連結成分 $S_e$ に属するすべての辺は，問題の条件を満たす。つまり， $S_e$ に含まれる辺は残してもよいことになる。このようにして，辺を追加していきながら，条件を満たす連結成分の集合 $S_{e_1},S_{e_2},\cdots.S_{e_n}$ がわかる。これらの和集合に属する辺たちを残しておけば，条件を満たすグラフが作れる。では，残すべき辺たちはどのようにして調べることができるだろうか。Union-Findしながら，重複をはじきつつ辺の数を数えるのは難しく見える。
ここで， $S_e$ の見方を変えてみる。辺 $e$ の重みを $w_e$ と書くと， $S_e$ は，「 $e$ から重みが $w_e$ の辺のみを使っていくことができる頂点の集合」であることがわかる。つまり， $S_e$ を求めるためには， $e$ が結ぶ頂点から適当にdfsやらbfsやらをするだけでよいことがわかる。本当に求めたいのは $S_{e_1},S_{e_2},\cdots.S_{e_n}$ の和集合で，何も考えずにやると $O(N^2)$ かかってしまうが， $e_1,\cdots,e_n$ のうち， $w_e$ の大きい順に調べていけば， $w_e \leq w_e'$ かつ $S_e \cup S_{e'}\neq \emptyset$ のとき， $S_e \subset S_{e'}$ になるので， $O(N+M)$ で終わる。
以上のことより，次のようなアルゴリズムを考える。

まず，重みの小さい辺から順にグラフに追加していく。もし，この辺 $e$ を追加したことによってできた連結成分が条件を満たすなら， $e$ をリストに追加する。
上の作業が終わったら，リストに追加した辺のうち，重みの大きいものから $S_e$ を求め，残すべき辺の数を数える。
$M-(残すべき辺の数)$ が答え。

最後に，このアルゴリズムが正しい解を返すことを確認しよう。まず，グラフの重みが最大の辺が条件を満たさないなら，その辺は削除されなければならない(1の正当化)。満たす場合，その辺と同じ連結成分に属する他の辺も条件を満たすので，その連結成分については辺を削除する必要がない(2の正当化)。この議論に沿った手続きを再帰的に行っているのが上のアルゴリズムであり，正当性がわかる。(解説の通り帰納法で書いた方がすっきりするかも？)

提出

Submission #4117234 - 全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019

Union-Findのsという配列が，連結成分の重みをもっている。
2に使う辺の管理だが，小さい順にリストに追加して，大きい順に取り出すので，stackを用いるのが楽だと思った。

Cでハマってしまい本番はこの問題を詰め切れず，本選出場も逃したが，観戦権は得ることができた。よろしくお願いします。(誰に対して言ってるんだろう...。)

2019-01-21

ABC116-D:Various Sushi

解法自体は素直なので400点なのだろうが，見た目はとっつきにくいので難しいと思った。

問題

D - Various Sushi

考察・解法

食べることにする寿司の集合を $S$ ， $S$ のネタの種類を $f(S)$ と書くと， $\sum_{i\in S} d_i + f(S)^2$ の最大値を求めることになる。解法はさまざまだが，ここでは $d_i$ の和にまず注目することにする。この部分を最大化するのは簡単で， $d_i$ が大きい $K$ 個を取ればよい。これら $K$ 個の集合を $S_0$ としよう。これが最適解とは限らないというところが難しいのだが，これより良い解があるとしたら，それはネタの種類が $f(S_0)$ より大きい場合に限る。だから， $f(S_0)$ からネタの種類が増えるように $S_0$ の要素の寿司を交換していくことを考えたくなる。さらにこのとき，おいしさの和の項ができるだけ大きくなるようにする(どうしても小さくなるわけだが，それを最小限にする)必要がある。これはどのようにすれば効率的な計算時間で可能だろうか？

まず， $S_0$ を決めるために $(d_i,t_i)$ でソートしておく。これにより $d_i$ が大きい方から $K$ 個とり， $S_0$ と $f(S_0)$ を計算する。さらに，実際に $S_0$ に含まれるネタの種類とそれぞれの種類の寿司の数を記録しておく。ここまでやってスタートである。
ここからネタの種類を増やしていく。まず， $K+1$ 番目に $d_i$ が大きい寿司 $i$ のネタ $t_i$ の種類を見る。同じネタが $S_0$ にあるなら， $S_0$ のどの寿司を入れ替えてもネタの種類は増えないし，おいしさの和は減るだけなので，交換する必要はない。 $t_i$ が $S_0$ にない場合，何かと交換することでネタの種類が増える場合がある。この場合，交換に出すべき $S_0$ の寿司として最適なものは，「 $S_0$ に2つ以上含まれるネタの寿司の中で，もっともおいしさが小さいもの」である。このような寿司を選ぶことで，おいしさの和が小さくなることを最小限に抑えることができる。 $S_0$ に1つしか含まれない寿司を交換に出しても種類が変わらないことに注意しよう。
以上の手続きを繰り返すことで，おいしさの和を最小限に抑えながら，ネタの種類を増やしていくシミュレーションができる。食べる寿司の集合 $S$ が更新されるごとに答えの候補として試し，最大値を出力する。計算時間は $O(N)$ または $O(NlogN)$ でできる。

提出

Submission #4063050 - AtCoder Beginner Contest 116
これを実装してくださいと言われてもまだ大変かもしれない。上のコードでは， $S_0$ を求めたあと， $r=N-K+1$ とおき，これを交換する候補の最初のindexとしている。また，食べる寿司の集合のネタの種類と数はmapで管理した。ここから寿司 $r$ が交換に出す寿司の候補としてふさわしいか判断し，だめなら寿司 $r+1$ を試すということを繰り返している。 $r=N+1$ となったら，もう交換に出せる寿司の種類はないということなので，処理を終了してよい。mapを使っているので計算時間は $O(NlogN)$ となっている。

ABC Only回としては難しい，でもこういう問題好きです。
こどふぉと被っていて，こどふぉはratedなのでそっちに出ていた。
〇〇 Sushi という問題は難しめという謎の習慣...？

2019-01-14

青色になるまでの軌跡

色が変わったら記事を書く人がそこそこいる競プロ界隈ですが，自分もその流れに便乗してみようと思います。ついでに，茶色からの話も少しだけしてみようかと思います。(本編は水色～青の話です。)
最初にこの記事の結論を言ってしまうと，「ちょっとレベルが高めの問題を解こう！」ということに尽きます。レベルを上げるためには自分のレベルより少し上に触れる必要があると思います。

茶色まで

200点までがサクッと解けて，300点もたまに解ければなれるラインだと思っています。こんな言い方ですが，決して簡単なラインではないと思います。200点までをしっかり埋めていきましょう。

緑まで

緑になるためには，計算量という概念についての理解と，それを改善するための具体的な手段をいくつか身につける，思いつけるようになる必要があります(300点で求められるラインです)。愚直にやるとTLEしてしまう解法をうまくやって計算量改善する，という営みの基本的な能力が求められます。300点を解きながらそういうところを意識して学んでいくとよいと思います。
あとは簡単な数学の知識が必要になります。特に整数分野が頻出な印象があります。ここは数学の勉強が必要になると思います。

水色まで

水色に求められるのは以下のようなレベルだと考えています。

300までが早い
400~500がたまに解ける

特に300までに早さに安定感があると，緑帯ならほとんどレートは下がりませんし，AGCなら1完で青パフォが出たりするのでお得です。僕は基本的に遅いのでどうすればいいかわかりません。
400~500あたりですが，知識としては蟻本2章+4章のゲーム・数え上げの節程度で十分だと思います。あとはもう問題を解きながら，経験を積んでいくのがよいと思います(投げやり)。
僕は緑で苦戦していた時期が長く，「競プロは地頭ゲーでは...」という気持ちになり正直苦しかったです。なんとか続けてここまで来れているのはよかったなあと思っています。今でも頭は大切だと思っていますが，勉強量でなんとかなる部分もあると思います。

余談ですが，水色になるまでに必要な知識やテクニックをまとめたpdfでも作ろうかな...とちょっと考えています。蟻本では触れられていない部分や，やや言語化しにくいテクニックをまとめたものってないなあという気持ちがあります。

青になるまで

青に求められるレベル

青に求められるものは以下レベルだと考えています。

400(~500)までが早い
500~600はそこそこ解ける
700~900がたまに解ける

頻度の書き方が雑ですが，気持ちとしてはそれくらいです。ちなみに僕は(グラフの通り)安定感は皆無ですが，AGCで800とか900をたまに通してレートが+100みたいなことをして青になったタイプの人です。もちろん，堅実に500~600あたりを通してレートを上げた回もあります。

パフォーマンスの推移

f:id:sigma1113:20190114130635j:plain

時折爆死していますが()，基本的には順調に伸びているように思ってます。どんどん伸ばすのが難しくなると思っているので，このぺースが維持できるかはわからないですね....。
さて，このグラフを見るとわかる通り，2018年の9月から突然黄色パフォや青パフォがよく出るようになりました。ここら辺であったことを簡単に述べたいと思います。

冒頭に述べた通り，2018年の8~9月頃から，自分のレベルより少し難しい問題を解き始めました。これは400~500が埋まってきたということもあるのですが，結局700あたりが解けるようになるためには，700あたりを知らないとどうしようもないわけです。敵を倒すには敵を知らなければいけません。
さて，当然自分のレベルより高い問題なのでだいたい自力で解けないのですが，積極的に解説ACをしていきました。この「過去問埋めのときに解けなかった問題の解説を見るべきか？」という問題はよく(?)話題になりますが，僕は積極的に見ることを推奨する派閥(?)です。コンテスト中に問題が解けるかどうかが全てだと考えているので，過去問埋めでは基本的に知識や経験を蓄えるべきと考えています。もちろん，解説を見ずに詰めるということも大切な経験ですが，コンテスト時間は高々2時間ですから，僕は2時間くらいで諦めることが多いです。
また，これはこれくらいの得点帯の問題あるあるですが，解説を見たらすぐACできるとかそんな甘いものではありません。解説は往々にして実装レベルに落とすまでの細かい部分が省略されています。また，当然いくつかの知識が仮定されてることが多いです。このような理由で，解説を見て理解して実装するということも十分負荷のある経験であり，実力を伸ばすことに大きく寄与すると考えています。
このような取り組みを始めるまでは，400~500も怪しかったですが，最近は400はほとんど落としませんし，700以上もたまに通せるようになってきました。点数の高い問題は踏むべき考察ステップが多く，1問埋めるだけで多くのことを得ることができます。その結果としてそれより低い問題の正答率にも貢献しているのだと思います。

精進の方法について1つの考え方を述べてみましたが，人それぞれではあるものの，結局自分が難しいと思うレベルの問題もこれから解けるようにならないといけないので，いくつか見ておくということは有用だと考えています。

今年中に「黄色になるまでの軌跡」というタイトルで記事が書けることを祈って本記事を締めくくりたいと思います。引き続き頑張りましょう。

2018-12-29

AGC-030:Tree Burning

解けてよかった。

問題:

B - Tree Burning

考察

まず，高橋君はどういう動きをすべきかを考えよう。直感的に， $0(L)$ を中心として，左右に振れるような動きをしたくなる。つまり

最初は $i$ 本分右に進んで，それ以降は左→右→...と進む。(1)
最初は $i$ 本分左に進んで，それ以降は右→左→...と進む。(2)

これを $i=1...N$ で試したとき，その最大値が答えになる(この部分が非自明ですね，わかり次第(そして余裕ができ次第)追記します)。部分点解法は， $i$ を固定したあと，この動きを愚直にシミュレーションすればよい。
Submission #3894463 - AtCoder Grand Contest 030

では，満点解法を考えよう。要は，部分点解法ではシミュレーションに $O(N)$ かけて答えを求めているが，これが $O(1)$ でできれば満点だ。これはすぐにはわからないので，実験をしてみよう。例えば $N=5$ で， $i=1$ としてみよう。このとき，高橋君の歩いた距離は(実際に手を動かしてください)
$x_1 + \{x_1 + (L-x_5)\} + \{(L-x_5) + x_2\} + \{(x_2 + (L-x_4)\} + \{(L-x_4) + x_3\}\\\ =2x_1 + 2x_2 + x_3 - 2x_4 -2x_5 + 4L$
さて，これを見てなんだかきれいそうな形をしているなあと思えないだろうか。実は，一般的には以下のような結果になる。対称性のため，(1)のパターンだけ述べることにする。

$(i+N)$ が偶数のとき

$m = (i+N)/2$ とする。数列 $\{S_i\}$ を $\{X_i\}$ の第 $i$ 項までの累積和とする。このとき，高橋君の歩いた距離は
$2(S_m-S_{i-1})-X_m - 2(S_N-S_m) + (N-i)L$
である。

$(i+N)$ が奇数のとき

$m = (i+N+1)/2$ とする。このとき，高橋君の歩いた距離は
$2(S_{m-1}-S_{i-1})- 2(S_N-S_{m-1}) + X_m + (N-i)L$
である。

本当にこうなるかどうかに関しては，実際に確認してみることを勧める(万が一違ったら，提出を参考にしてください)。(2)のパターンも同様の式で書ける(提出を参考にしてください)。
これは累積和を事前に計算すれば $O(1)$ でできるので，全体で $O(N)$ で解ける。

提出

Submission #3895747 - AtCoder Grand Contest 030

Garbage Collectorの公式の解説放送では，りんごさんが実際に具体例で計算することでキーとなる式を導いていた。これと同じことを試したら解けたので，具体例での計算は大切だと実感。
青にあと7届かず。

2018-12-08

ABC115-D:Christmas

Pythonで解いた記念。

問題

レベル $L$ バーガーを以下のように定義する。

$L=0$ のとき，パティ1枚。
$L\geq 1$ のとき，パン1枚，レベル $L-1$ バーガー，パティ1枚，レベル $L-1$ バーガー，パン1枚　を下から重ねたもの。

レベル $N$ バーガーの下から $X$ 枚目までに，パティは何枚あるか。
$1\leqq N \leqq 50$

考察

レベル $L$ バーガーが再帰的に定義されていることを使いたい。絵を描いてみるとこんな感じ。
f:id:sigma1113:20181208224144p:plain
これの $X$ 番目が例えばここだとする。
f:id:sigma1113:20181208224158p:plain
これを見れば，「レベル $L$ バーガーの $X$ 番目までのパティの数」は「レベル $L-1$ バーガーの $X-1(=X')$ 番目までのパティの数」だとわかるだろう。同様に，レベル $L-1$ バーガーはこんな感じで， $X'$ 番目がここだとする。
f:id:sigma1113:20181208225003p:plain
これを見れば「レベル $L-1$ バーガーの $X'$ 番目までのパティの数」は
「レベル $L-2$ バーガーの $(X'-2-(レベルL-2バーガーの長さ))$ 番目までにパティの数 $+$ レベル $L-2$ バーガーのパティの数 $+1$ 」
とわかる。こう考えると，再帰的に問題を解いていけばよさそうという気持ちになれる。
　では，具体的に再帰関数を書いていくことを考えよう。まず，レベル $i$ のバーガーの長さを $l_i$ ，レベル $i$ のバーガーにあるパティの数を $p_i$ とすると，これらは次の漸化式を満たす。

$l_i = 2l_{i-1}+3,l_0=1$
$p_i = 2p_{i-1}+1,p_0=1$

これはバーガーの定義からわかるだろう。事前にこれらの値は求めておく。
そして， $dfs(level,dist)$ を次のように定義する。

$level=0$ のとき， $1$
$level\neq0,dist=1$ のとき， $0$
$level\neq0,dist=l_{level}$ のとき， $p_{level}$
$level\neq0,dist=2+l_{level-1}$ のとき， $p_{level-1}+1$ (ちょうど真ん中)
$level\neq0,dist \leqq 1+l_{level-1}$ のとき， $dfs(level-1,dist-1)$
$level\neq0,dist \geqq 3+l_{level-1}$ のとき， $p_{level-1}+dfs(level-1,dist-2-l_{level-1})$