週記(2023/05/29-2023/06/04)

05/29(月)

午後4時起床。購買に行こうと思ったが空模様が悪いのでやめた。

ABC303の賞品としてアマギフ3万円分が届いていた。これは日本人2位に対する額であるが、順位表を見る限り自分がその位置にいるとはとても思えない。「また」賞品発送に手違いがあったのではないか、と考えた。

TLを見ているとABC299の賞品が来たという報告がたくさん流れてきた。自分は全体9位なので確実に受け取れるはずだが、しばらく待ってもメールが来ない。順位に比べて少し多い額面のアマギフを受け取った方もいるようだから、メール送信が遅れているというだけではなさそう。

週記(2023/04/24-2023/04/30) - kotatsugameの日記

前回は発送されなかった側だったが今回は逆。前回の対応を思い出せばこの3万円を返せと言われることはないだろう。しかしそのときミスした分の賞品はAtCoder側が補填したはずだから、無邪気に受け取ってしまうのもためらわれる。公式からなにか発表があるまで放置しておくことにした。

午後4時半からインターン先定例会に出席。ドキュメント整備が終わってまた次もドキュメント整備ということで、書くことがない。今日も画像を1枚貼り付けておいた。

勉強会は正規表現の話だった。自分としてはすべて知っている内容だったので、ぼんやり聞きつつ冒頭で紹介されたRegex Golfで遊んでいた。Perl正規表現を親だと思っているので、その記法が使えないと腹を立ててしまう。再帰が必要になるはずの問題があったのにそれをどう書けばいいのかわからなかったので放り出してしまった。

Regex Golf

解散後はずっと週記を書いていた。今週も穴あきだらけのまま午後11時半頃に投稿。コンテストの感想を先に書いていたらラノベハーメルンの感想が書ききれなかった。読んですぐ書かないとなかなか言葉が出てこないから、文章量は少なくても時間がかかる。

今年のTCOがなくなったという話をTLで見た。もともと今年が最後で、さらにオンライン開催であることも予告されていたが、それすら潰れてしまったらしい。ただでさえ質が悪いSRMに出続ける理由はもはや「惰性」しかなくなってしまったように思う。今後一度でも離れたら二度と戻って来られないだろう。

その後週記の穴埋め作業に勤しんでいたが、午前4時くらいからラノベを読み始めた。「一生働きたくない俺が、クラスメイトの大人気アイドルに懐かれたら」4巻を読了。

面白かった。主人公の過去と家庭の問題編が始まり手強そうな敵も出てきてこれは長引きそうだと思っていたら、あっさりこの巻の中で片付いてしまった。しかしこれはこれで辛い展開がなく快適だったし、決着の付き方も気持ちの良いもので読んでいて嬉しかった。主人公が思っていたより何倍も「御曹司」であったという事実は今後どう関わってくるだろうか。自分としてはこういう設定そのものが大好物なので、これからも擦っていってもらえたらと思う。

午前8時就寝。

05/30(火)

午後4時起床。布団から這い出て大学に向かい、購買でラノベを受け取った。張り紙によれば6月から営業時間が午後6時15分までになるらしい。

サークルに出席。今日のバチャは10問目をなんとなく覚えていた。本番中に挑戦したものの全く歯が立たなくて、解説を見て仰天した記憶が強く残っている。細かい部分をその場で再現できて無事AC。

9問目でfor文のインクリメント幅ミスと上限ミスを同時に埋め込んでしまい、奇跡的にサンプルが通るせいで3ペナも出してしまった。サボらずランダムケースを試せば良かった。上限ミスはWwtypoによるもので、こういう変数名は問題文で使われていようとも避けるべきだなと強く感じた。

https://kenkoooo.com/atcoder/#/contest/show/f89d7a0d-0cd7-4d22-b32c-2007a5fea124

午後6時半に解散となり、学食で夕食を摂って帰宅。明日ホスフィンと家飲みする予定なので部屋の掃除をした。何度カーペットにコロコロをかけても意味不明な量の体毛が取れ続けて、ほぼ1ロール使い切ってしまった。

シャワーを浴びてからインターンの作業をした。ちょっとしたリファクタリングとドキュメント整備。今週の1on1は自分の都合で明日に予定されており、今書き換えているコードをそこで使うはずだから、やるならやるでちゃんと完了させなければならない。改修の規模が小さくなるような設計を考え、またテストも入念に行った。このリファクタリングでテストがしやすくなったのは良かった。

