3完。難しかった。全て未証明AC(未証明だとあとで証明するみたいだから無証明とかのほうがいい)。やや怖いwriterだったが、やってみてまあイメージ通り。ARCらしく普段と違う景色を見せてくれた。問題は面白いけどやってるときは不安なんだよ。
A - Seat Occupation
手札が与えられるので、最後の2人組が来る前に2連続の空きがなくなるようにしてくださいという問題。端から1個おきにやるのが最適に見える。反例が見つかる気がしない。実装もけっこう大変。座る位置を(0-indexedで)1から始めてa_i+1を足していく。はみ出したら、そこまでは座れていて(2人来てても間を空けなければ座れる)、そこから別モードに切り替えて以降2人組が来たらNo。そうでなければ全員座れている。思ったよりだいぶきれいなコードになったが、実装難度は高いと思った。
B - Pass on Path
めちゃくちゃ難しくてある程度考えてから一旦飛ばした。道を一方通行のループにしてみたけどはっきりしない。両端に行って戻ってくるには少なくともL*2の距離を歩くことになる。
難しすぎる。端を鏡だと思って切り開いてみる。長さLの道を3つ並べる(左・真ん中・右とする)。真ん中だけ左右反転している。両端を訪れて出発地点に戻るとは、左の休憩所から右の対応する休憩所まで真っすぐ歩くことだ。同じ方向にあるくと惜しいところで片方しか端に到達できないから2人は違う方向に歩く必要がたぶんあって、そうなるとL*2の距離を歩いたら2回くらいすれ違う。うち1回を出発地点とすればすれ違うのは1回。このくらい仮定しないとやってられん。さて、すれ違う場所を決めると、左右の休憩所の遠いほうまでの距離を歩くのに必要な時間の2倍が答えになりそう。2人で出発地点が違っていてもメリットはなさそう(サンプル1で違うほうがいいこともあると刷り込まれがち)。ということでしゃくとり。どちらで回すか迷ったが、出発地点をforで回して真ん中の休憩所をずらしていった。やや安全側に倒して1個戻してから次に行ったりした。提出してAC。
C - Pivot
2s-aは見覚えのある形。図で考えると、印が両端の2個を含めてN個付いた棒が地面に対して45度の角度であって、それを印の場所で90度バキっと回す(というより上下反転させる)操作だ。まず、最大と最小の差は変わらない。2回操作すると2回の操作の印の位置の差の2倍だけ動く。これを偶数回操作と奇数回操作の2つの世界について考えればいい。色々考えたが、そのときの最大値を選び続けることで安全にいくらでも大きくできると気づいて進展。GCDの取り方もよくわからなかったが、隣との差が全部3の倍数ならその2倍の6の倍数単位でしか動かせないのは明らか。ということで、両端について(最大値の位置で操作すればそこが最小値になるので)初期位置の高さの値を、隣同士の差のGCDをとって2倍した値で割ったあまりを求め、その2つの小さいほうに棒の長さを足したのが答え候補になりそう。最後の2回の操作で負の値を経由してしまう必要が生じるのではないかと不安だったが、ちょっと難しすぎてとりあえず提出してみてから考えようとしたら通った。
(解説を(内容はわからないけど)少し見て)あーそうか、棒の長さの2倍だけ安全に(負の数を経由するリスクなく)下げることができるから、目標値+棒の長さの2*10^100倍の高さちょうどに行ってから戻ってくるだけだ。
D - Halftree
操作後の辺は偶数本になるのでNは奇数である必要がある。また、サンプル3のように巡回する場合は簡単で、つまりNとKの最大公約数が1ならパスグラフを作れる。他は無理そうだな~とか思いながら書いて、これで通るならこんなにペナ祭りになってないよなと気づく。GCDが1でなくても木は作れるのだろう。例えばN=15, K=6で3系統のループができるけど、ここから木を作るにはと考えて何も想像できなくなってしまった。
(追記)解説よくわかんなかったけど自分で適当にやってできそうと思ったら解説も同じっぽかった。解説見てわかんないって言ってる時間が長すぎる。K=gcd(N, K) のケースを解けば対応させることができると思っていたけど、そもそも解説にあるように最初からきれいに並んでいる。当たり前すぎて自分がどこで混乱していたのか思い出せない。奇数*奇数の長方形に並んでいるので、L字と縦棒と横棒を置くだけ。これが木になることがあるの感覚に入ってなかったなあ。世界は広い。紙の厚さ1枚隔てた場所のことも知らない。