09/12(月)

午後1時起床。布団に横たわったまま1時間くらいTLを眺めていた。シャワーを浴びて生協とコンビニへ。予約していたラノベを受け取り、パンやお菓子を買ってきた。帰ってきてしばらく先週の週記を書き進めていた。

午後4時半からインターン先定例会。先週火曜日の1on1までを進捗として報告。週あたりの稼働時間はこれまでと特に変わらないが、今回は求めるものにかなり近い出力が得られているので、ウキウキで発表した。今週は帰省のため全く稼働しない予定。

勉強会はビームサーチの話だった。焼きなましはそれっぽく書いてもまあまあ動くのに対し、ビームサーチはうまく行った試しがない。そもそも自分のマラソンマッチ経験が少ないからというのもあるだろう。今日は基本的なこと、どのような実装上の工夫があるかなどに焦点を絞って聞いていた。

終えてからもずっと日記を書いていた。午後11時半になって一通り文章が出来上がったので投稿、即座にCF #820 div.3に出た。

Dashboard - Codeforces Round #820 (Div. 3) - Codeforces

Aは $a-1$ と $|b-c|+c-1$ を比較。 $b=1$ のときの注意書きを誤読し、最初は場合分けしていた。サンプルで落ちたので改めてしっかり読むと真逆で、特別扱いしなくてよいと書かれていたのでびっくり。Bは後ろから復元すると簡単。Cは先頭から末尾に一気に飛ぶのがコスト最小の経路の一つ。文字コードに関してその間にあるマスを全部踏んでもコストは変わらないから、それを出力する。

Dは $y_i-x_i$ を見て、最大と最小をペアにできるならするのが最適。ペアにできない場合、最小のほうをグループに含めようとするとそこに $y_i-x_i\gt 0$ なる人を二人以上使う必要があるが、それをするくらいならその二人だけでグループを作っても変わらない。つまり最小のものを無視してよい。dequeで実装した。

Eは微妙に二分探索できない制約なので乱択しろと言っている。3頂点の間で計3回聞いてループを作ることにした。パス2本のうちどちらが答えとして返ってくるかは $2^3$ 通りあって、そのうち $5$ 通りではそれぞれ答えが一意に確定するようだ。つまりそれらを候補とし、今度こそ二分探索することで正しい答えが求まりそう。

二分探索にかかるクエリ回数を適当に見積もった結果、9頂点の完全グラフを聞いてそこから $\binom 9 3$ 個のループを取り出し候補を作ることにした。辺がたくさん重複しているので、1ループあたり候補に答えが含まれる確率が先ほど求めた $5/8$ になっているかは不明。信じて投げたらWAが出てしまった。

今度はループに含まれる辺に重複がないようにしてみた。ループの数は13個になってしまうが、これでも失敗する確率がケース当たり $(3/8)^{13}$ で、50ケースあるのだから全体の成功確率は $(1-(3/8)^{13})^{50}\approx 0.9999$ 。この計算でかなりの自信を持ちつつ提出。しかしこれもWAだった。

流石に何かおかしいと思ってコードをチェックすると、クエリを投げる関数の引数がint型になっていた。ここをlong longに修正したら上の二つの方法はどちらも通った。つまらないミスで2ペナと+10分、残念。

Fは $\bmod 9$ が聞かれているので桁和に言い換え。あらかじめ $v(l,r)\bmod 9$ と $k$ のすべての組み合わせを試しておき、クエリに答えた。しかしこの前計算も定数時間で行えているので、素直にその場で求めてもよかったかもしれない。

Gはdp。 $s$ を先頭から見て、 $t$ の出現があったらそれと被るような区間をドットに置き換える。どこを置き換えるかは全探索し、置き換えた先の文字に飛ぶ。最初に $s$ のどこに $t$ が出現するか列挙しておいたら計算量が $O(|s||t|)$ になった。制約は3乗を許すくらい小さいので謎。

全完23位。Eは2頂点を $(a,b)$ と $(b,a)$ の形で聞くのでも良かったらしい。 $1\le a\lt b\le 6$ の範囲で15セット聞くだけでも、それぞれ $1/2$ の確率で失敗するので全体の成功確率は $(1-(1/2)^{15})^{50}\approx 0.9985$ で、通った。クエリ回数は33回程度なので、この確率はまだいくらか上げることができる。

