ABC250

6完。ペナ込みで100分超え。今日はずっときんモザ読んでた。その後プロセカのアフターライブ。momokenの配信を見ながら書いている。解けた問題の解説は目を通したが、時間がない(眠い)ので考えてはいない。

A - Adjacent Squares

隣接するマスは基本4個で、端であれば1を引くというのを4通り書く。

B - Enlarged Checker Board

最初はタイル毎と思ったけど、(A*N)*(B*N)のマスと捉えたほうがすっきりしそうなのでそうした。タイルのパリティがわかればいいので、割り算で縦横何番目のタイルか求める。

C - Adjacent Swaps

頑張って0-indexedに直す。ボールに書かれている整数と、整数が書かれているボールの位置の両方を管理する。スワップしていく。左隣を左端と誤読した(さすがにここまで字面が似てて左端のがよく見る形となると仕方ない)。位置の入れ替えが、意外と脳に負荷がかかる。

D - 250-like Number

計算量どこまで落とせるかすぐにはわからないけど、とりあえず3乗から攻めれば10^6まででいいし、しゃくとりできる形になる。しゃくとりは、初めてNGになる位置までインデックスをインクリメント。pとqの大小関係に注意する。

E - Prefix Equality

座標圧縮、できればしたくないけど、必要なのかなあ、みたいな気持ち。クエリをどっちかでソートしても集合の情報量が大きいので計算量がなかなか落ちない。ここで、ハッシュを使うことを思いつく。衝突が不安だったが、実装してみると集合はO(N)個の01で表せるので、コンピュータ将棋のZobrist hashと同様になり衝突しなさそうだなと感じた(こういうとこ詰める余裕のない日だった(競プロってわりとこのくらいの甘えが通っちゃうんだけどできれば避けたいところではある))。座標圧縮して、ABそれぞれについて先頭からi個の集合のハッシュを求める。普通に集合を表す配列を持って前から求めていける。

F - One Fourth

2乗でいいなら簡単だが、共通化できる場所が見つからない。Gを5分くらい考えてから戻ってくると、しゃくとりを思いつく。全くそっち方向の発想なかった。開始地点を順番にN通り試す。1/4以上になるまで伸ばす。面積0を採用してはいけないと思って気を遣っていたが、今考えると半分以下の面積には切れるのだから答えは全体の1/4以下にはなるので問題なかったな。扇形みたいのの面積を持っておいて、そこから三角形を引いて面積を求める。凸なので単調性はありそう。シンプルに書く勇気がなくてゴミみたいなコードに。提出してWAで、答えの最大値を見積もったら意外と大きくlong longの最大値にけっこう近い。そこを直してWAが1個減った(何もわからないので提出回数優先)。もう少し考えると、continueで必要な処理を飛ばしていたので修正してAC。残り3分。