ABC129

開始前36.7(風呂が熱かったせいか?)、Eを通したあと37.1、終了直前36.7。体調悪いから上がりやすかったかも?ただ、コンテスト体験としてはよかった。力も出せたと感じている。始まる前から耳栓をしていたのがいいムーブだった。

A - Airplane

珍しく30秒くらい読み込めなかった。最大のやつを使わない。考察は面白いけど、ループを使えないのがストレス(使ってもいいけど実装は遅くなるだろうし)。maxをmax({p,q,r})の形で書くのを思い出すのが微妙に遅れてもにょった(ちょうど解説にあるようなコードを書きたかった)。

B - Balance

これなー、片方を0個にしちゃいけないという問題で、それをちゃんと書くのに苦労した。でも、今気づいたけど片方を0個にするより1個とN-1個にしたほうがいいから気にしなくてよかったんだ。酷い。最小値をとる初期値も、1<<30にしたけどs(予め計算しておいたΣw)でよかったしほんと酷いな。

C - Typical Stairs

あまりにも典型なDP。あとで、メモリ使用量を減らしたのも書きたい(さすがに、実装スピード優先にしました)。

D - Lamp

解法はすぐわかったけど、4通り書かない実装が思い浮かばず。reverseとswap(s[i][j], s[j][i])で4通りというのも考えて実装しかけたが、照らされるマスの数を格納する配列にもこの操作が必要なのに気づいてやめた(追記:その時点ではやめてなくて、h!=wのケースに気づいてやめたんだった)。結局コピペで4つ。照らすマスの数の0初期化する位置を間違えてて、4回直した。だから嫌だったんだよ。こういう実装はやりたくない。

E - Sum Equals Xor

あとから考えるとこれもすごく典型だな。上の桁から見ていって、10000未満・10100未満・10101未満・10101と考える(最初に1を足すことも考えたけど桁数変わり得るしそこでバグらせてもあれなので見送った)。10000未満の場合だと、aとbのビットが立ってる位置が被ってちゃいけないから、aに立ってるかbに立ってるかどちらにも立ってないかの3通り。2つの条件があるが、逆の順で見たほうが考えやすい。4桁なので3^4通りとなる。10000以上10100未満のときは、上位のビットは確定しているので、そのうち1のものがaに立ってるかbに立ってるかの2通り。2^1*3^2通りとなる。最後に10101の2^3通りを足す。Lに1を足して検算したいなあと思ったけど時間もないし提出。

F - Takahashi's Basics in Education and Learning

一応問題文を「素数」で検索する(Mが素数とは限らないようだ)。Lがクソでかい(L回ループはできない)。桁数は高々18なので桁数が増える回数も高々18回。つまり、桁数が変化しない問題が解ければいい。102105108111みたいなのは111+108000+105000000+102000000000になる。まあ1000倍して引いてやれば(等比数列の和を求めるときみたいに)できそうだよね。頑張って計算するが、Mは素数じゃない。割り算したいのだけど、あまりがそれになるやつが複数あるかも。これに気づいたのが終了15分前で、これは解けないと思った。なんかextgcdみたいにしてできるのかなとか思ったけどそれも無理そうだよなあ。これは力不足。(解説をちょっと読んで)いやあ、なるほどだけど、解説をから目を離して考察が自動で進むわけでもないので、力不足。教育的な問題多いっすね。