先週の週記の校閲に入り、午前4時完了。しばらくコードゴルフしてから布団に入り、ラノベを1冊読んだ。「D級冒険者の俺、なぜか勇者パーティーに勧誘されたあげく、王女につきまとわれてる」4巻。

この巻はシリアス＋バトル。3巻までの内容をあまり覚えておらず、伏線に言及されてもピンとこなかったり、前の巻で取り扱われたキャラを新キャラだと思い込んでしまったりしたが、メインの1巻からずっと出ているヒロインに関してはいくらか覚えていたのでついていけた。終盤は主人公の無双シーン。日記での言及を読み返す限り、3巻はそういう描写がなくて消化不良気味だったらしい。今回は読めて嬉しい。相変わらずの理不尽な強さは、これからだんだん背景が明らかになっていきそうな予感。

ハーメルンを開いて最近のランキングをチェックし、1作読んだ。「依存症な彼女たち」。まだ2話しか連載されていないが、今のところ非常に面白い。なんとなく淫靡な雰囲気が気に入った。主人公の動じなさも好み。

syosetu.org

午前8時半就寝。

09/13(火)

午後4時起床。1時間くらいスマホを触ってから身を起こした。準備を整えて外出。ゲーセンに向かう。

油そばで腹ごしらえをして、午後6時半から5時間くらい遊んだ。今日はひたすら新曲。それなりの難易度の譜面がいくつも追加されて、それぞれ粘着してAJを捻り出そうとしていた。

Blows Up Everything AJ
最高精度で決まったけど同時押しで出したのが辛い pic.twitter.com/BNka3YwmKF
— こたつがめ (@kotatsugame_t) 2022年9月13日

端に接するように配置されたフリックは、その端の1マスともう一箇所を含むように触れるだけでJC判定が出る。これを利用して手をあまり動かさずにフリックを拾う、いわゆる端フリックと呼ばれるテクニックがあるが、これを嫌ったのかこの譜面ではひたすら内側にフリックがあって大変やりにくかった。

普通の譜面と同じ感覚でやると外側に弾くように手を動かしたくなるのに、それだとアタックが出てしまうので、意識して内側に向ける羽目になり、プレイしていて気持ちよくない。そもそも端フリック判定というのは、多少のアバウトさを許し爽快にプレイさせるためのものであるからして、これを回避されては苦しい。

《偏愛》～ Shattered Memories AJ pic.twitter.com/vrGzeC5Aed
— こたつがめ (@kotatsugame_t) 2022年9月13日

中盤も終盤も難しい。ホールドをある程度無視することで中盤の勝率が上がったと思ったら、無事終盤で癖が付いて大変だった。ちょっと運指を組んで解決。

プレイ真っ最中の午後7時過ぎ、TLでPAST11に関する言及を見たので、さてはと思ってAtCoderを確認したら過去問が公開されていた。出先にいてコードゴルフできない。慌てて最初数問を見たが、そんな一瞬で最適っぽいコードが出そうなものはなかったので、とりあえず安心。

帰宅してから数時間ほどコードゴルフしていた。

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

とりあえずHまでとJを解いた。DFHは特に縮みそうな気配がない。

Aは $X/A+C-X/B$ の符号を見る。符号を見るときはdcでRコマンドを使うのが定番で、このとき適当に掛け算して非ゼロの場合の絶対値が $3$ 以上になっている必要がある。ところがこの式に $B$ を掛けたものがすでにその条件を満たすらしい。すると式自体もかなり書きやすくなって、いい感じに縮んでくれた。

BはRakuのマッチングでExhaustiveオプションを使うのが強い。取り出す区間に重なりがあっても構わず、あり得るすべてのマッチを取り出してくれる。実行時間だけが心配だったが、かなり余裕を持って間に合ったのも嬉しい。

Cは整数と浮動小数点数にあまり区別のない言語だと単にべき乗を計算するだけで十分である。なぜなら10⁹くらいなら精度を落とさず表現できるから。試した中ではPerlで書くのが短い。

