週記（2022/05/16-2022/05/22）

05/16(月)

先週は週記を投稿してからすぐ布団に入った。しかしそこからしばらくYouTubeを見てしまって、寝たのは正午だった。

午後4時前に起床。インターン先定例会までの短い時間で、多少なりとも進捗を出しておこうと思って調べ物をしていた。それでも進捗はゴミカス。今週は火曜日にミーティングがあるので、否が応でも何か進むだろう。

他の人の発表を聞きつつ、勉強会スライドの確認と手直しをしていた。文字に色を付けたり。定例会が長引き、普段より遅い時間から勉強会が始まった。使用したスライドは公開してある。

勉強会0516.pdf - Google ドライブ

テーマは関数型言語で、ラムダ計算の導入、そのSKIコンビネータによる表記、またそれを用いたHaskellにおけるポイントフリースタイルへの書き換えを話した。ただでさえ普段より遅く始まった勉強会で長い時間喋り散らかすのは躊躇われるため、スライドの式変形を大胆にカットして雰囲気で進めたつもり。しかし1時間ちょっとはかかっていたようだ。

発表に対して頂いたコメントで、結構置いてけぼりにしてしまったことを知った。当たり前で、ラムダ計算という目新しい表記を導入しているのに、それを使ってバリバリ計算するような内容を急いで喋っていては理解できるものも理解できない。勉強会でこういう「自分はよく知っているが他の人があまり知らない分野」について話すときは入念な戦略が必要である。例えば今回であれば、僕が最も伝えたかったのはポイントフリースタイルへの書き換えであったから、ここを重点的に……いや、それでもラムダ計算の導入は必要なのか。難しいな。

いくつかの部分ではラムダ式をPythonコードにしたものも添付していたので、その辺りは視覚的な面白さもあったのではないかと思っている。コンビネータSとKをそれぞれPythonのラムダ式で書いて、そこからIを作り、実際に適当なラムダ式を書きなおしてみる。すると見た目にはとんでもない文字列になるが、正しく動作する。この見た目に圧倒されてくれれば僕としてはもう満足。ただ理解の助けになったかというと微妙。Pythonのラムダ式で書いたところで、そもそも「関数を返す関数」が理解しにくいので、わかりやすくはならない。

スライドを投稿してからゲーム理論の教科書を読み始めた。今日期限の課題が1個ある。集中を切らしてラノベを読んだりYouTubeを見たりしつつ、何とか期限の30分前に完成して提出できた。お互い7個の戦略を持つ戦略系ゲームの表を書かされる問題があって、手書きで書き始めたことを後悔していた。その後さらに2時間かけてもう一つ課題を倒した。

少しコードゴルフ。ARC140C。最短コードがdcでびっくりしたが、軽く読んだ感じ普通に場合分けしているように見えたので、もっと単純な方針をまともな言語で書いたら短くなると考え、やってみた。ただその単純な方針を考えるのに、他のコードがあまり参考にならずかなり苦労した。

1\dots Nを2つに分割して、適当にreverseした後交互に出力するというもの。前半後半に分割しただけでもほとんどの場合うまくいって、Nが偶数かつX=N/2の場合、またはX=N/2+1の場合のどちらかを特別扱いする必要がある。先に分割してしまうとうまくいかなかったため、分割する前に適宜reverseする方法を思いついた。整理していくと、後ろからN/2だけpopした後に残ったもののreverseとzipするだけで書けてしまい感動。reverseが2か所に出現するのがちょっと気になるが、Vimで書くと2度目の出現をほとんど省略できるのでむしろ短くなるのかも。ということで、そのVimで書いたものが最短になっている。

Submission #31753205 - AtCoder Regular Contest 140

午前4時頃にゴミを出した。この時間でももう外が薄明るくなっていて、夏（正確には夏至）が近づいてくるのを感じる。とはいえド早朝であることに違いはなく、誰もいないだろうと外に出たら、なぜかアパートの前の道路を原付がゆっくり走っていた。できるだけ見ないようにしてごみ集積所まで往復。大変怖い思いをした。

布団に入ってしばらくなろうを読み、午前7時就寝。

05/17(火)

30分おきに設定した目覚ましを何度か無視し、正午にやっとかっとで起床。昨日寝る前にしこたまなろうを読んだのが本当にバカ。まだ身を起こせるほどではなく、しばらくはまたなろうを読んでいた。

30分ほどコーディングした後、午後1時から1時間ミーティング。あれよあれよという間に、僕が書いていたコードが「本番環境に」デプロイされそうな感じになった。実は今までデプロイデプロイ言っていたのは全部ステージング環境の話だったのだ。そう変なコードを書いたつもりはないが、もし僕の作った処理が原因で落ちるなどしたら大変なことである。まあ、祈るしかできない。

