3匹の猫

みみねこの競プロ精進メモ

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人分だけ考えればすべての結果がわかる。

f:id:mmnkblog:20201129002836p:plain
k=4, n=3の例。青字の部分を複製し、赤字の部分だけ保存する

これをk回繰り返したとき、配列の先頭に保存されている手が優勝する手である。

計算量は、O(kn)

D - L

解けなかった。

上記ツイートの数字は、石がそのマスまで移動するのにかかる最小手数を表している。移動したい位置がくの字であることは保証されているので、移動先の3つのマスにそれぞれ移動するまでの最小手数(上記ツイートの数字)を計算し、3つの最小手数の中の最大値に対して

  • 最大値が3つ中1つだけならその最大値を出力
  • 最大値が3つ中2つあるなら最大値+1を出力

というアルゴリズムで実装したが、WAだった。

感想

3完はできたものの、もう少し早くACできればもっと良かったかなと思う。ただペナルティを出さなかったのはえらい。

*1:オーバーフローを避けるために、実装時はx=1から初めて2倍にしていく方法でやった。