Eは $i=\lfloor\sqrt{N-1}\rfloor$ として $|N-i^2-i-1|+1$ が答えとなる。これはすでにdcで隙のないコードが提出されていた。Gは過去の問題を漁って、グラフを連結にするためにはあと何辺必要かという問題を探し、それの最短コードを少し弄って提出した。ただの判定ならもうちょっとなんとかなりそうではある。

C - Connect Cities

JはRaku。普通に日付のRangeでループしようとしたら、最大で300万回弱回すことになって流石に間に合わなかった。日付から、暦の起算日から数えて週末が何回あったか求め、差を取る方針に。daycountメソッドで得られる日数のカウントが1858年11月17日水曜日を0として数えたものであることに注意しつつ、頑張って式を作った。

明日帰省する予定。その前にやっておくこと、クラウドに上げておいたほうが良さそうなデータなどを確認していた。途中TLを見たらProject Eulerを埋めていた人がいて、つられて自分も1問挑戦してみたが、結局解けなかった。

午前6時に布団に入った。1時間ほどハーメルンを読んで寝落ち。

09/14(水)

午後1時起床。昨日に続いてハーメルンを少し読んでいたが、帰省のためにはそう悠長にしている時間はなかった。布団から脱出して準備開始。

仙台にいる間にやっておきたいこととして、月曜日読んだラノベの感想を日記に書くことと、前期の単位の取得状況をツイートすることがあった。それぞれパパっとこなした。以下のツイートの画像には含まれていないが、5月下旬頃に一週間グラフ理論の集中講義を受けていて、これは2単位分。無事AAだった。

単位取得状況 12/14
単位取得率 86%
集中講義を表現できず、困ってしまった pic.twitter.com/d1GGv72djh
— こたつがめ (@kotatsugame_t) 2022年9月14日

いよいよ集中講義一日目である。
週記（2022/05/23-2022/05/29） - kotatsugameの日記

今回の帰省では「虚構推理」シリーズの既刊5冊を一気に持ち帰ることにした。以下に引用したような経緯があって、今がちょうど良い機会だと思う。

pic.twitter.com/1rMWFgclID
— こたつがめ (@kotatsugame_t) 2022年9月14日

漫画を読んでいた。虚構推理の1巻と、転スラの10巻から15巻あたり。前者は小説版を積んでおり、序盤を漫画で確認することで読む意欲を高めようとした。
週記（2022/09/05-2022/09/11） - kotatsugameの日記

午後3時を回ってから出発。仙台駅に向かい、まずみどりの窓口で切符を購入した。9月のド平日なのに大量に人が並んでいて、30分くらいかかった。券売機の方も大混雑で一体何があったのか謎である。

それから一旦ゲーセンに向かって2クレだけプレイした。明日のアップデートで終わってしまうイベント、チュウニズムデュエルがあって、まだ走りきれていなかったのだ。昨日しこたま進めただけあって無事完了。

今日は昨年11月の超大型アップデート以来始めての旧筐体でのプレイで、その60fpsと新筐体の120fpsが思ったより激しく違うことを体感できた。早い話、感覚が全然合わずひたすら下手くそだったのだ。

間に合った〜 pic.twitter.com/BGkAizT8UD
— こたつがめ (@kotatsugame_t) 2022年9月14日

仙台駅に戻って新幹線の時刻を調べたが、ちょうど良い接続のものはつい10分ほど前に出てしまったらしい。そもそも大宮から黒部までは1時間おきにしかなく、今からだと指定席に課金しても見当をつけていたものには間に合わないようだ。到着時刻がその分遅くなってしまうが、まあ仕方ない。

1時間遅い列車に乗るとすると、仙台から大宮までは自由度が2だけあって、仙台でたっぷり待つか仙台と大宮で半分ずつ待つかということになりそう。もう一度ゲーセンに行く元気もないのでとっとと移動を開始することにし、後者を選択した。

新幹線の中ではずっと、昨日寝る前に読み始めたハーメルンを読んでいた。到着ギリギリまでかかって1作読了。「女王の女王」。