また、そうやってコードを弄った記憶が残っているうちにとドキュメント整備も一気呵成に終わらせてしまった。かなり興が乗っていたということもあるだろう。最終的に、なんと5時間近く作業していたようだ。

寝る前にまた先週の週記の穴埋め。今日は読んだラノベの感想を書いた。今週月曜日に読んだものも書いたので合計4冊分、なのに3時間もかかってしまった。

面白くなかった本は雑に書いてもいいやという気分になるので一番書きやすい。特別面白かった本は面白かった部分に言及すればよくて、文章の組み立てで迷うくらい。問題はその中間の本で、これといって書くことがない場合は本当に苦労する。そしてそういう本が一番多いのである。印象はそこそこ良かったのだから雑に書いてしまうのもなんだかなあ、という気持ち。

午前8時前に就寝。

05/31(水)

午後2時起床。ABC303の賞品発送についてAtCoderからメールが届いていた。案の定3万円を返せとは言われなかったから、大手を振って受け取った。

午後3時から1on1。最初1時間くらいは会議参加者を二人増やし、現在扱っているツールの運用まわりの説明が行われた。ここで昨日触っていたコードを動かすタイミングがあった。本番でもちゃんと動いて安心。その後1対1に戻り、ダブルチェックしながら作業していた。ここに結構時間がかかり、次のタスクを決めて解散したのは午後6時だった。

外出してホスフィンと夕食。今日はピザ。狭い店だったが非常に美味しかった。

ドンキに寄って午後9時前に帰宅。いよいよ飲酒……の前に、今日が締め切りだった奨学金の書類を手早く作成して送った。学振の申請書をほぼそのままコピーしたり、インターン申込み時に用意した履歴書を使い回したり。業績リストには競プロの大会をずらずら並べておいた。それしかないから。

火曜日送った奨学金に関しての問い合わせに回答が返ってきていた。自分にも受給資格があるようだ。せっかくだから申し込みたいと考えている。

週記(2023/05/22-2023/05/28) - kotatsugameの日記

今日もボードゲーム。新しく買った「Quarto」と「Blade Rondo -Night Theater-」をプレイした。

「Quarto」は姉からお薦めされたもの。四つの特徴「形」「色」「穴の有無」「高さ」についてそれぞれ2通りの状態、計24個の駒があるので、それを4×4の盤面に並べて同じ状態の駒を一直線に揃えるゲームである。気を抜いているとすぐリーチを見逃してしまうので注意力が必要で手の読み合いはかなり大変だったが、楽しくもあった。適当に打った手が相手を詰ませるものだったと気づいたときは感動した。

「Blade Rondo -Night Theater-」は前回の家飲みのときに買った「Blade Rondo」の続編。相変わらず面白かったがちょっと難しくなったように感じた。物理攻撃も魔法攻撃も、新要素であるドールすらもなんだかパッとしない。わかりやすく強いカードがなくて、どうやってダメージを与えていくか考えるのにかなり苦労した印象。前作と混ぜてプレイしたら二人とも前作のカードをメインに手札を組んでしまった。

「限られたカードプールからカードを選んでデッキを組む」のが楽しいのだと認識している。それならば、ブックオフに行ってデュエマのストレージからカードを掴み取って来てもいいんじゃないかと思った。もちろんBlade Rondoの続編も買い続けるつもりだが、一度はそういうこともやってみたい。

「Blade Rondo」は限られたカードプールから7枚ずつ手札を持って対戦するカードゲーム。一目見てイラストに惚れ込んだ。実際にプレイしても非常に面白かったので、総合してこれまで購入したボドゲの中では一番のお気に入りとなった。同シリーズの後継作品があと四つあるらしい。今すぐにでも全部買ってしまいたいが、家飲みの度に一つ二つ買ってじっくり楽しみたい気持ちもある。

週記(2023/02/06-2023/02/12) - kotatsugameの日記

午前1時半くらいに急激に気持ちが悪くなって、便器でしばらくえずいたあと布団に倒れ込んで寝た。

06/01(木)

午前5時半起床。ホスフィンは自分が倒れてから1時間後に寝たらしい。二人で飲んでいると一人倒れたらすぐやることがなくなってしまうので、申し訳ないなという気持ちがある。

ホスフィンはもう少し寝るらしいので、Blade Rondo -Night Theater-の一人プレイを始めた。前作に比べると効果がちょっと控えめだったり「予備動作」で1ターン猶予があったりしてやりやすく、初めて勝てた。