そのあと作った処理のドキュメントを書いていた。書きあがって担当の人にお見せするとき、ついでにユースケースに合わせるような仕様の変更案を伝えると、実現すればかなり嬉しいという反応があったので、そこからしばらくはそのためのコーディングをしていた。デプロイ直前にこうやってコードに更新を入れるのは、当たり前ながら一般的に良くない。それに気づかずに更新しますという宣言をして、ひとしきり議論が発生した。この決着について話そうとすると、僕がやっていることをこれまでより詳細に説明する必要が出てくるため、割愛。午後5時くらいに一段落した。

コードゴルフをした。APG4bのEX11。以前までの最短はPerlで普通にevalするものだったが、AWKでコードを組み立てdcに食わせるコードで縮められていた。errorの場合分けもAWKのほうで行うとうまくいくらしい。これを単にVimに書き写してもどうしようもなかったので、もうちょっと本質的な改善を考えたい。実はerrorの場合分けはdcで行うほうが短くなるのではないか？[error]pqのような文字列をスタックに積んでおいて、ゼロ除算とそれ以外でスタックの様子に変化があるのを利用して検出し、実行する。Vimでうまいことコードを組み立てると何とか縮んでくれた。

その後、こちらもAWKで組み立てたほうが2B短くなることに気づく。しかしqでdcを抜けると終了コードが非ゼロになり、REとなってしまう。これを解消するため、+1Bでdcからシェルスクリプトを呼び出すテクを使うことになり、合わせて1Bの短縮となった。

Submission #31763359 - C++入門 AtCoder Programming Guide for beginners (APG4b)

コードゴルフをしていたら学食が閉まってしまった。しばらくなろうを読んでから食事し、いよいよおすすめのネット小説をまとめようと思って、とりあえず今年読んだものを週記からリストアップしていた。はてなブログの下書きの状態で塩漬けにしてある。多分、これ自体も昨年のように形式を整えて年末に投稿することになるだろう。昨年は1年分の週記をチェックするのが大変だったので、こうやって定期的に集めておくと便利そう。

今年読んだネット小説のまとめ - kotatsugameの日記

最新の週記まで確認し終えたところで気が抜け、しばらくなろうを読んでいた。するといつの間にか椅子の上で少し寝入ってしまったので、布団に移動。そこからもしばらくなろうを読み続けて、午前1時半ごろに寝落ちした。

05/18(水)

午前8時頃起床。手癖でYouTubeを開いたら犬山たまきさんが配信を行っていて、何気なく視聴してみたらしぐれういさんがいた。朝から声を聴けていい気持ちになれた。アーカイブはメンバー限定公開になってしまうようなので、一期一会。

しぐれういさんがこの配信の通話から抜けた段階で自分も視聴を止め、もう一度寝ようと考えた。しかしすっかり眠気がどこかに行ってしまったようで、適当にスマホを触っていたらうっかりハーメルンを1作読み始め、読み終えてしまった。「転生したら美少女VTuberになるんだ、という夢を見たんだけど？」。チートガン積みでかなり良かったが、配信風景の描かれ方と同接数やスパチャ額が見合っていないように感じられた。とんでもない数字を叩き出すのだから、本人の言動以外の部分だけでももうちょっと厳かというか、偉大さのある描かれ方をしていてほしかった。

syosetu.org

そのあと、昨日書いたデプロイについて少し確認とやり取りをして、午後1時に再度就寝。午後6時に起床。