syosetu.org

面白かった。男女ペアの主人公はかなり好みの要素である。片方が原作キャラというのは、そもそも原作を読んでいなければ全く気にならない。主人公が常に混ぜっ返すような態度なのは少し気に入らないが、それ以外は堂々たる最強格として君臨しており、良い。原作の展開と合わせるためか序盤はあまり主人公ペアが主導権を握らなかったので、そこで焦らされた分その後の展開がまさに満を持してという感じで爽快だった。

駅から実家までは父の迎えの車。午後10時を過ぎてから帰り着いた。夕食・入浴を済ませ、布団に転がって本を読んでいたら日付が変わるくらいに寝落ちした。

09/15(木)

午前4時前に目を覚まし、また変わらず本を読んだり、ハーメルンを読んだりしていた。両親の起床に合わせて朝食を摂り、布団に戻ってまた午前8時頃に寝た。

午後3時半起床。寝ている間にDMが届いていた。見ると明日発売予定の「競技プログラミングの鉄則」という本に付属する演習問題のジャッジURLだった。正式な発売前に手に入れた方のブログ記事に載っていたらしい。コードゴルフの時間だ！

競技プログラミングの鉄則演習問題集 - AtCoder

とりあえず最初の数問を見ると、すでに自明な最短コードが提出されていた。これは同じようにやっていては一つも取れないぞと思って問題をつらつら眺めていたら、B01も同じくらい自明なことに気づいた。よって問題番号がBから始まるものから埋めていくことにした。

ちょっと複雑な問題、簡単に縮みそうにない問題は容赦なく飛ばしていって、3時間くらいでBとCを一通り確認した。Aのほうは流石にもう目ぼしいものは残っていないだろうと思えたので、とりあえず一息ついて夕食を摂った。

夕食後、両親に「笑わない数学」というテレビ番組をおすすめされたので、録画が残っていた暗号理論の回とABC予想の回を視聴した。

暗号理論の方は手を動かしやすい話題ということもあって面白かった。暗号の歴史や素因数分解の困難性というアイディアを紹介したあと、実際にRSA暗号を計算するところまでやっていてびっくり。

ABC予想の回は微妙。そもそも ${\rm rad}$ の定義を一切説明してくれなかったので以降の話も全部あやふやだった。この回でも頑張って手を動かせる話題を探したらしく、 $a=2^n$ 、 $b=3^n$ としたとき $a+b$ を素因数分解すると $p^1$ または $5^2$ しか現れないことを計算で確かめていて、この事実はなかなか強いことを言っているなあと思ったが、式変形が追えないのは残念だった。

後から ${\rm rad}$ の定義を調べて納得。これは正整数に対し、それの互いに異なる素因数の総積を表す。このもとで、先ほどの $a,b$ を用いてABC予想のステートメント $a+b\lt K(\varepsilon){\rm rad}(ab(a+b))^{1+\varepsilon}$ から上の主張を導こう。ただしこの $a,b$ で $\varepsilon\rightarrow 0$ のとき $K(\varepsilon)\rightarrow 1$ としたのは番組でも画面下に注釈があった。

今 $a+b$ は $2$ と $3$ を素因数に持たないため、 $ab$ とは互いに素。よって ${\rm rad}(ab(a+b))={\rm rad}(ab){\rm rad}(a+b)$ である。 ${\rm rad}(a+b)$ を移項することで $(a+b)/{\rm rad}(a+b)\lt{\rm rad}(ab)={\rm rad}\left(2^n\cdot 3^n\right)=2\cdot 3=6$ 。つまり $a+b=\prod_i p_i^{e_i}$ と素因数分解したとき $\prod_i p_i^{e_i-1}\lt 6$ であり、 $p_i\ne 2,3$ なので、 $e_i-1\gt 0$ なる $i$ が存在すればそれは $(p_i,e_i)=(5,2)$ に限られるということがわかる。

部屋に戻ってまたコードゴルフ。すぐに眠気が来て、布団に転がって2時間ほど寝たあと、今度は午前7時までずっとコードを縮めていた。

