ABC258

ACDEの4完。Bを飛ばす判断はよかった。Fと心中したのがどうだったか。Bが嫌いすぎてレーティングはどうでもよくなった。

A - When?

0埋めの方法がパッと出てこず、10未満だったら0を(そうでなかったら無を)挿入する実装に。

解説見た。あー、printfでいいじゃん。

B - Number Box

「上下左右および斜めの 8 方向のうちいずれかを初めに選びます」を読んでなかった。えー、Nが小さすぎる。Fをやってるときに、「そういえばサンプル1は9797のが大きいよな」とかちょっと思ってた。

(追記)コードはかなり長くなったが、そんなに難しいところはなかった。

C - Rotation

落ち着いて考えると簡単だとわかる。Sはrotateされるだけだから、元先頭だった文字がどの位置にあるかを管理しておく。

D - Trophy

昔のABCっぽくて好き。ただ、正面から考えると思ったより簡単。各iについてステージiまでクリアしてステージi+1はクリアしないときの最小値を求めていく。1回ずつのクリアで足りないぶんはそこまでの最小のB_iを使う。1回ずつでX回を超えてたらループを抜ける。実装は、思ったよりは大変だった。

E - Packing Potatoes

W視点でi番目から箱詰めを開始したとき何個になるかを求める。これは累積和と二分探索でできる。N個以上入ることがあるのを最初見落としていた(しゃくとりを考えていたが、普通に可能ではあるかもしれないが混乱するのを避けて二分探索に変更)。予め割り算しておいて、N個未満の半端だけを処理する。N個未満なので、累積和の長さはN*2で大丈夫。さて、この問題がつらいのは、更にサイクル検出までしないといけないというところ。N個の場所について何箱目かを記録していき、ループしたらループ開始と終了が何箱目かを保存する。j箱目の位置はiみたいのも保存しておく。クエリに対しては、開始位置がわかればいいので、ループ開始前かどうかで場合分けしてさっき保存した位置を持ってくる。これパート数が多いのに実装やり切れたのえらすぎ。

F - Main Street

大通りに出ない場合は簡単。大通りに出るとき、どこかで曲がって大通りに出るのは、逆へ進むのは明らかに最善じゃないし、そうでないなら初めから曲がらず大通りを目指したほうがいい。よって4通りを考えればいい。スタートとゴールで16通り。大通りに出てからは、「xもyもBの倍数の場所」を通るかで場合分け。通らないなら同じ道にいてまっすぐ大通りを進むだけ。通るなら、最初に通る「xもyもBの倍数の場所」が左右(上下)2通り考えられる。これもスタートとゴールで4通り。64通りを全部調べて最小値を求める。サンプルが合わなくて終了。

(追記)変数をforの内側に書いてて毎回初期化されてた。酷い。しかも、それに気づいてなお、縦横どっちに動いたかのフラグをforの内側に置いたままで、時間を使った。

G - Triangle

(追記)Twitterでbitsetを見てしまったのでそのまま実装。kの位置はどこでもいいとして答えの3倍を求めると楽。愚直もギリギリで通った。-Ofastを付けると倍くらい速くなってびっくり。