2020/11/28に開催されたコンテストの感想

AtCoder Regular Contest 109

A

100階のビルA,Bがある。AとBの同じ階、Aのn+1階とBのn階の移動はコストxで、同じ建物の上下移動はコストyでできる時、Aのa階-Bのb階の最小コストは

• ダイクストラとかで解けるけど時間かかりそう、O(1)で行けるはず
• a=bのとき、明らかにx
• a>bのとき、Aのb+1階までのコストmin(2x,y)*(a-b-1)+x（AからBに移動しつつ1フロア降りる）
• a<bのとき、Aのb階までのコストmin(2x,y)*(b-a)+x（AからBに同じ階で移動）

B

1~n+1までの丸太で1~nまでの丸太を作るには何本選んで取ればいいか

• nは長さnで作ればいい
• たいていはそう
• n+1を活用したい
• 短い丸太はこれを使う
• n+1で何本作れるかは二分探索で分かる
• 範囲を狭く見積もりすぎた。計算するべきだった

C

2の冪乗人が参加するじゃんけんトーナメント。参加者の手はS[番号%len(S)]で不変。勝者の手は何か

• DPっぽい
• けど遷移多くね（多分大丈夫説ある）
• 周期的
• 周期性で何とかしたい
• 試合を重ねても残っている参加者の手は周期的
• 試合ごとに生きている若い番号の参加者の手の周期の最初の部分だけ覚えておけばいい
• 繰り返せば最終的な勝者の手もわかる

D

三つの点がL字を保ったまま移動するとき何手で目的の場所に届くか

• 実験してみると法則が見えてくる
• が、これを式に落とせなかった
• し、法則も若干間違ってた
• 解く人数もうちょい多そうに思ったけど少なくて助かった
• 座標が多いときは代表的な座標を考えるのね