05/29(月)
午後4時起床。購買に行こうと思ったが空模様が悪いのでやめた。
ABC303の賞品としてアマギフ3万円分が届いていた。これは日本人2位に対する額であるが、順位表を見る限り自分がその位置にいるとはとても思えない。「また」賞品発送に手違いがあったのではないか、と考えた。
TLを見ているとABC299の賞品が来たという報告がたくさん流れてきた。自分は全体9位なので確実に受け取れるはずだが、しばらく待ってもメールが来ない。順位に比べて少し多い額面のアマギフを受け取った方もいるようだから、メール送信が遅れているというだけではなさそう。
週記(2023/04/24-2023/04/30) - kotatsugameの日記
前回は発送されなかった側だったが今回は逆。前回の対応を思い出せばこの3万円を返せと言われることはないだろう。しかしそのときミスした分の賞品はAtCoder側が補填したはずだから、無邪気に受け取ってしまうのもためらわれる。公式からなにか発表があるまで放置しておくことにした。
午後4時半からインターン先定例会に出席。ドキュメント整備が終わってまた次もドキュメント整備ということで、書くことがない。今日も画像を1枚貼り付けておいた。
勉強会は正規表現の話だった。自分としてはすべて知っている内容だったので、ぼんやり聞きつつ冒頭で紹介されたRegex Golfで遊んでいた。Perlの正規表現を親だと思っているので、その記法が使えないと腹を立ててしまう。再帰が必要になるはずの問題があったのにそれをどう書けばいいのかわからなかったので放り出してしまった。
解散後はずっと週記を書いていた。今週も穴あきだらけのまま午後11時半頃に投稿。コンテストの感想を先に書いていたらラノベやハーメルンの感想が書ききれなかった。読んですぐ書かないとなかなか言葉が出てこないから、文章量は少なくても時間がかかる。
今年のTCOがなくなったという話をTLで見た。もともと今年が最後で、さらにオンライン開催であることも予告されていたが、それすら潰れてしまったらしい。ただでさえ質が悪いSRMに出続ける理由はもはや「惰性」しかなくなってしまったように思う。今後一度でも離れたら二度と戻って来られないだろう。
その後週記の穴埋め作業に勤しんでいたが、午前4時くらいからラノベを読み始めた。「一生働きたくない俺が、クラスメイトの大人気アイドルに懐かれたら」4巻を読了。
面白かった。主人公の過去と家庭の問題編が始まり手強そうな敵も出てきてこれは長引きそうだと思っていたら、あっさりこの巻の中で片付いてしまった。しかしこれはこれで辛い展開がなく快適だったし、決着の付き方も気持ちの良いもので読んでいて嬉しかった。主人公が思っていたより何倍も「御曹司」であったという事実は今後どう関わってくるだろうか。自分としてはこういう設定そのものが大好物なので、これからも擦っていってもらえたらと思う。
午前8時就寝。
05/30(火)
午後4時起床。布団から這い出て大学に向かい、購買でラノベを受け取った。張り紙によれば6月から営業時間が午後6時15分までになるらしい。
サークルに出席。今日のバチャは10問目をなんとなく覚えていた。本番中に挑戦したものの全く歯が立たなくて、解説を見て仰天した記憶が強く残っている。細かい部分をその場で再現できて無事AC。
9問目でfor文のインクリメント幅ミスと上限ミスを同時に埋め込んでしまい、奇跡的にサンプルが通るせいで3ペナも出してしまった。サボらずランダムケースを試せば良かった。上限ミスはW
とw
のtypoによるもので、こういう変数名は問題文で使われていようとも避けるべきだなと強く感じた。
https://kenkoooo.com/atcoder/#/contest/show/f89d7a0d-0cd7-4d22-b32c-2007a5fea124
午後6時半に解散となり、学食で夕食を摂って帰宅。明日ホスフィンと家飲みする予定なので部屋の掃除をした。何度カーペットにコロコロをかけても意味不明な量の体毛が取れ続けて、ほぼ1ロール使い切ってしまった。
シャワーを浴びてからインターンの作業をした。ちょっとしたリファクタリングとドキュメント整備。今週の1on1は自分の都合で明日に予定されており、今書き換えているコードをそこで使うはずだから、やるならやるでちゃんと完了させなければならない。改修の規模が小さくなるような設計を考え、またテストも入念に行った。このリファクタリングでテストがしやすくなったのは良かった。
また、そうやってコードを弄った記憶が残っているうちにとドキュメント整備も一気呵成に終わらせてしまった。かなり興が乗っていたということもあるだろう。最終的に、なんと5時間近く作業していたようだ。
寝る前にまた先週の週記の穴埋め。今日は読んだラノベの感想を書いた。今週月曜日に読んだものも書いたので合計4冊分、なのに3時間もかかってしまった。
面白くなかった本は雑に書いてもいいやという気分になるので一番書きやすい。特別面白かった本は面白かった部分に言及すればよくて、文章の組み立てで迷うくらい。問題はその中間の本で、これといって書くことがない場合は本当に苦労する。そしてそういう本が一番多いのである。印象はそこそこ良かったのだから雑に書いてしまうのもなんだかなあ、という気持ち。
午前8時前に就寝。
05/31(水)
午後2時起床。ABC303の賞品発送についてAtCoderからメールが届いていた。案の定3万円を返せとは言われなかったから、大手を振って受け取った。
高橋様
— こたつがめ (@kotatsugame_t) 2023年5月31日
お世話になっております。AtCoder株式会社 運営事務局です。
AtCoder Beginner Contest 303の賞品発送において賞品獲得対象者となるための参加登録情報がわかりにくいとご指摘がありました。そのため今回に限り参加登録情報に全ての項目を記入しない場合でも賞品獲得対象者となりました。
この操作により高橋様には、2万円多く賞金をお送りしております。
— こたつがめ (@kotatsugame_t) 2023年5月31日
この度は混乱を招いてしまい、申し訳ございませんでした。
弊社の不手際ですので、多くお送りした賞金につきましては、そのままお受け取りいただけますと幸いです。
何卒よろしくお願いいたします。
午後3時から1on1。最初1時間くらいは会議参加者を二人増やし、現在扱っているツールの運用まわりの説明が行われた。ここで昨日触っていたコードを動かすタイミングがあった。本番でもちゃんと動いて安心。その後1対1に戻り、ダブルチェックしながら作業していた。ここに結構時間がかかり、次のタスクを決めて解散したのは午後6時だった。
外出してホスフィンと夕食。今日はピザ。狭い店だったが非常に美味しかった。
— こたつがめ (@kotatsugame_t) 2023年5月31日
— こたつがめ (@kotatsugame_t) 2023年5月31日
ドンキに寄って午後9時前に帰宅。いよいよ飲酒……の前に、今日が締め切りだった奨学金の書類を手早く作成して送った。学振の申請書をほぼそのままコピーしたり、インターン申込み時に用意した履歴書を使い回したり。業績リストには競プロの大会をずらずら並べておいた。それしかないから。
火曜日送った奨学金に関しての問い合わせに回答が返ってきていた。自分にも受給資格があるようだ。せっかくだから申し込みたいと考えている。
週記(2023/05/22-2023/05/28) - kotatsugameの日記
飲酒します pic.twitter.com/ZH1g9BnSvn
— こたつがめ (@kotatsugame_t) 2023年5月31日
今日もボードゲーム。新しく買った「Quarto」と「Blade Rondo -Night Theater-」をプレイした。
— こたつがめ (@kotatsugame_t) 2023年5月31日
「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月の読書記録をツイート。今月は、前半は悪役令嬢、後半はウマ娘とネット小説に熱中していた。
5月の集計
— こたつがめ (@kotatsugame_t) 2023年5月31日
買った:25冊
読んだ:9冊
積読:+16冊
積読(累積):+66冊
午前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は上の操作しか考えなくて良さそう。駒の連結成分が大きいほど得だから、常に一番右の駒に対して操作を行い右の駒から順に連結成分に巻き込むことにしたら、通った。具体的な値はとしてである。
Cはについて区間から選ばれた要素と区間から選ばれた要素の組が答えにどれだけ寄与するか考えた。二つの要素が異なる場合は明らかにであるから、等しい場合を考える。
、とすれば、要素の選び方通りのうち通りで等しくなる。このときどんなでも転倒数に寄与しないから、求める値はである。
あらかじめ答えをとしておきどれだけ減るか求める。上の計算は、に重みがあるとしての重みの和にを掛けることで再現できるので、座圧して遅延セグ木に乗せることで計算できる。
Dはまず適当に根付き木にする。パスの中心の点がとのLCAである場合とそうでない場合で数える対象の頂点がどこにあるか分かれるが、いずれにしても部分木を定数個足し引きするだけで表せる。部分木のサイズを前計算しておき、どの部分木を取得するかをLevel Ancestorで求めればよい。
EはMo。問題ごとにdequeを用意すれば、ACを出したタイミングで分割した際のWAの回数の列を管理できて、ここから答えも計算できる。しかし一応定数時間ではあったものの定数倍が悪すぎるようでずっとTLEだった。
あらかじめが同じ提出をまとめて次のACまでの提出回数を前計算しておくと、その中での区間の両端とACの回数を持つだけで計算ができるようになって高速。1.7secで通った。
Fは#
を上手く使うようなことはしなくてよい。の白マスにおいて左上から右下に行く方法がだから、となるようにを選びの右下にのケースを順に繋げることで再帰的に構築できる。やってみると無事制約の範囲内に収まっていた。
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時半起床。昼食を摂って礼服に着替え、祖母の四十九日の法要に参列した。
— こたつがめ (@kotatsugame_t) 2023年6月3日
まずお寺で読経・焼香・法話。法話の話題はいくつかあったはずだが、特に冒頭で言われた「人には肉体的な死の他に、忘れ去られるという意味での死もある」という話が印象的。Dr. ヒルルクの名言は由緒正しいものだったんだなあと思った。また浄土真宗において四十九日とは故人を懐かしみ忘れないようにするための法要であるらしい。
その後代々のお墓に移動して納骨を行った。お墓の内部を見ることはそうそうない。思ったよりたくさん骨壷が並んでおり、古いものなど蓋が割れていて、なんというか壮観だった。納めるときは内部に体を入れるが、礼服が汚れないようシートやジャンパー、帽子を使うという用意周到さを見せた父。下見に来たとき必要になると気づいたらしい。
午後4時頃に帰宅し、私服に着替えて今度は夕食に向かった。道中、PAST14の過去問が公開されているのを知り、Cまでコードゴルフしておいた。
Aはどうせの偶奇で分類できる。サンプルを見て合わせた。Bはdcでそのまま足せばよい……かと思いきや、出力する桁数が大きすぎる場合勝手にバックスラッシュ+改行で分割されてしまう仕様でWA。bashからdcを呼び出し、trで不要な文字を削除した。CはPerl。
夕食は鮎の店だった。
— こたつがめ (@kotatsugame_t) 2023年6月3日
— こたつがめ (@kotatsugame_t) 2023年6月3日
午後7時に帰宅。入浴して午後8時からUniversal Cup 19回目、Americaセットに出た。今日は自分の法事のため、チームメイトにお願いしてこの時間に参加することにしていた。
2022-2023 ICPC North America Championship - Dashboard - Contest - QOJ.ac
これについて書く前に、まずは午後9時からABC304に出た話。Gと格闘していて結局1時間40分こちらに掛り切りになっていた。ジャッジ詰まりで20分延長された分までは流石に出なかった。
Aはよい。Bは最初3文字以外を0にすればよい。どちらもすぐ短くなるようには見えなかったためC++で書いた。サイトが重くてしばらく提出できず、また問題文もC以降開いていなかったため、少し待ち時間が発生した。
CはBFS。Dはイチゴごとにどのピースに乗っているか求めmapでカウントすると最大値はすぐ求まる。最小値についてはmapのサイズがより小さい場合0を出力するのに注意。
Eはまずの連結成分を1点に圧縮してから考える。最初に思いついたのがとに対してを記録しておき、とで同じインデックスが記録されているか調べるという方法だった。記録されているインデックスが少ない方を全部見てチェックすれば速い、というのを先週のCFで見たから、今回もそれだろうと深く考えずに飛びついてしまった。
答えをメモしておけばが相異なると思うことができて、インデックスをsetで管理したため計算量はになる。出したらTLEした。冷静になってなるが存在するか判定するだけでよいことに気づいた。
Fはを固定するとどの日に出勤しなければならないか確定するので、それ以外の日の自由度を考えることで周期を持つシフトが数え上げられる。問題文にあるように異なるで同じシフトを生成してしまう可能性があるから、それを約数についての除原理で取り除けば答えになる。
Gは解けなかったので、考えていたことを書いておく。答えを上の桁から二分探索していた。各値について、XORが閾値以上になるようなペアに対して辺を張り、最大マッチングを求めれば良さそう。頂点を倍加して二部マッチングとして解いた。元に戻したとき奇閉路ができるケースが怖いが、ないだろうと信じた。
ペアに辺を張るのは流石に間に合わないので、超頂点を介して張ることにした。これはという組に対し一つ存在すればよい。とりあえず書いて出したら当然のようにTLEした。手元のランダムケースでは22秒ちょっとかかっていた。
ここから辺の張られ方をぐっと睨むと、二分探索で桁を降りていくたびに「辺を追加してマッチング」→「足りたらその辺を削除」ということを繰り返していることに気づいた。削除はできないが追加する前のグラフを保存しておくことはできる。
これによって毎回新しく張る辺が本になり、マッチングも以前のものが残った状態から追加で計算できるようになった。以上の高速化によって同じランダムケースが手元で8秒ちょっとまで縮んだ。が、当然通るわけもない。
書く
感想戦を終えた後、ABC-Exのupsolveをした。といってもまともに解けたという感触はない。今使えるもののうちが最小のものを選ぶ貪欲が4ケースWAで、ではその先の頂点のも含めたうちの最小値を見ることにすればどうかと出してみたら通ってしまった。
解説とは辺を遡る際にをデクリメントしているか否かという点で異なるため、正当でないかもしれない。特に証明を試みたりはしていない。
しばらく日記を書いた後、午前4時半ごろに布団に入ってハーメルンを読み始めた。午前7時前就寝。
06/04(日)
午後2時過ぎに目を覚ました。それから3時間以上布団でずっとハーメルンを読んでいたが、二度寝するような時間ではなくなってしまったため起きて、用意されていた昼食の一部を食べた。
親に服を新調したいとねだったら、今日これから買いに行くことになった。mont-bellともう一店。午後7時になっても太陽が地平線の上に残っていて、いよいよ夏至が近づいてきたのを感じた。
遙かなるmont-bell pic.twitter.com/zqm1MHA2kJ
— こたつがめ (@kotatsugame_t) 2023年6月4日
今着ている服は4年くらい使い続けているはずで、ヘタってきたので買い替えたくなった。じゃあ自分で買えば、と言われていたし確かに仙台にもmont-bellはあるが、この歳になっても自分のお金で服を買うという感覚がいまいちわからない。買い換えなくても我慢できるし、服屋は自分の行動範囲内に一切存在しないから買う機会も生じない。
ちなみに、競プロで配られるTシャツは基本使い物にならないと考えている。普通に店で買うようなものと比べ質が格段に劣るのは当然だし、海外サイズだと半袖の袖がやたら短くて脇毛全開になりがち。
午後9時前に帰宅して夕食。その後横になったら寝てしまったが、午後11時半からコンテストがあることは両親に伝えてあったため、その30分くらい前に起こしてもらえた。急いで入浴してCF #877 div.2。10分こどふぉって45分からの開始になった。
Dashboard - Codeforces Round 877 (Div. 2) - Codeforces
Aは負の数がある場合それが操作で生成されることはないから答えとして適切。ない場合生成された数は操作前の最大値を更新できないから、最大値が答えになる。なかなか難しかった。
Bは長さとの順列が避けられない。との間にが存在する場合、その二つ以外ありえないから最適であるが、これは必ず達成可能。とをできるだけ離したいというところから思いついた。
Cはちょっと苦労した。が偶数の場合、左上から右に向かって埋めていくと差がまたはになってOK。が奇数の場合は同様に埋めたあと各行を上から0、1、2……マス左にずらすことで差をとできた。
Dはが偶数であることが必要。括弧をにして累積和を取り、これが全部非負になって最後が0で終わるよう調節する。調節するためには((
または))
が必要だから、その位置を管理しておく。また累積和は区間ADD・区間MIN取得の遅延セグ木で持つ。
まず非負の条件については、最も左にある((
のさらに左で負となる場合NOである。そうでない場合は最小値が0以上になるよう(必要であれば)調整し、一旦遅延セグ木を更新しておく。あとから戻す。
次に、最後が0で終わっていない場合は最も右にある))
で適切に減らす。その右で区間MINを求め、最後の点よりも小さな値がもし存在すれば、そこはどうしても負になってしまうからNOである。以上のチェックを全て通過すればYES。かなり面倒だったが一発で合って通った。
Eは最初外れ方針を引いてしまったが考え直したら上手く行った。最初の方針は、の部分列を左から貪欲に構成していったときの項目で完成するとして、その場合の数で足し合わせるものだった。Wolfram|Alphaに投げても綺麗な形にならず断念。
を適当に延長して、十分な長さを持つ列にする。このうち何項目まで作れたかというのを状態に持つdpをFPSで書くと、1回の遷移がになるため全体ではその乗となる。このうち次以降の係数の和を求めればよい。これは係数の和から次の係数をそれぞれ引くことで計算できる。
FPSを経由して得た式だが、余事象を考えるとスムーズだったらしい。上で求めた次の係数はの項目までしか作れなかった場合の数と一致する。
Fは理論的には解けたが実装が間に合わない。盤面を1行置きにジグザグに辿って、もしそこから外れたら間の行を通ってすぐ盤面の外に運ばれていくようにする。それで実際に置いてみて、盤面の外に運ばれるなら答えとなるマスの行が高々二つに絞れる。無限ループするならどこでそれが起こるか二分探索。
ジグザグを逆向きにしたり、1行ずらしたりすることで全マスについてチェックできる。端のマスが怖いのでそれらは個別にチェックしておく。端のために2掛ける4クエリ、ジグザグで4クエリ、ジグザグは5000マス程度しか使わないので残り13クエリで二分探索が行える。
40分近くあって端の実装しか終わらなかった。聞くところによるとジグザグを色々試して無限ループを引き起こすだけで良いらしいが……。結果は5完14位。
日記を書いて午前4時くらいに布団に入った。そこからハーメルンをずっと読み続けて気づいたら朝。朝食を摂って午前8時半に就寝した。