途中C++のコードを書こうとしてファイルを開いたら、ABC266-Exを3D BITで解こうとしたときのコードが残っていたので、完成させて提出しておいた。座圧用のインデックスをBITにおける上位のノードに伝播させておらずバグっており、それを直したら無事4sec弱で通った。3Dセグ木は確か手元のランダムケースでも16secかかっていたはず。定数倍の差はそれほどまでにあったらしい。

atcoder.jp

朝食を摂り、少し日記を書いた後外出。地元で済ませる必要のあった用事を二つばかり片付けた。本来は木曜午後に行う予定だったが、思いがけず大量の問題が公開されたので今日に延期してもらったのだった。

正午前に帰宅。昼食を摂ってしばらく本を読み、午後2時前に就寝。

09/16(金)

午後10時を過ぎてから起床。夕食を摂って、TAの書類作成に取り掛かった。今日が期限である。印刷→押印→スキャンの作業に思ったより手間取ったが、なんとか日付が変わるギリギリに完了することができた。仙台にいる間にできれば良かったのだが、そもそもこの書類の提出を求められたのが火曜日で、気づいたときにはもう帰省秒読みに入っていたのだ。

少しコードゴルフしたりハーメルンを読んだりしてから読書に入った。午前4時頃になって本を1冊読了。「虚構推理」。

面白かった。ちょくちょく叙述トリックみたいなものが挟まれてその度にびっくりする。少なくとも序盤のそれの種明かしについては、漫画版だと大ゴマで強調されていたのでわかりやすかったが、小説版だと特に前後に空行があるわけでもなかったので、そういう演出を必要としないのは潔いなと思った。

解決編は100ページばかりを一気読みした。もともとどういうスタイルのミステリかはタイトルやあらすじにあるし、それがこの作品のポイントになっているのだが、実際に虚構の推理を実現されると、真実を知る自分でもそうかと思えるような納得の行く論理展開で、まさに狐につままれたようだった。期待以上。

次の巻である短編集を読み進めつつ、朝まで日記を書いていた。朝食を摂り、また読書に戻る。午前11時半就寝。

09/17(土)

午後2時45分の目覚ましで起床。午後3時からのAHC014に合わせたものである。開始と同時に問題文を読み、提出してまた就寝。

estie Programming Contest 2022（AtCoder Heuristic Contest 014） - AtCoder

今日は外食に行くと聞いていたので午後4時過ぎに起床する予定だったが、実際に起こされてみると午後8時でびっくりした。どうやら僕の睡眠時間が短く細切れだったのでなしになり、僕も目覚ましを掛けなかったのでこうなったらしい。かなり申し訳ない。

最近の自分の感覚ではこのくらいの睡眠時間でも頑張って起きて活動するのは珍しくなかったので、遠慮なく起こしてもらって構わなかったのだが、高校生の頃は非常に寝起きが悪かったのでその頃と同じ対応をされたんだなあと思った。

夕食を摂り、午後9時からABC269に出た。

UNICORN Programming Contest 2022(AtCoder Beginner Contest 269) - AtCoder

Aはdcで書いたら入力に負号が含まれていてWA。AWKで書き直した。そこからは特に工夫なくC++。Bはよい。Cはいつもの $O(3^N)$ bitDPで使うループ。

Dは問題ページを開いた瞬間六角座標が見えてげんなりしたが、隣接マスへの差分が $i$ または $j$ の偶奇によらず決まる形だったのでかなり書きやすかった。AOJ-ICPCなどでは、そうでない面倒な座標の取り方をされた問題ばかりだったように記憶している。

Eは縦横それぞれ二分探索。 $[1,(l+r)/2]$ を聞いたのに $[l,(l+r)/2]$ で判定してしまい1WA。Fは二次元累積和と同様マス $(1,1)$ を左上とするようなクエリ四つに分解し、それぞれ気合いで計算する。最初は書かれている値の偶奇で $0$ に書き換えられるか決まると思っていたので、 $M\bmod 2$ を見る場合分けをしてしまった。