あとはずっとTLを見て過ごしていた。月が変わっていたので5月の読書記録をツイート。今月は、前半は悪役令嬢、後半はウマ娘とネット小説に熱中していた。

午前8時過ぎにホスフィンが起きて、少し後片付けをした後帰っていった。

二日酔いで微妙に気分が悪く、もう一眠りする気にはなれないがPCの前から動けるわけでもないという状態で、かなり長い時間を過ごした。その間はTLを眺める他に、先生から共有された他の人のセミナー発表原稿を読んでいた。

なんとかシャワーを浴びて購買に向かい、ラノベやお菓子を買ってきた。諸々の準備を整えてまた外出。今日から帰省する。

みどりの窓口で切符を購入した。普段はどの列車でどうやって移動するか前もって決めているが、今日は面倒だったので窓口の人と会話しながら決めてみた。目的の駅を伝えて列車を探してもらうと接続が結構微妙。大宮での待ち時間を少なくした結果、出発まで1時間弱の猶予ができた。

この時間を利用して駅前のロフトでポーチを買った。本を持ち運ぶときはいつもリュックの背中側のポケットに入れているが、こうすると擦れて結構大変なことになりがち。かといって別のところに入れると他の荷物に潰されてしまう。なので一度このポーチに入れて保護しようと思った。実際入れてみるとサイズが微妙に大きくて残念。

まだ時間に余裕があると思って悠々と駅ナカのラーメン屋に入ったが、よく見たらあと20分ちょっとしかない。出てきたものを急いで腹に収めて間に合わせた。

新幹線車内では、大宮まで爆睡、そこから長野まではセミナーの原稿読み、乗り換えて黒部までラノベを読んでいた。

午後9時頃帰宅してすぐ夕食と入浴を済ませ、来るときに読んでいたラノベ「極めて傲慢たる悪役貴族の所業」を読了した。

面白かった。個人的には周りのキャラに振り回されるような描写はないほうが好みかなと思ったが、そうすると単なる主人公最強モノになって書籍化まではされなかったのだろう。この作品はそういうちょっとコミカルなところも人を惹きつける要素になっているはず。それはそれで、やはり面白かった。

別のラノベをしばらく読んで午前1時半就寝。

06/02(金)

午前7時頃に目を覚ましたので朝食を摂った。布団に戻ってしばらくラノベを読み、また午前10時半から午後4時まで二度寝していた。

FFになりすましたアカウントからフォローされた。元のIDの末尾にアンダーバーが追加された以外はアイコンもbioも違いがない。最初は気づかずフォロバしてしまったが、後からTLで問題になっているのに気づいて解除した。

自分は通信量削減のため画像読み込みをOFFにしていて目にするのを免れたが、自傷行為の画像やら動画ばかりを載せて引用ツイートを繰り返していたとのこと。その線で報告もしておいた。

用意されていた昼食を摂り、準備を整えて午後5時からセミナーにオンライン参加した。今日はもともと自分だけオンラインの予定だったが、参加者のうち数名がコロナに感染したため完全オンラインになった。ちなみにこのことが分かったのは日曜日で、そこから数日経っても特に症状が出ていない自分は感染していないものと思って今週は行動していた。実は無症状なだけかもしれないと恐れている。

まず2時間ほど、最近加わった参加者によってDiestel 5.3章の内容が発表された。辺彩色の話。結果も強いし証明も面白いし、さらに扱われた定理の証明に共通する部分を抜き出すなど話の構成がめちゃくちゃ上手い。以上は教科書自体の性質だが、これら重要なポイントを完璧に押さえた上で自前の図も用意された大変良い発表だった。

その後同級生による発表があるはずだったが、欠席していたためそのまま解散になった。体調不良が長引いてしまったのか。先生は特に疑問に思っていない様子だったから連絡はあったのだろう。

夕食を摂り入浴を済ませ、午後9時20分からyukicoder 391に出た。

yukicoder contest 391 - yukicoder

Aは貪欲。Bは上の操作しか考えなくて良さそう。駒の連結成分が大きいほど得だから、常に一番右の駒に対して操作を行い右の駒から順に連結成分に巻き込むことにしたら、通った。具体的な値はA_0=0として\sum A_i-A_{i-1}-1=A_N-Nである。

Cはi\lt jについて区間[B_i,C_i]から選ばれた要素と区間[B_j,C_j]から選ばれた要素の組が答えにどれだけ寄与するか考えた。二つの要素が異なる場合は明らかにN!/2であるから、等しい場合を考える。

