AtCoder Regular Contest 109参加記（～C問題）

300-400-500-0(2)-0-0でノーペナ3完1200点。

A - Hands

この問題の構造は、各階→頂点、廊下・階段→辺として重み付きグラフに落とし込める。このグラフの2頂点間の最短路問題を解けばよい。例えば、ダイクストラ法で実装すれば頂点数 $V=200$ 、辺数 $E=397$ より計算量は $O(E\log V)$ となる。

実際に解いた時はなぜかBFSで実装していたがACできた。この辺よくわかってないのだが、最短路問題はDFSやBFSでも正しく解けるのだろうか？（今日はもう疲れたので明日考える）

B - log

長さが $n$ の丸太は、

長さ $n$ の丸太そのまま
長さ $n+1$ の丸太を切る

のどちらかの方法でしか入手できない。さらに、もし長さ $n+1$ の丸太から長さ $n$ の丸太を切り出せば、長さ $n-1$ の丸太に関して同じ議論が続くこととなる。この時、長さが $1$ の丸太が大量発生してもったいないので、基本的には

長さ $L$ の丸太は、長さ $L$ の丸太を買って手に入れる

ことにする。
ただし、これだと長さ $n+1$ の丸太を有効活用できていない。どの丸太も同じ値段なのだから、はじめに長さ $n+1$ の丸太を買って、短い丸太から順に切り出せるだけ切り出すのが最適である。
ここで、長さ $n+1$ の丸太から何本の丸太を切り出せるか？という小問題が出てくる。これは、 $x$ 本切り出せると仮定して二分探索を行う*1ことで $O(\log n)$ で計算可能。 $1$ から $x$ までの整数の総和は $\frac{x\times (x+1)}{2}$ で求められる。
$n$ 本買う予定だったうちの $x$ 本を買わずに、長さが $n+1$ の丸太 $1$ 本で代用するので、答えは $n-x+1$ である。計算量は、 $O(\log n)$ 。

C - Large RPS Tournament

トーナメントの参加者は最大で $2^{100}$ となるため、愚直にシミュレーションしていては当然間に合わない。ここで、各参加者が出す手は周期的であるため、同じ計算をしている箇所があるはずである。トーナメントの1回戦目を考えると、 $2n$ 人ごとに同じ手を出すペアが同じ順番で登場することがわかる。よって、はじめの $2n$ 人分だけ考えてそれを長さ $n$ の配列に保存すれば一回戦目の結果はすべてわかる。
その次の試合結果も、先ほどの議論を再帰的に適用することで、はじめの $2n$ 人分だけ考えればすべての結果がわかる。