トヨタプログラミングコンテストの本選に出た。競プロで実地イベントに出るのは何の誇張も無しに初めての経験だったのでめいっぱい楽しんできた。

A: 頑張って長方形内の総和を式で表す。長方形の幅・高さはN,Mを超えないので、NM通り全探索してしまえばよい。幅・高さ・和を固定すれば適合する左上の座標を(存在するなら)計算で一意に出せる。適当な左上の座標が存在しないなら無い。この計算は定数時間でできる。

式変形をミスしまくってかなり手間取ってしまった。いつも考察を進めるときはブレスト的にあまり整理せずメモを取っていっているのだが、明確に解法が見えているならちゃんと整理して式変形をミスらないように計算をすすめるべき。

あとはWolframに投げるみたいなのも選択肢に入れるべきだったな。この式を計算すればいいというのが分かっているならWolframに投げるのが手っ取り早い。

B: 順列の構築なので挿入DPとかが一瞬チラついたが、制約から考えて貪欲法なので貪欲法をした。頑張って式計算すれば2か所を入れ替えたときの期待値の変化が分かるので、それを使ってソートすればよい。

C: 割り算とxorというあまり相性の良くなさそうなものの組み合わせなので、全探索に近いやり口を考える。

A^Bを固定して考えると、AもBもA^Bの倍数であることが分かる。A≠BであることからB-A≧A^Bであり、A^B<B-A≦R-LなのでA^BはR-L以下と限定することができる。

A^Bを固定したとき、あり得るAはL以上R未満かつA^Bの倍数なのでO((R-L)/(A^B))個。A^BとAが決まればBは決まるのでそこで残りの条件(BはA^Bの倍数、A<B≦R)を満たすか調べればよい。調和級数なので全体$O((R-L)\log (R-L))$で処理することができる。

D: 解けず。途中までは考察が進んだのだが。

順列f(a,b)の先頭がある数x(0≦x＜N)であるような(a,b)はxに関わらずN個ある。なので求める順列の先頭の数はceil((K-1)/N)として求めることができる。

順列の先頭がその数になるような(a,b)の組N個は全列挙できるのでf(a,b)の辞書式順序でソートできれば良いのだが、定義通りに比較すると最悪$O(N)$かかってしまい、ソートには$O(N^2\log N)$かかる。これでは間に合わない。その後、階差数列の最長共通接頭辞をロリハでにぶたんすれば$O(N(\log N)^2)$に落とせるのではという考えが出たが実装がバグっているのか通らず。厳しい。

最終的な結果は3完で208人中137位。周囲のレベル帯からして0完最下位とかも覚悟していたのだが、思ったよりも健闘出来て本当にうれしかった。

終了後にいろいろトークセッションとかrngからの挑戦状とかがあった。rngからの挑戦状はTwitter情報によれば長寿コンテンツらしいが過去の記録が全く見つからない…すぬけ探しとか無茶苦茶な手計算問題とかで大爆笑した。

AtCoder Problemsの開発話とかも聞けてなかなか良かった。kenkooooさんすごい。開発力と同じくらいに過去の図太いエピソードがすごい。

トヨタの取り組みに関するトークもあって、思っていたよりは面白かった。D-ROOMというのがあって、色々勝手に試せる環境が全国数十か所にあって今も広げているらしい。勝手に何でも出来る実験室的環境は大事。超正統派エンジニアの揺籃になる。

懇親会では本当に知らない人だらけだったが、どうにかして割といろんな人と雑談した。話のネタを出すのは苦手なのだが、ちょっと挨拶して自己紹介すれば結構向こうから話をしてくれる人が居て助かった。

あと競プロフレンズさんの解説をいつも結構頼りにしているので、見かけたため感謝を伝えに行った。3年近くも前に描いたファンアート一枚を未だに覚えてくれていたのでめちゃくちゃに嬉しくなってしまった。