b=\max(B_i,B_j)c=\min(C_i,C_j)とすれば、要素の選び方q=(C_i-B_i+1)(C_j-B_j+1)通りのうちp=\max(c-b+1,0)通りで等しくなる。このときどんなpでも転倒数に寄与しないから、求める値は(1-p/q)\times N!/2である。

あらかじめ答えをN(N-1)/2\times N!/2としておきどれだけ減るか求める。上の計算は、[B_i,C_i]に重み1/(C_i-B_i+1)があるとして[B_j,C_j]の重みの和に1/(C_j-B_j+1)を掛けることで再現できるので、座圧して遅延セグ木に乗せることで計算できる。

Dはまず適当に根付き木にする。STパスの中心の点がSTLCAである場合とそうでない場合で数える対象の頂点がどこにあるか分かれるが、いずれにしても部分木を定数個足し引きするだけで表せる。部分木のサイズを前計算しておき、どの部分木を取得するかをLevel Ancestorで求めればよい。

EはMo。問題ごとにdequeを用意すれば、ACを出したタイミングで分割した際のWAの回数の列を管理できて、ここから答えも計算できる。しかし一応定数時間ではあったものの定数倍が悪すぎるようでずっとTLEだった。

あらかじめPが同じ提出をまとめて次のACまでの提出回数を前計算しておくと、その中での区間の両端とACの回数を持つだけで計算ができるようになって高速。1.7secで通った。

Fは#を上手く使うようなことはしなくてよい。h\times wの白マスにおいて左上から右下に行く方法が\binom{h+w-2}{h-1}=(h+w-2)!/(h-1)!/(w-1)!だから、N=h+w-2となるように(h,w)を選びh\times wの右下にN=h-1,w-1のケースを順に繋げることで再帰的に構築できる。やってみると無事制約の範囲内に収まっていた。

Gは非常に面白かった。クエリ2に対する常套手段として頂点を次数の大小で分けるという方法があるが、今回は作用が可換でないため全然上手く行かない。特にクエリ3との両立が難しい。

クエリ3は頂点をdfs順に並べて遅延セグ木に乗せることで上手くいく。それに対してクエリ2は頂点をbfs順に並べるのが良い。この二つを両立させられないか考えてみたところ、見事にできてしまった。

dfsする際にまず子だけ一気に並べてしまって、その後各頂点に降りていく。こうすると子は常に区間になり、部分木は自身を表す1点だけ離れて他が区間になる。

HはこれとHLDを組み合わせればよい。Heavyな辺で結ばれた頂点だけ先に降りて行ってしまうことで、子は1点+区間に、Heavyなパスもほぼ区間になる。ところがこの「ほぼ」というのが厄介で、正確には部分木の話と同様最初の点だけ離れたところに存在するから注意が必要。このせいでWAが取れず、気づく前にコンテストが終了してしまった。

7完10位。直後に上に書いたHのWAの原因に気づきupsolveした。HLDを空で書けたのは偉かった。最近よく使っているし、HLDの構造を利用する話も先週目にしたので、内容に関して理解が深まっている。

コンテスト後はラノベを読んでいた。「俺は星間国家の悪徳領主!」7巻を読了。非常に面白かった。前半ひたすら主人公に辛い展開が続いたが、これまでの6巻を思い出せばこの巻の中で必ず丸く収まるということが期待できる。実際その通りで、しかも期待以上に爽快なシーンが続き読んでいてスカッとした気持ちになった。500ページ近くあって満足感もある。

少し日記を書いて午前4時就寝。

06/03(土)

午後0時半起床。昼食を摂って礼服に着替え、祖母の四十九日の法要に参列した。

まずお寺で読経・焼香・法話法話の話題はいくつかあったはずだが、特に冒頭で言われた「人には肉体的な死の他に、忘れ去られるという意味での死もある」という話が印象的。Dr. ヒルルクの名言は由緒正しいものだったんだなあと思った。また浄土真宗において四十九日とは故人を懐かしみ忘れないようにするための法要であるらしい。

その後代々のお墓に移動して納骨を行った。お墓の内部を見ることはそうそうない。思ったよりたくさん骨壷が並んでおり、古いものなど蓋が割れていて、なんというか壮観だった。納めるときは内部に体を入れるが、礼服が汚れないようシートやジャンパー、帽子を使うという用意周到さを見せた父。下見に来たとき必要になると気づいたらしい。