先週日曜日に出たCodeChefの4問目の解説が公開されていたらしいので、読んだ。\gcd(a',P-1)=k以降嘘しか書いていないが、方針は分かった。頂いたリプライも参考に、B^k\equiv C^k\pmod P\Rightarrow \exists t\in\mathbb{Z}\;s.t.\;A^t\times B\equiv C\pmod Pの証明を自力で付けてみる。ここでkはA^k\equiv 1\pmod Pを満たす最小の正整数、つまり乗法群における位数である。

PWMUL - Editorial - editorial - CodeChef Discuss

まず原始根gを取ってA\equiv g^a、B\equiv g^b、C\equiv g^cとおき、全体を指数の法M=P-1による合同式で書き換える。0\le t\lt kなる整数tに対してat+b-c\bmod Mの値を見て、0にできればOK。

ここで\bmod{M/k}を考えてみる。まずk=M/\gcd(M,a)よりM/k\mid aとなるから、at\equiv 0\pmod{M/k}。また仮定よりbk\equiv ck\pmod Mであるが、このとき両辺をkで割るとb\equiv c\pmod{M/\gcd(M,k)}が得られる。\gcd(M,k)=kなのでここでも\bmod{M/k}が出現して、まとめるとat+b-c\equiv 0\pmod{M/k}が言えた。つまりat+b-c、ひいてはat+b-c\bmod Mは常にM/kの倍数。

kの定義よりt=0\dots k-1でat\bmod Mは一致しないので、at+b-c\bmod Mも一致しない。今[0,M)にM/kの倍数はk種類しか存在しないため、そのすべてを1度ずつ取ると言える。当然その中には0も存在する。以上より、どこかのtでat+b-c\equiv 0\pmod Mが満たされると分かった。証明終。

少しコードゴルフして、午後8時くらいに外出。もっと早く家を出たかったが思ったより二度寝で爆睡してしまった。ゲーセンに行く。05/02に帰省の途中で大宮のゲーセンに寄って以来なので、二週間以上間が空いたらしい。

今日は新曲を埋めた後14+を適当に触った。新曲から理論値+2、また14+のAJも+2。

ジェネリック緋蜂とは片手で連打しつつもう片手が同時押しだったり交互だったりする配置のことを指している。そこの噛み合い待ちで、ほかの場所、例えばジェネリックAttraqtiAはバッチリだった。

前にプレイしてからしばらく日を置いたらスッと出た。最高精度は以前日記でも触れた6-1-0なので、これでも倍以上の赤を出してしまっている。ただ14+で9950↑は初なので、嬉しい。記憶によれば1000コンボ時点で10個出ていたはず。最高精度を出したときはそこまで理論値だったので、前半の癖が残っていたのだろう。

久しぶりのプレイから2回で出た。こういうリザルトが特に苦労もせず出るようになったという点で自分の成長を感じる。昔は両手それぞれに認識難で片手トリルが降ってくる配置とか、ラストの高速四連打繰り返しに苦しめられていた。

閉店までいたあと油そばを食べて帰宅。実はゲーセンに入る前にも立ち食いそば屋で食事していて、それからあまり時間が空いていなかったので、食べきるのに結構苦労した。

帰宅するとatgolferに更新が複数流れてきていた。Perlに新手が出たらしい。shebangでオプション-aをつけて実行すると、入力が自動的にsplitされて@Fに保存される。splitだけだと自分で書いたほうが短いように見えるが、変数に入れるところまでやってくれるという点が二回以上使う場合に効いてくる。さらにオプション-pで出力を省略することで、実際に最短コードを更新するほど短くなったらしい。自分でもいろいろチェックして少し見つけたほか、それで縮んだものをさらに縮めようとしてしばらく考えていた。午前4時になって切り上げた。

Submission #31788047 - 九州大学プログラミングコンテスト2018

TLでpaiza_runがpaiza_botとして復活したことを知った。出力が画像として返ってくるようになっている。昔僕がQuineを投げて無限ループさせたから……。当時のtogetterを見返しつつ自分の感覚を整理してみると、反省はしているけれど後悔はしていない、というくらいになった。当時の自分にカウントダウンQuineが組めるくらいの力があれば良かったのに。ところで、画像欄で遊んでいたのは普通にマナー違反だった。

なぜ無限ループに対応していなかったのかについては恐らくTwitterのリプライの仕様変更が効いている。もう僕も記憶があいまいだが、リプライ先IDがリプライの文面に含まれないようになったのがこの少し前だったはず。その前は勝手に文章の先頭にIDが書かれた状態になっていたので、Quineしようとしたとしても普通にinvalidなツイートが生成されるように見える。

togetter.com

明日のセミナーの準備を始めた。先週発表しなかった分があるとは言え、きちんと準備できていないし、1週間経って内容も頭から抜けてしまっている。特に、教科書を読んでいるときその場で考えて埋めた行間をちゃんとメモしていなかったので、その再現と、必要であれば改めてメモしておくことを行っていた。

全然終わっていないのだが、朝になってしまったのでいったん眠ることにする。午前5時半くらいに布団に入って、そこからなぜか30分YouTubeを見てから寝た。

www.youtube.com

05/19(木)

昼前に起きて、混む前に学食に行って、一旦帰ってセミナー準備をしようと思っていた。実際は正午になっても起きられず横たわっていた。

午後1時前にスマホに通知が来て、何かと思ったらもうすぐインターン先の会議が始まるとのこと。と言っても僕にとってはただ参加して聞いているだけでOKの、何というか大きな枠組みでの会議。そもそもインターン生が参加することを想定されているのかなど気になることはあるが、いいきっかけなので頑張って身を起こした。

会議を聞きつつ教科書を読み進めていた。全然終わらない。そもそもどれだけ飛ばしても今日1日で発表しきれる分量ではないな、と気づき、後半部分をすっぱり諦めることにした。

準備して午後2時半に出発。途中生協でラノベを受け取りつつ午後3時の直前に教室についてみると誰もいなかった。買ってきたパンを食べつつ先生にメールを送ってみるも、返事がない。

もう一人の同級生にLINEを送ってみると、その人が今日集中講義でセミナーに出られず、そのことを伝えられた先生も帰ってしまったということが判明した。ギリギリに来てしまった僕もちょっと反省すべき。とりあえず今日は帰宅することにして、来週は二人とも集中講義なので、次は再来週になる。

上のようなツイートをしたが、実際には読まず、院生室でしばらく駄弁っていた。入学から4年以上経った今でも僕が同級生の名前をほとんど覚えていないという話が出て（出したのは僕ではないことを念のため注意しておこう）、実際その時喋っていた2人のうち片方の人の名前がわからないということをカミングアウトした。ショックを受けたような反応をされてかなり申し訳なさがある。

その人とは昔から頻繁に生協で遭遇するしよく話すので、僕はもちろん友達だと思っていたし、反応から彼も僕のことを友達と思ってくれていたのだろう。当然顔を見れば一発で認識できる。ただ自分の中で、ある人が友達であることと、その人の名前を知らないことは矛盾なく両立してしまうのであった。名前を知らなくても適切に代名詞やジェスチャー・目線を使えば会話は問題なく行えるし、仲良くなってから改めて名前を確認するのは躊躇われる。今日ちゃんと名前を聞いたので、このような強烈なエピソードもあるから多分忘れない、と思う。

夕食を食べる約束をしていたホスフィンにセミナーが消えたことを連絡しておいたら、わざわざ院生室まで来てくれた。元からいた2人と別れてセミナーが行われるはずだった教室に戻り、2人でゼミっぽいことをした。お互いに今やっていることを喋るやつ。教科書はまだ読み始めたばかりなので、その前に読んだ論文について喋った。ホスフィンはもう具体的な問題に取り組んでいて、学士で卒論を書く必要がない数学科のぬるま湯加減が意識された。

午後6時くらいになって教室を出て学食に向かった。普段使う理薬食堂は今工事中で閉まっているので、少し歩いてけやきダイニングというところに行った。ここは窯で焼いたピザが売られている、ちょっとオシャレなところだった。ところで、3本の直線によって円は最大7個の領域に分割されるが、これを一般化すると怠け仕出し屋の数列というものになるらしい。

コンビニで原付の軽自動車税を支払いつつ帰宅。次の1か月の新刊ラノベをチェックした。買うことにしたものが19冊あり、2冊は予約受付が終了していたため、残り17冊を注文。予約受付の終了とはおそらく既定の冊数に達したからだと思うが、発売まで1週間以上あるのにもうそういう売り切れっぽい状態になっているのは驚き。人気シリーズの続刊なので理解できないことはないか。

今日のCF combinedはwriterが青だったのでサボって、深夜までラノベを読んでいた。FFの方が仙台に来ているようだったので、リプライを送って明日会う予定を立てた。

午後11時半からTCB47に出た。日曜日終了なのでここに各問題へのコメントを書く。

1問目はうっかりbit全探索を書こうとして、問題名が答えになっていることに気づいた。4問目はなかなか難しい。\min(X,A_i)\le 1の場合だけ加算する。\min(X,10^9)も一緒に管理して解いた。7問目は面倒。「楽しさがXより大である間常に行う」としたときT回以内に収まる最小のXを二分探索した後、残りの行動を全部楽しさXで行ったとして値を求める。ここで二分探索の範囲は必ずX\ge 0となるように決める。

8問目は難しかった。初手では適当に取る順番を決めて、swapしたときの合計時間の変化を見るものと考えたが、全然うまくいかない。しばらく考え込んで、取る順番より経路をもとに考えたほうが良いことに気づいた。ある経路を通るとき、各パンはそこを最後に通った瞬間に食べるのが良い。こうすると、まだ食べていないパンの区間を狭めていくようなdpが考えられる。区間のどちらの端にいるかも次元に持って、そこのパンを食べた後区間を一つ狭めつつどちらの端に移動するか決める。配列外参照で1WAと、時間も結構かかってしまい-29pt。

9問目は棒を取れるrの範囲をそれぞれ求めて区間スケジューリング。範囲の両端は2乗したものが有理数になるのでそれで持って、比較は__int128を使った。後からよくよく式をチェックしてみれば、確かに分子が10^{16}オーダーになり得るものの、比較で出現する有理数のペアはどちらかの分母が必ず1となっていたりして、うまいことオーバーフローしないようだ。直線と点の距離が線分と点の距離になる条件を記述し忘れ1WAで-15pt。

10問目はそれぞれの木で貪欲法を使い最大マッチングを求めた後、マッチングに使わない点同士を優先的に辺で結ぶのが良い。連結成分ごとに使わない点の個数を持って、残り1個同士をできるだけ結ばないようにする。

合計-44pt。WA2つがそれぞれしょうもない理由なのがつらい。8問目の配列外参照は、それだけでほとんどのケースに落ちるということが信じられず、他に原因があるものと思ってかなり念入りに確認していた。

少しコードゴルフしてから日記を書き、シャワーを浴びたりラノベを読み進めたりして午前4時半に布団に入った。そこからハーメルンの更新分を読んで午前5時就寝。

05/20(金)

午前11時起床。昨日、正午あたりには仙台駅近くにいると宣言したので、その通りにするため準備して出発した。

狙い通り到着。駅ナカのドトールで食事がてら時間をつぶし、お相手の方から仙台駅に着いたとの連絡を貰ってすぐ駆け付けた。それほど自由に行動できない状況らしかったので、サッと会ってパッと帰る感じ。自己紹介して、アカウントのホーム画面を互いに撮影して、一人とツーショットを撮って、あとは少し喋って別れた。

そのままゲーセンに向かい、午後1時半から夕食を挟んで午後10時半まで遊んだ。

まず夕食前の成果。理論値が2譜面、14+のSSSとSSS+がそれぞれ1譜面、15のSSSが2譜面。15のSSSが2譜面！？

2回ある高速乱打がどうにもならず、追加されてすぐ出した鳥寸からちっとも伸ばせていなかった。今日は見えたまま手を動かしたらスルスル通って、2回目で鳥に。普段と何が違うのか全然わからないので、結局そうやって「押せる日」を待つしかないように思える。その分押せる人にとってはかなり簡単な部類の譜面だとされていて、実際これが14+初AJの人をTwitterで何人も観測した。

非対称トリルっぽいところ、具体的には85小節目で出したはず。ここは譜面が見えておらずいつも勘で押しているので仕方ない。今日はそれ以外の部分で全然出さず、我ながら上手かった。

今日解禁してすぐSSSまで出た。普通にやると追いつかないが、追いつかないくらい速いので擦っても通る。ありえないくらい簡単だった。これが15なら確かにContrapassoもotoriiも15。

特に運指は組まず全部見えたまま押して、癖がつく前に噛み合った。今日は信じられないくらい上手。スコアも今のところ15で最も高くなっている。

何度も上手上手と連呼しているように、今日はこれまでとは別次元に上手い日だった。もっと15のSSSを出せるかと思ってX7124と蜘蛛の糸も狙ってみたが、それぞれ7k弱、5kで断念した。癖がついてしまったので、やはり15と向き合うときはちゃんと運指を組まないといけないようだ。しかしそう考えるとPOTENTIALは上手かったな……。

ラーメンを食べて別のゲーセンでもう少しプレイした。食後すぐは眠かったのと、少しすると音ゲーサークルの人々が来て待ちが発生したため、適当に14+を触るくらいで終わった。とは言えこれも上手く、いくつか伸びたのと、larvaのAJを出した。本当にスッと出て、直後は手が震えていた。ただ精度は不甲斐ない。理論値を狙う時と同じ判定なのに、難しい譜面だとFASTに寄ってしまっている。赤Jでも通ればいいやとプレイするのではなくて、ちゃんと光らせることを意識してもいい頃合いなのかもしれない。そういう意識を持てるほど落ち着いてプレイできるようになったはず。

午後11時前に帰宅。疲れ果てて長い間ネットサーフィンをしていた。日付が変わったあたりでRebellionの理論値ツイートが流れてきて目を剥いた。

ニコニコ動画を見ながら日記を書いていた。午前6時くらいに切り上げ就寝。

05/21(土)

午後4時起床。二度寝はしないことにして起き上がった。用を足してすぐ生協の冷凍弁当の配達があって、少し早かったら応対し損ねるところだったと冷や汗をかいた。

YouTubeに時間を吸い取られつつ日記を書いて、午後9時からABC252に出た。

AtCoder Beginner Contest 252 - AtCoder

Aはdcで2B。BはRuby。ここからC++に切り替えた。Cは揃える文字を全探索して、どう止めるのが最適か考える。リールにおける文字の位置の被り具合を見ることで少なくとも何周する必要があるか求まるので、最後の周はどの位置まで回す必要があるかを確認すればよい。Dは手癖でjを固定しようとしてうまくいかなかったので、異なる3要素の取り方を求めて並べる方法を数えようとしたら、i\lt j\lt kとした場合とA_i\lt A_j\lt A_kとした場合が一対一対応することに気づいた。Eは初手がわからず少し悩んだ。初めのd_2,d_3,\dots,d_Nからどれくらい増えるか考えようとして、各頂点への最短経路をうまく選べば一切変えない状態が達成できると気づいた。

Fはかなり悩んだ。解説にあるような操作の二分木への言いかえを真っ先に行ってしまって、そこから各要素に深さを割り当てる方法をずっと考えていた。なんとなく見覚えがあるのに全然解けないな……と思いつつソートしてdpなど考えているうちに、急に脈絡なく最小要素2つのマージを繰り返す方法を思いついた。正当性もわからないが、自分の直感や既視感はこれが正しいと強烈に主張しているので、実装。しかしWA。実はそれ以前の考察で\sum A\lt Lの場合は最初に使わないパンを切り離してよいという大嘘をついていた。幸い「使わないパンはまとめて切り離す」というところまでは考えていた証明も正しそうなので、A_{N+1}=L-\sum Aと追加して同様のことを行ってみたら通った。

Gは簡単。区間[l,r)が頂点lを根とする木になる場合の数を、区間dpで求めてみる。特に工夫しないと区間ごとにO(N^2)のdpで計算する方法が考えられて、とりあえずサンプルは合う。ここで区間ごとのdpをよく見ると、左端を固定したとき右端を伸ばすごとにO(N)で更新するように書けていることがわかる。区間dpで扱う区間の順番をl降順・r昇順に書き直して、rを動かすときにdp配列を使いまわすようにしてO(N^3)になった。

Exは、後から振り返ってみれば惜しいところまで行ったようだ。まず、ネックレスの作り方がそれほど多くないことに気づく。適当にdpして調べてみると、N=70で最大10^{11}くらいにしかならないらしい。よって半分全列挙ができる。列挙したものをA,Bとして、BをBinaryTrieに持っておく。美しさがX未満になるようなネックレスの作り方の総数を求めるときは各a\in Aに対し\#\{b\in B\mid a\oplus b\lt X\}を求めればよく、これはBinaryTrieでO(\log\max B)になる。Xを二分探索することで\logが2つついた解法が得られた。案の定TLEして、BinaryTrieの構築だったり探索をベタ書きして高速化を試みたが、結局通らなかった。

7完で58位。Fが遅いのは反省。二分木へ言いかえる前に操作を逆順に見ることができていれば、これがマージテクと全く同じであることに気づけただろう。少なくとも、このことを知ってからはそうとしか見られない。既視感もこの事実からきているはずだ。

コンテスト後にExを改めて考えてみた。コンテスト終了直前は、すべてのa\in Aに対して毎回BinaryTrieを根から辿るのではなく、ある程度まとめつつ辿ろうとしていた。つまり、そのノードに到達するAの集合を管理するということ。そうやってX未満になることが確定した個数をカウントする実装をよくよく見ると、Xのbitが立っているときだけカウントが増えていることに気づいた。このことから、BinaryTrieを辿りつつXの上位bitから立てるか立てないか選ぶことで、カウントした値を二分探索のしきい値ギリギリにできることがわかる。BinaryTrieの\logと二分探索の\logをまとめられて、無事AC。

コードゴルフ。Aは提出スピードで辛くも勝利を掴んだ。13秒。画面の録画を確認したところ問題一覧ページへの遷移に5秒かかっているので、A問題のURLを用意しておけば夢の1桁秒ACが達成できたのかもしれない。B、CはRaku。DでもRakuのBagを使ってみて、TLEしなかったもののRubyのtallyのほうが短くなった。FはPythonのheapqで、負け。A=sorted(A)みたいなことを書いていたのは反省。これはA.sort()である。他は手付かず。

午前1時からTCO22 R2A。Stage3でR4への進出が確定しているはず……であるが、CLISTはあくまで非公式であるから、絶対確実とまでは信頼しきれない。公式からの発表はまだないため、そこそこまともな問題が出るとの評判も聞いたことだし、念のためR2にも参加しておくことにした。

TCO22 Stage3の結果が今日のSRM826で確定していた。僕はSRM825に参加していないのでちょっとひやひやしていたが、それ以外の成績がまあまあ良かったので問題なくRound4への進出が叶った。TCOの予選はcombinedのratedなので、毎年通行料などと言われて評判は良くない。Topcoderのシステムでcombinedにするのはさすがに時代遅れ。ナウなヤングはFull-Feedbackにしか出ない。 https://clist.by/standings/tco22-algorithm-stage-3-28608402/

週記（2022/03/28-2022/04/03） - kotatsugameの日記

https://community.topcoder.com/stat?c=round_overview&er=5&rd=19223

参加者を見て赤が多いなと思っていたが、combinedだけあって部屋分けで分散し、Roomには僕含め3人しかいなかった。

Easyはタコ足配線の問題だと気付いて問題文をスラスラ読めた。分岐できるものをとりあえず並べて、空いたところに残りの家電を差していく。どこがどれだけ空いているかを適当なコンテナで管理して、使うたびにpopしていくような実装をした。

Medはカス。これをTopCoderのシステムで出題するのは人の心がない。いろいろ方針はあると思うが、自分の解法を説明する。まずleading zeroを作ることによって桁数を減らして、Yの桁数未満にする。できなければYは一桁なので、X=1としておく。次に9を並べた形を作ってインクリメントすることで桁数を増やし、Yの桁数と一致させる。特に、一致した時の形が10のべき乗であるようにする。先ほどX=1としたのはこれを満たすためである。あとは最下位桁を弄ってswapを繰り返すことで、基本的には目的の値が得られる。

ただし、Yの最上位桁以外がすべて0の場合は注意する必要がある。最上位桁を揃えた後swapすると、最下位桁に1が来てX=Y+1となってしまう。これはどうしようもないので、代わりにY-1を作ってインクリメントすることにする。Yが10のべき乗の場合は桁数が減ってしまうが、その時は元からX=Yとなっている。あとは念のためYが一桁の場合も別に処理しておいた。

Hardは半分全列挙やるだけ。なぜ900点がつけられているのだろうか。3問提出して25位あたりで、残り時間はMedを1\le X,Y\le 1000で走らせてチェックしていた。WAが大量に表示されて心臓が消し飛びそうになったが、チェッカーの間違いだったことに気づいて一命をとりとめた。

今回はChallengeフェーズも頑張る必要がありそう。しかしMedは読みたくないので、Easyだけ集中的に読んでいた。その甲斐あって、本当に久しぶりに一つ落とすことができた。一つしか口がない分岐について、それを別の分岐と繋ぐために使ってしまったのに、さらに家電を差そうとするコードがあった。そういうものをスキップするときにwhileではなくifを使っていた、というミス。

システスは全部通って、12位まで上がった。レートは2655→2699(+44)。部屋のEasyがもう一つシステス落ちしていて、何かと思って読み直したところ配列外参照らしかった。たとえ気づいていたとしてもこれにChallengeする勇気はない。

日付が変わる前あたりにあったしぐれういさんの配信アーカイブを見た。待機画面のイラストに描かれたロリういの表情がかなり良い。その後、朝まで日記を書いていた。午前7時に布団に入り、そこからなろうを読んで午前9時半就寝。

www.youtube.com

05/22(日)

今日がAHC開始の日だと思っていて、正午にかけておいた目覚ましで起床。慌ててコンテストページを開き、一週間後であったことに気づいた。即座に二度寝。

午後4時半起床。今日は通常のOpenCupがなく、代わりにadminから配られたコンテストにバーチャル参加することになっていた。チームメイトの一人が通常の開始時刻である午後5時に間に合わないらしかったが、バーチャル参加なので開始時間には融通が利く。3人揃ってから開始することにして、チームメイトを待つ間はラノベを読んでいた。

午後6時半からスタート。今日のコンテストタイトルにはPTZW 2022 Day 3（Kazakhstan Contest）と書いてあった。

チームで6完。自分が担当した問題は……ない！なんと5時間で1問も解けなかった。ひっじょ～～～に苦しい。途中から思考がフワフワしてしまい、取り組む問題をコロコロ変えていたのだが、これを1問に絞ったところでどうしようもなかっただろうと断言できるほど手も足も出なかった。このコンテストにはいっそ感動した。わざわざadminが選んで配布したコンテストだけあって、どれも問題文がシンプルで、その上ハチャメチャに難しいわけだ。自分の伸びしろを感じる。しかしこの伸びしろを、僕はおそらく埋められないままICPCを引退するのだろう。

直後、午後11時半からCF #793 div.2。

Dashboard - Codeforces Round #793 (Div. 2) - Codeforces

Aから少し難しい。sと{\rm rev}(s)を並べ、一文字削除して一致するという条件を線を引くなりして確認してみると、ある範囲の文字がすべて一致している必要があるとわかる。最近ARCで見たことがある気がする。とにかく、sの中心から同じ文字が連続する範囲を求めればよい。|s|の偶奇には気を使う必要があった。

A - Remove One Character

Bはi\ne p_iなるp_i全体のbitwise ANDが答えになる。これでソートできるのは、その値を動かすことで一つ一つ揃えていけることから明らか。逆に、p_iを動かそうとするときはXを含んでいる必要があるので、Xは動かす必要のあるp_i全体のbitwise ANDに含まれることになる。

Cは同じ値ごとにまとめて、{\rm LIS}(a)と{\rm LIS}(a')のどちらに含めるか決めていく。同じ値の要素が二つ以上あるなら両方に一つずつ含めることができて、一つしかないなら現状短いほうに含める。一つしかない値が一種類以上あった場合、そのうち一種類を両方に含めることができるので、これを最後に処理する。これまでと同様短いほうを一つ伸ばすとしてよい。

Dはsに含まれる'1'の個数が奇数またはゼロのとき以外必ず構築可能。隣接している頂点をマージしていくことで交差が発生しない。'1'は必ず一個以上存在するので、'0'と'1'が並んでいるところをマージし、新たに'1'であるような頂点と見なす。これを繰り返すと残り全部'1'になって、このとき頂点数が偶数個になっているため、適当な頂点を中心にしてウニグラフを作ればよい。

Eはかなり面倒だった。swap操作を辺と見ると森になっているので、木ごとに解く。葉から順番に揃えてよいという大嘘をついた。p=\{2,4,1,3\}と(1,2),(2,3),(3,4)が反例。

一度辺（swap）を使うとそこで木が分割され、以降二つの木の間で要素を移動できないので、使える辺を見つけるために適当に根を取って各部分木について足りない要素・余っている要素の集合を管理することにした。これは集合のXORで書け、下から順にマージテクで求められる。u\rightarrow vという親から子への辺について、vの部分木に対する集合が\{p_u,p_v\}であればよい。そのように使用可能な辺を見つけたら即座に使い、v以下については別の関数で対応する。「使用可能な辺を即座に使った」という条件から、v以下の部分木で次に使える辺があるとしたらそれはp_vが書き換わったばかりのvに接続していなければならない、ということを利用して、下りながらどんどん使っていく。

使える辺を探すときはuから出ている辺を全部チェックすればよいと考えていたが、それではp_uが書き換わり新しく使える辺が出現する場合に対応できないことに気づいた。何とかしてチェックを高速化する必要がある。ここで、求めた集合のサイズが常に0または2であることに気づいた。このことはvalidな順番に並べたswapで後ろから帰納法することで確認できる。そして、再度「即座に使う」条件を用いて、vの部分木に対する集合はサイズ2かつ一方が必ずp_vであることも言える。なぜなら、v以下の辺が使われるのはu\rightarrow vの辺が使われた後であり、p_vは必ず辺u\rightarrow vのu側に行かなければならないからだ。

よって、「p_vでないほう」をキーにして辺を保存しておくことで、使える辺＝キーがp_uである辺を即座に取得することができるようになった。今、集合のサイズが高々2であることから、各部分木に対する集合を直接保存しておけるため、u\rightarrow vを使った後v以下を揃えるときは、それを参照しつつ木を下っていける。提出したら何とか通った。

Fは見た目こそヤバいものの簡単。コストの条件からより近い頂点に向かって流すと嬉しいとわかる。コストを分割して考えると、l\le i\lt rについてa_iとa_{i+1}の間を通るフローの流量は\left|\sum_{k=l}^i b_k\right|であると言える。よってS_j=b_1+\dots+b_jとして、(a_{i+1}-a_i)\times|S_i-S_{l-1}|のl\le i\lt rに渡る和を求められれば良い。S_i\gt S_{l-1}の場合とS_i\lt S_{l-1}の場合に分け、Sの降順・昇順に見て、a_{i+1}-a_iと(a_{i+1}-a_i)\times S_iそれぞれの和を管理するセグメント木を用意しておけばよい。実装が間に合わなかったが、システス後に書き上げて提出したら通った。

システスは全部通って5完28位。Eの正当性は日記を書きながらassert等で必死に確認したものであって、コンテスト中は正直半信半疑だった。

TCB47が終了していた。3位。2位とは1pt差で惜しいところ。1位はこのセットでも満点近くを叩き出している。自分もしょうもないWAがなければなあ、とそれなりに悔しさを感じた。

日付が変わったあたりで先生からメールが来ていたのに気づいた。来週火曜日から金曜日は集中講義であるが、それに関連する座談会なるものが月曜日に予定されていて、対面で出席してくださいとのこと。直前に言われるとかなりびっくりしてしまう。インターン先定例会と被ってしまうためオンラインで勘弁してほしい気持ちが強いものの、こういうところでは学業を優先するのが正解なのだろうとわかっている。定例会を休むと伝えておかなければならない。

朝までかけて日記を書いていた。今週もかなり溜めていて、木曜日以降を一息に書き上げた。土日はコンテストが少なく時間に余裕がありそうだなと思っていたのに、実際は何もできていない。月曜日締め切りの課題が2つあることに今更気づいたりもしてしまった。謎の忙しさをずっと感じている。おすすめのなろうを纏められていないし、いくつかまた溜まっている質問への回答もできていない。しばし待たれよ。