Gは最初全部表向きにした状態から $B_i-A_i$ を何個使うかという問題だと捉えた。この値は $O(\sqrt M)$ 種類しかないので、それぞれ $O(M)$ でdp遷移ができれば嬉しい。実際、 $|B_i-A_i|$ 本のdequeを用意してそれぞれスライド最小値を行うことで、不可能な遷移を削除しつつ計算できることに気づいた。ちょっと割ったり余りを取ったりの操作が重いかなと思いつつ提出したら2973msで冷や汗を垂らした。

Exは2乗の木DPを畳み込みで高速化したら当然のようにTLE。結局解けず、7完25位。

コードゴルフ。AはAWK。最初に提出したのが31Bで、その後Bashからdcを呼び出す方法でも31Bを達成し満足していたが、30分くらい後になって改行を空白にしてもACできることを思い出した。これによりAWKのコードが1B縮んで最短となっている。Bは適当にRaku。[Z]で転置を再現するのは何回か使ったテク。

Cは普通にループすると $N$ から減らしていくことになるので、その値を $N$ から引いて出力することで昇順にした。また無限ループしないように条件を定めようとすると出力が1行足りなくなるのは、判定と同時に出力を行うことで解決。EはRubyのbsearch。他は手つかずである。

日付が変わったあたりからはずっと本を読んでいた。2冊読了。

「虚構推理短編集岩永琴子の出現」。虚構推理シリーズの2巻として位置づけられているが、講談社タイガにおける発売日は最も早いのでちょっと分かりづらい。収録されている短編のうち第二話「うなぎ屋の幸運日」は他とは毛色が違い、岩永琴子以外の推理がメインとなっており印象的だった。

「虚構推理スリーピング・マーダー」。シリーズ3巻となる長編、と言っても短編三つと中編が緩やかに連携する感じだった。この中編は主人公ペアの異質さ悪辣さが前面に押し出されていて非常に楽しく読めた。と言ってもただ職務に忠実なだけだったと説明はあるが。虚構の推理を単純にラストに持ってくるのではなく、そこからもう一捻りあったのには驚かされた。

朝食を摂り、布団に入ってしばらくハーメルンを眺め、午前9時就寝。

09/18(日)

午後4時半に起こされた。今日こそ外食、焼き鳥屋に行く。

開店から数分後には店に着いたものの、その時点で待ちが数組いて、当然今いる客も食事を始めたばかりなのでテーブルに案内されるまで1時間半ほどの待ち時間があった。その間にハーメルンを1作読了。「真の実力はギリギリまで隠しているべきだったかもしれない」。

syosetu.org

全体的にギャグ風味。こういうのはサッと完結するのが一番好みで、これも11話で一応の完結を見た。そこまでは面白かった。しかしその後も連載は続いている。蛇足とは思わないが、相変わらずギャグ展開を多めに混ぜ込むので風呂敷が広がり続け、だんだんよくわからなくなってきた。さらにエタっているのでちょっと印象は悪くなった。

1時間弱食事して帰宅。

食事 pic.twitter.com/wcoqx0mtza
— こたつがめ (@kotatsugame_t) 2022年9月18日

帰ってきて、今日はコンテストが何もないので寝っ転がってハーメルンを読んでいた。また1作読了。「女王様と犬」。

syosetu.org

雪ノ下陽乃の高校時代をメインに据えるにあたって関係者の学年が色々ずらされており、特に城廻めぐりと同級生になるというのはかなり目新しかった。内容も非常に面白い。雪ノ下陽乃の印象は原作のような悪いものではなく、ただ万能なサディストという描かれ方をしていて、ヒロインとして違和感がない。まさかくっつくとは、というのは原作を読んでいるときも違う相手に対して思ったことか。エピローグとして未来の風景が描かれるのも大好物だった。

入浴後はハーメルンをチラチラ読みつつずっと日記を書いていた。完成しないまま午前5時過ぎ就寝。

今週は帰省にお誂え向きでコンテストが全然なかった週だった。特に日曜日が丸々空くというのは何時ぶりだろうか。その時間で参加記を完成させるでもなく、相変わらずハーメルンに費やしてしまったのは残念だが止めようがない。そうやってずっと実家でグダグダしていたこともあり、この週記は12000文字弱と普段に比べ量が控えめになった。