午後4時頃に帰宅し、私服に着替えて今度は夕食に向かった。道中、PAST14の過去問が公開されているのを知り、Cまでコードゴルフしておいた。

第14回 アルゴリズム実技検定 過去問 - AtCoder

AはどうせN+S+Tの偶奇で分類できる。サンプルを見て合わせた。Bはdcでそのまま足せばよい……かと思いきや、出力する桁数が大きすぎる場合勝手にバックスラッシュ+改行で分割されてしまう仕様でWA。bashからdcを呼び出し、trで不要な文字を削除した。CはPerl

夕食は鮎の店だった。

午後7時に帰宅。入浴して午後8時からUniversal Cup 19回目、Americaセットに出た。今日は自分の法事のため、チームメイトにお願いしてこの時間に参加することにしていた。

2022-2023 ICPC North America Championship - Dashboard - Contest - QOJ.ac

これについて書く前に、まずは午後9時からABC304に出た話。Gと格闘していて結局1時間40分こちらに掛り切りになっていた。ジャッジ詰まりで20分延長された分までは流石に出なかった。

Tokio Marine & Nichido Fire Insurance Programming Contest 2023(AtCoder Beginner Contest 304) - AtCoder

Aはよい。Bは最初3文字以外を0にすればよい。どちらもすぐ短くなるようには見えなかったためC++で書いた。サイトが重くてしばらく提出できず、また問題文もC以降開いていなかったため、少し待ち時間が発生した。

CはBFS。Dはイチゴごとにどのピースに乗っているか求めmapでカウントすると最大値はすぐ求まる。最小値についてはmapのサイズが(A+1)(B+1)より小さい場合0を出力するのに注意。

EはまずGの連結成分を1点に圧縮してから考える。最初に思いついたのがx_iy_iに対してiを記録しておき、pqで同じインデックスが記録されているか調べるという方法だった。記録されているインデックスが少ない方を全部見てチェックすれば速い、というのを先週のCFで見たから、今回もそれだろうと深く考えずに飛びついてしまった。

答えをメモしておけば\{p,q\}が相異なると思うことができて、インデックスをsetで管理したため計算量はO(K\sqrt Q\log K)になる。出したらTLEした。冷静になって\{p,q\}=\{x_i,y_i\}なるiが存在するか判定するだけでよいことに気づいた。

FはMを固定するとどの日に出勤しなければならないか確定するので、それ以外の日の自由度を考えることで周期Mを持つシフトが数え上げられる。問題文にあるように異なるMで同じシフトを生成してしまう可能性があるから、それを約数についての除原理で取り除けば答えになる。

Gは解けなかったので、考えていたことを書いておく。答えを上の桁から二分探索していた。各値について、XORが閾値以上になるようなペアに対して辺を張り、最大マッチングを求めれば良さそう。頂点を倍加して二部マッチングとして解いた。元に戻したとき奇閉路ができるケースが怖いが、ないだろうと信じた。

ペアに辺を張るのは流石に間に合わないので、超頂点を介して張ることにした。これは(k,\lfloor A_i/2^k\rfloor)という組に対し一つ存在すればよい。とりあえず書いて出したら当然のようにTLEした。手元のランダムケースでは22秒ちょっとかかっていた。

ここから辺の張られ方をぐっと睨むと、二分探索で桁を降りていくたびに「辺を追加してマッチング」→「足りたらその辺を削除」ということを繰り返していることに気づいた。削除はできないが追加する前のグラフを保存しておくことはできる。

これによって毎回新しく張る辺がO(N)本になり、マッチングも以前のものが残った状態から追加で計算できるようになった。以上の高速化によって同じランダムケースが手元で8秒ちょっとまで縮んだ。が、当然通るわけもない。

書く

感想戦を終えた後、ABC-Exのupsolveをした。といってもまともに解けたという感触はない。今使えるもののうちRが最小のものを選ぶ貪欲が4ケースWAで、ではその先の頂点のRも含めたうちの最小値を見ることにすればどうかと出してみたら通ってしまった。

解説とは辺を遡る際にRをデクリメントしているか否かという点で異なるため、正当でないかもしれない。特に証明を試みたりはしていない。

しばらく日記を書いた後、午前4時半ごろに布団に入ってハーメルンを読み始めた。午前7時前就寝。

06/04(日)

午後2時過ぎに目を覚ました。それから3時間以上布団でずっとハーメルンを読んでいたが、二度寝するような時間ではなくなってしまったため起きて、用意されていた昼食の一部を食べた。

親に服を新調したいとねだったら、今日これから買いに行くことになった。mont-bellともう一店。午後7時になっても太陽が地平線の上に残っていて、いよいよ夏至が近づいてきたのを感じた。

今着ている服は4年くらい使い続けているはずで、ヘタってきたので買い替えたくなった。じゃあ自分で買えば、と言われていたし確かに仙台にもmont-bellはあるが、この歳になっても自分のお金で服を買うという感覚がいまいちわからない。買い換えなくても我慢できるし、服屋は自分の行動範囲内に一切存在しないから買う機会も生じない。

ちなみに、競プロで配られるTシャツは基本使い物にならないと考えている。普通に店で買うようなものと比べ質が格段に劣るのは当然だし、海外サイズだと半袖の袖がやたら短くて脇毛全開になりがち。

午後9時前に帰宅して夕食。その後横になったら寝てしまったが、午後11時半からコンテストがあることは両親に伝えてあったため、その30分くらい前に起こしてもらえた。急いで入浴してCF #877 div.2。10分こどふぉって45分からの開始になった。

Dashboard - Codeforces Round 877 (Div. 2) - Codeforces

Aは負の数がある場合それが操作で生成されることはないから答えとして適切。ない場合生成された数は操作前の最大値を更新できないから、最大値が答えになる。なかなか難しかった。

Bは長さ1nの順列が避けられない。12の間にnが存在する場合、その二つ以外ありえないから最適であるが、これは必ず達成可能。12をできるだけ離したいというところから思いついた。

Cはちょっと苦労した。mが偶数の場合、左上から右に向かって埋めていくと差が1またはmになってOK。mが奇数の場合は同様に埋めたあと各行を上から0、1、2……マス左にずらすことで差を1,m-1,m+1とできた。

Dはnが偶数であることが必要。括弧を\pm 1にして累積和を取り、これが全部非負になって最後が0で終わるよう調節する。調節するためには((または))が必要だから、その位置を管理しておく。また累積和は区間ADD・区間MIN取得の遅延セグ木で持つ。

まず非負の条件については、最も左にある((のさらに左で負となる場合NOである。そうでない場合は最小値が0以上になるよう(必要であれば)調整し、一旦遅延セグ木を更新しておく。あとから戻す。

次に、最後が0で終わっていない場合は最も右にある))で適切に減らす。その右で区間MINを求め、最後の点よりも小さな値がもし存在すれば、そこはどうしても負になってしまうからNOである。以上のチェックを全て通過すればYES。かなり面倒だったが一発で合って通った。

Eは最初外れ方針を引いてしまったが考え直したら上手く行った。最初の方針は、aの部分列を左から貪欲に構成していったときbi項目で完成するとして、その場合の数\binom{i-1}{n-1}(k-1)^{i-n}k^{m-i}を[tex:n\le i\le mで足し合わせるものだった。Wolfram|Alphaに投げても綺麗な形にならず断念。

aを適当に延長して、十分な長さを持つ列にする。このうち何項目まで作れたかというのを状態に持つdpをFPSで書くと、1回の遷移が(k-1)+xになるため全体ではそのm乗となる。このうちn次以降の係数の和を求めればよい。これは係数の和k^mから0\dots n-1次の係数をそれぞれ引くことで計算できる。

FPSを経由して得た式だが、余事象を考えるとスムーズだったらしい。上で求めたi次の係数\binom{m}{i}(k-1)^{m-i}ai項目までしか作れなかった場合の数と一致する。

Fは理論的には解けたが実装が間に合わない。盤面を1行置きにジグザグに辿って、もしそこから外れたら間の行を通ってすぐ盤面の外に運ばれていくようにする。それで実際に置いてみて、盤面の外に運ばれるなら答えとなるマスの行が高々二つに絞れる。無限ループするならどこでそれが起こるか二分探索。

ジグザグを逆向きにしたり、1行ずらしたりすることで全マスについてチェックできる。端のマスが怖いのでそれらは個別にチェックしておく。端のために2掛ける4クエリ、ジグザグで4クエリ、ジグザグは5000マス程度しか使わないので残り13クエリで二分探索が行える。

40分近くあって端の実装しか終わらなかった。聞くところによるとジグザグを色々試して無限ループを引き起こすだけで良いらしいが……。結果は5完14位。

日記を書いて午前4時くらいに布団に入った。そこからハーメルンをずっと読み続けて気づいたら朝。朝食を摂って午前8時半に就寝した。