週記（2021/11/01-2021/11/07）

11/01(月)

午後4時過ぎ起床。インターン先の定例会のギリギリまで寝るのが常態化している。いつかやらかすのではないかと自分のことながら心配だ。

進捗報告のスライドを用意して、インターン定例会に臨んだ。進捗報告は最近我ながら内容が薄い感じがして、せめてもと前回からの更新部分を強調しようとしたのだが、そのとき「良くなっている」という言葉を使ってしまった。以前から、いま行っている学習の結果がどうなってほしいかは伝えられていて、その理由についても自分で納得していたのだが、そういう基準に従えば僕がこのとき見せた結果は特に良くもなっていないものだったのだ。メンターさんから即座に訂正が入って、間違えてしまったことに凹んでいたら、結果が良くなっていないことに凹んでいると取られたのか、慰めの言葉をかけていただいた。まあ……それもないことはない。

他の人々の報告を聞いたり、そのあとさらに技術的な話をしていたところ、Aho-Corasickが使えそうな箇所を見つけたため、興奮してそのことを指摘した。しかし課題を微妙に取り違えていたのか、それほど効果がないかもしれないという反応であった。そのあと別の人からさらにいくらかの助言があって、細かい計算量の評価に入っていたのだが、自分はAho-Corasickの計算量すらよく知らないためついていけず、残り時間は置物になって過ごしていた。

14の理論値が出たらしい。そもそもこの曲を解禁していないため思ったより自分の反応が薄かったが、すごい勢いでツイートが伸びていて、それを見てようやく偉大さがわかってきた感じがする。

10月の読書記録をまとめてツイートした。先月はちっとも本を読めていなかった。やはりネット小説を読み漁っていたからだろうと思うが、そちらは記録をつけていないため、わからない。つけるべきかと以前より思ってはいるものの、未だどのような形式の記録になるのか想像がついていない。

今年もICPCの出場場所をサークル顧問の先生に用意してもらえたらしい。今年は山の上の部屋でチーム全部を賄えるようだ。どの部屋で出場するかについては、当日AtCoderレートの総和が大きいチームから順に選べることになるらしく、面白い。そういえば数年前のACPCで、テーブルに座った一同がレート順に中華を取るため、真ん中の回る部分をぐるぐる回していたことがあったが、これも自分では面白いと思っていた。しかしその後参加記等でいくつかの反応を見聞きするに、微妙に引かれてもいたようで、感覚の違いに戸惑った。

テーブルの可動部分を回して料理を取る一般的なテクを使用するタイプの懇親会でした。 我々のテーブルでは料理を取る順番はAtCoderじゃんけんによって決定されました。

ACPC2019 参加記 - kotatsugameの日記

先週の週記をまだ書いている。KUPC-Eで用いた、inverseの辞書順を最小にするような順列の構築方法（後ろから貪欲）について、コンテスト中の考えが論理的でないことに気付いたため、正当性を確かめようと考えを巡らせていたら、30分くらい椅子の上で寝てしまったようだ。あまりにも眠すぎたため今日はもう寝ようかと考えたが、少し週記を書き進めるうちに眠気が多少マシになったので、そのまま最後まで書ききった。

午前2時くらいになって、ようやく先週の週記を投稿した。

その後しばらくネットサーフィンをした後、布団に入って少しラノベを読み、午前6時就寝。

11/02(火)

午前11時過ぎ起床。今日は正午から1on1を入れているので、それに間に合うよう急いで学食に行き、さらに注文していた本を数冊受け取ってきた。

正午から1時間弱の1on1。これまでの学習を事前調査と位置付けて、これから実用化の方向性を探るため、別チームの人にヒアリングを行ったりすることになるようだ。思ったより多くの人を巻き込むようなので、頑張っていきたい。インターンを開始して初めの1on1のとき、いくつか提示された中から今取り組んでいる課題を選んだ。そのときは、完成したときの効果が結構大きいだろうとワクワクしていたのだが、学習を進めるに従ってそんな容易いものではなかったと深く実感するようになった。今はメンターさんや別の方々に何とか介護をしてもらい、当初僕が妄想していた形よりは範囲を絞って、それで実現が可能かを見ている。自分が書いたコードで意味がありそうな値が出るのは楽しかったが、精度という面ではお話にならなかった。

わざわざ正午に1on1を入れてもらったのは、この予定で無理やり起きてゲーセンに行こうと目論んでいたからだった。ということで、出かける。セガ仙台に行ってみると、チュウニズム8台中6台の電源が落とされており、明後日に迫った新作稼働に備えているようだった。とりあえず1クレプレイして、適当に選んだ13で新規AJが出た。

さすがに2台は辛いので、タイトーステーション名掛丁店に行った。こちらは3台が稼働。実はここがたくさん稼働しているというのはTwitterで教えてもらった情報で、その人ともう一人がプレイしていたため、3人でしばらくマッチングをした。明日で消えてしまう曲のマッチング称号を一緒に取ってもらい、ありがたい限りであった。

ICPCのルールに更新があって、特にACL等をincludeしている場合はわざわざ展開する必要がなくなるらしい。

さらにしばらくプレイして、13の新規鳥と新規AJをそれぞれ1譜面ずつ。ホスフィンが来たので、夕方あたりにいったん離脱してラーメンを食べ、本屋に寄った。本屋では一冊購入。ラノベの新刊はあらかたチェックしているが、一般の文庫本のチェックは漏れがちなので、リアル書店に来たらそちらを重点的に見るようにしている。

またゲーセンに戻る。メルトを選曲したら、今日一発で理論値が出た。何回か連奏したことがあって、判定をいろいろ弄ったりしても全然出なかったのに、今日は±0でシュッと出て驚き。終盤は緊張で死にそうになっていた。

と、細々とした成果はあったが、今日一番の目的は「Memoirs of ○○」マップの完走だった。先週の週記ではMemoriesと書いていたが、正しくはMemoirsらしい。ミンミンゼミというキャラクターを今日育て終わったが、これがランク15になると獲得できる「セミファイナル」というスキルは、どんなに出来が悪くても25%の確率でゲージが9本たまる。これを使って課題曲が14でノルマ9本のマップを突破し、またキングレコードというキャラの「キングレコードゥァア゛ーッ！」というスキルでノルマ10本のマップを突破する算段だ。

セミファイナルを最初に使ったのは、混沌9マスノルマだった。8回連続で失敗して疲労で死にそうになっていたが、9回目で何とか成功。他3譜面ではそれぞれ2回、2回、4回で成功し、合計回数としては17回中4回成功ということで、だいたい25%だったが、よりにもよって混沌で失敗を続けなくてもよかろうというものだ。まあ、諦めなかった甲斐もあって、無事5つのマップを完走できた。このツイートをしたときはマップ名のスペルが間違っていることに気づいていなかったが、後からよこにリプライで指摘された。

さらに1クレプレイして旧筐体納めとし、帰宅。ギリギリCF div.3に間に合う時間に帰ってこれたようだったが、あまりに疲れているため見送ることを決意。シャワーを浴びてパソコンの前に座り、しばらく動けなくなってずっとYouTubeを見ていた。少しラノベを読んで午前3時就寝。

11/03(水)

昼頃起きたような記録がある。しばらくクネクネしていたが、無事二度寝できたようだ。午後8時起床。HACK TO THE FUTURE 2022 予選が始まっていた。ヒューリスティックRatedらしい。

HACK TO THE FUTURE 2022 qual - AtCoder

チュウニズム生放送を少し見た。ゲストプレイヤーによる新難易度「ULTIMA」のプレイを見て満足したので閉じたが、その後ここにきてさらに大量の新曲追加情報が発表されていたらしい。公式アカウントのツイートで追っていた。他のいろんな音ゲーから移植される曲が発表されていて、特に最後に発表されたらしい「ピアノ協奏曲第１番”蠍火”」はコナミの曲ということが衝撃らしく大変話題になっていたが、他音ゲーをほとんどしない自分はよくわからず、ちょっと寂しい思いをした。

先週Pythonで選択アルゴリズムを実装した課題の評価がついていた。120/120だった。コードに対するコメントやフィードバックがないのでかなりあっさりとした感じ。そういえば昨日、今週分のスライドがClassroomに上がっていて、そこにこの課題の想定解のようなものが書かれていた。数値が4000未満の整数なのでバケットソートが一番速いです、と書かれており、そのような制約は一度も触れられていなかったが？という気持ちになった。サンプルコードではfloat型で読み込ませておきながら、バケットソートのコードではしれっとint型で読み込んでおり、そのあたりも気に入らない。

今日はゲーセンに行かないので、ちゃんと昨日が旧筐体納めになった。確認するとギリギリ5000プレイに届いていた。

今日はやけに眠いので、布団に入ってラノベを読むことにした。途中ほとんど寝落ちしていたが、何とか意識を取り戻して1冊読了。

「隣のクーデレラを甘やかしたら、ウチの合鍵を渡すことになった」3巻。良かった。序盤のお互いに隠しきれていない好意や、その後トントン拍子に進んでスッと告白に成功しているのが良い。両片思い状態で焦らされる話もいいけど、こういうのも僕にとって新鮮味があった。あとがきではかなり打ち切りになりそうな雰囲気が出ていてかなり怖い。

今週分のPythonの課題を終わらせる。行列の各要素を文字でおいて行列式を余因子展開で求め、要素の積や和を文字列で表現して行列式の公式を作るという課題。ガウスの消去法で計算量を落としてみようかと思っていたが、文字式の割り算の実装が面倒になったので、特に変なことはせずほぼサンプルコードのまま提出した。

布団に戻ってまたラノベを読み、さらに1冊読了。「英雄と魔女の転生ラブコメ」。主人公最強系の話をもとにラブコメするのだと思って買ったが、主人公とヒロインの前世が思ったより重くて、それなりに辛い話だった。

さらにもう1冊。「家事万能の俺が孤高（？）の美少女を朝から夜までお世話することになった話」。非常に良かった。主人公がかなり万能系だったが、途中で風邪を引く描写がある。その意外性がグッときて、その後のヒロインの看病シーンも含めて良かった。ヒロインが表紙イラストでご飯茶碗に食べ残しのご飯粒をつけており、ちょっと気になっていたが、本文中ラストシーンの描写ではちゃんと全部食べ切っているようだったので、許した。

Kaggleのコンペが終了した。「Google Brain - Ventilator Pressure Prediction」。結局、ほとんどと言っていいほど作業を行わなかった……。早々に公開された上位チームの解法を読んだところ、PID制御のパラメータを全探索して入力とよく一致するものを採用することで、全体の何割かを誤差なく計算できるというものらしい。うーん、なるほど？どちらにせよ、先週も書いたように上位者のコンペにおける通常の動きを知れたことはよくて、コンペ特有のHackには今のところ興味がない。

午前10時になって、チュウニズムの新作が稼働し始めた。追加された2マップにはそれぞれ隠し曲が1つずつあったらしい。またSSS+はスコア1009k以上が条件となる。さらに、新曲の蠍火はレベル15ということで、オリジナル曲以外で旧バージョンのレベル14相当となる初の譜面であった。

午後10時半就寝。

11/04(木)

午後1時起床。焦りながらゼミのZoomに接続した。今週も微妙に遅刻してしまって申し訳ない。さらに、来週は対面で行われるため、この時間に青葉山にいなければならない。

日記を書きつつゼミを聞いていた。任意の正整数kに対して、k\times kの格子点たちであってどれも原点から見えないものが存在する、つまりa\lt\forall x\le a+k.\;b\lt\forall y\le b+k.(\gcd(a,b)\gt 1)なるa,bが存在するという命題を、実際に構築して示す部分があった。k=2における実例も紹介されたが、かなり値が大きいようだったので、自分でプログラムを書いて調べ、より小さな解を見つけてコメントとして付け加えたりしていた。調べる範囲を小さめにしていたため、k\ge 3でもう見つからなくなってしまった。

ゼミが終わってからもしばらく日記を書いていたが、さすがに眠い。午後6時くらいに布団に倒れこみ、そのまま寝てしまった。

11/05(金)

午前1時起床。ヤバい。

どうせ眠れないので、ちょっとパソコンの前に移動してyukicoderのテスター作業を終わらせた。また布団に戻り、ラノベを1冊読んだ。

「最凶の魔王に鍛えられた勇者、異世界帰還者たちの学園で無双する」。久しぶりに読んだ主人公最強+自分の実力を隠している系で、面白かった。主人公以外の異世界帰還者たちはそれぞれ固有の能力を持っている。1巻にして他人の能力を奪う能力が出てきてしまい、クライマックスという感じがするが、この先どうなるのだろう。主人公をメタろうと思えばいくらでもメタれるはずで、展開が楽しみ。

午前7時前に再度就寝。午前8時半から午前10時半ごろまで起きていた形跡があるものの、また眠ることができて、最終的に午後2時に起床した。予定では青葉山に午後2時半集合だったが、不可能だったので30分ほど遅刻してしまった。

ICPC国内予選。これについては別に参加記を書いた。

kotatsugame.hatenablog.com

午後8時すぎに帰宅して、しばらくエゴサを楽しんでいた。蟹江もなみさんの順位表実況動画で僕のチームのC問題FAが言及されており、嬉しい。

午後9時20分からyukicoder 321。全完。

yukicoder contest 321 - yukicoder

Aは何かいい性質があるのかと思ったが、結局よくわからなかったので、無理やり8進数に変換して数えた。とりあえず16^n=2^{4n}=a\times 8^{\frac{4n}{3}}で大まかに求めて、あとから繰り上がりを処理する感じ。Bはある数dが全体のgcd（の約数）になるためにはいくつまで整数を書き換えず残せるか、をすべてのdに対して求める。数列の要素を出現頻度でカウントしておけば、愚直に求めても全体で調和級数になる。CはKの約数だけをキーに持つdpをmapで書いたら通った。K\le 10^9という制約から約数の個数は最大1344個らしい。もう1桁大きいと思っていたが、それでも通るだろうと楽観的に投げた。

DはA問題と同じ感じの問題で、今度こそいい性質を見つけなければならない。ちょっと試してみると、16進数3桁と8進数4桁がピッタリ対応しているようだった。しかも各桁の制約から繰り上がりがなく、どの桁にも0が出現しない。よって16進数の桁数から8進数に直したときの桁数を計算でき、それが7の倍数である必要がある。調べると、N\bmod{21}=0,5,10が該当するようだった。サンプルからN=21とN=10の解が得られ、さらに手でN=5の解を求めておけば、これらを適当につなげることによって条件を満たす数が存在するすべての場合に対して構成することが可能になる。なかなか面白い問題だった。

Eは答えに対する寄与を求めるいつもの。(A_i,i)で順序を入れておく。ある要素A_iを見ているとき、組(l,r)に対する係数は[l,r]に存在する(A_i,i)より小さい要素の個数を2の肩に乗せたものになる。これを2^{c(l,r)}とおけば、指数法則から2^{c(l,i)}\times 2^{c(i,r)}と分解することができて、しかも\left(\sum_{0\le l\le i}2^{c(l,i)}\right)\times\left(\sum_{i\le r\lt N}2^{c(i,r)}\right)ですべての組(l,r)に対する係数の和が得られる。左右それぞれ区間MUL・区間SUMの遅延セグメント木で取り扱うことができる。

Fは難しい。先頭から見ていき、各操作が終了した段階で最初xだった要素がf(x)になるという関数を考えると、グラフはのこぎりの歯みたいになっている。f(x)=0なる点\{x_n\}_nを管理することにした。更新は、d=f(A_i)\gt 0ならば操作が行われ、x_{i+1}-x_{i}\gt dのとき新たにf(x_{i}+d)=0となる。ここで、\{x_n\}_nは常に昇順で管理されているとした。実際にはsetに点を入れて、さらにx_{i+1}-x_{i}を優先度付きキューに入れて管理したら通った。計算量解析はよくわかっていなかったが、解説によれば、新たにf(y)=0とする回数が高々2\times 10^5回ということから十分高速だとわかるらしい。

先週のyukicoder 320を埋めていたが、途中午前1時からSRM 818に出た。終盤コンパイルがタイムアウトするようになって、unratedになった。

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

Easyは簡単。Medはそれっぽいdpを書いたらサンプルがあったが、誤差が怖い。手元でいくらか実験して、dp配列が結局二項係数を2べきで割ったような形をしている、ということに気づいた。しかし、最終的にはそれらに係数をかけて中途半端な和を取っているので、どうにもならなそう。そのうえ他の人がどんどん提出しているようだったので、これで落ちるならみんな落ちるだろうと思い切って提出した。

Hardは乱択。100要素から特定の6要素を選ぶとき、左右50要素に3要素ずつ分かれる確率は、僕の計算が正しければ\frac{\binom{6}{3}\binom{94}{47}}{\binom{100}{50}}で大体32%くらいになるらしい。なので、適当にシャッフルした後左右から3要素以下を選ぶ方法を全列挙し、組み合わせるということを20回くらいやれば十分通りそう。頑張って書いたあたりでコンパイルがタイムアウトするようになった。さらにCEも出たので、仕方なく手元でコンパイルが通るまで試していたところ、うっかりそのファイルを開いたままバッチテストでのデバッグを初めてしまい、どこを変更してもArenaで見える答えが変わらないままコンテスト時間が終了してしまった。後から投げたらちゃんと通った。

実はこのミスは初めてではない気がする。TCのサーバに不備がなければ、そのうちデバッグ出力を挟もうとして出力されないのに気づいたり、そもそも別ファイルを編集することがなかっただろうが、それにしても開いているファイルが何かわかっていないのはひどい。Vimのどこかに表示するようにしておいたほうがいいのかもしれない。

yukicoder 320の続きを進めて、全部通した。

yukicoder contest 320 (Stray Bullet) - yukicoder

A、Bはよい。Cは素因数分解。DはB社の製品のみを購入した状態から1種類ずつA社の製品に交換することを考えて、ソートして貪欲。Eは頑張って再帰的に数える。文字列が反転されているか否かのフラグを管理するのに失敗し続けていた。Fは座標の符号を4通り全探索して、その内側でどれくらいずらすかを決める。得点をmapを使って数えたらTLEしてしまったが、vectorに溜めてソートしたら余裕をもって通った。Gはヤバそうな見た目をしているが、bit全探索できて面白かった。Hはタグにバーンサイドの補題とあったので、ググって解いた。

午前5時就寝。

11/06(土)

この日はコンテストもなかったので、1日中布団の上で過ごした。起きている間はなろうを読んでいた。TwitterやChromeの閲覧履歴から復元したところ、起きていたのは以下の時間帯であった。

  • 午前11時～午後1時

  • 午後3時～午後5時

途中で生協の弁当配達を受け取った。

  • 午後9時～午後11時半

  • 午前2時半～午前8時

11/07(日)

午後3時半起床。ICPC参加記を書こうとしたが、少しコードゴルフをしているうちにOpenCupの時間になった。

今日はチームとしてACEFGHJの7完。ここで、実際には問題番号はアルファベットではなく数だった。

最初にAを読んで、簡単枠かもと言ってほかの人に見てもらったが、そんなことはなかった。しばらくしてCが大量に通されていたので読むと、こんなものがOpenCupに出るのかと思うほど自明だったのですぐ通した。さらにHも場合分けするだけだったので通した。EとJがそれぞれ通されている間にFを考えていると、ただ基底を取るだけに見えてきたので、それでよさそうというチームメイトのお墨付きをもらって実装したら通った。実は問題文が微妙で、曜日を進める操作の話だったから1日待つのは可能かということをclarで聞いていたのだが、答えが返ってくる前に投げて通してしまった。不可能ということでよかったらしい。

しばらく空いて、Iが解けた気になったので書く。Aが落ちているのを尻目に投げるとWAで、デバッグしてもう一度投げる直前にチームメイトから解法が破綻していることを指摘された。ただ大筋はあっていそうだったので、修正して何度か投げるも、WA。そのうちAが定数倍高速化の末に通り、いつの間にかGも通されていたが、よくわからないままABCの時間になってしまった。

ABC途中で戻ってきたときの話になる。前は重実装を投げ出してABCに行ってしまったので、今回は15分で戻ってきます～と言っておきながら、実際に戻ってきたのは45分後だった。Bでマラソンをしているらしく、大量にペナがついていて面白い。その後結局Iも通らずコンテスト終了。IのWAの原因は、多項式を微分する際のオーバーフローチェックで、そのまま微分し続けたら消えてしまう項のオーバーフローを検出して止めてしまったのが問題だったらしい。

午後9時からABC226に出た。7完。Hはかなり見覚えがあったが、何もわからない。

AtCoder Beginner Contest 226 - AtCoder

Aはよい。17秒でFA+Shortest。BはRubyで、入力から列を取り出してuniqしていたが、実のところ先頭の要素数を含めてuniqしても変わらない。15Bで、これはRakuと同じ。気づいたのがコンテスト終了20分前で、最短を逃したかと思っていたが、何とか取れていたようだ。Cは適当にやる。Dは移動を全列挙するとペアのgcdで割ってよいことがわかる。Eは難しいが、向き付け前はなもりグラフの集合になっている必要があって、なもりグラフのループをどっち向きに回るかで連結成分ごとに2通りある。

Fは難読気味。結局順列をループの集合と見たときにループの長さのLCMをK乗した値が求まればよい。これまで何人決めたかと今のLCMをdpのキーに持ち、遷移はループの長さ=Lとそのループが何本あるか=tで、遷移の係数は\frac{1}{L^t t!}になる。最後にN!を掛ければ場合の数が求まるので、LCMをK乗した値をかけて和を取る。Gは、まず体力と同じ重さの荷物がある場合は貪欲に取って良く、さらに残りについても体力1、2、3の順で貪欲に決めてよいことがわかる。このとき、最終的に重さ4以下の荷物を体力5の人で運ぶか、重さ3以下の荷物を体力4以上の人で運ぶかに分かれ、どちらにせよ体力5の人から順に重い荷物を貪欲に運んでよい。半信半疑でコーディングしたところバグを3箇所くらいに埋め込んでしまい、3ペナに加えOpenCupと交互に見ていたこともあってかなり時間を取られてしまった。

コードゴルフ。ABはコンテスト中のものでよい。CはPerlで頑張る。Dは複素数の引き算をして偏角のuniqueを取ってもいいようだ。精度が気になるところだが、まあ通っているのだしOK。Rakuで書こうとしたらかなりTLEが出てしまい絶望していたが、mapしてからuniqueするのではなくuniqueのas引数を指定して変換しながら重複を削除することでそこそこ速くなり、通った。残りは手付かず。

夜は溜めていた日記とICPCの参加記を書いていた。

参加記を書くのはかなり難航し、集中力が切れてうっかりラノベを1冊読んでしまった。「前世は剣帝。今生クズ王子」2巻。1巻を読んだときの日記でも言及したが、この巻でも主人公の自分語りがあまり性に合わなかった。ただ、今回はそういうものとしてかなり端折りつつ読んだため、ストーリーの面白さに目が向いて、印象は良くなった。

ICPC国内予選 2021 参加記

2021/11/05に開催された国内予選にチームAobayama_dropoutで参加しました。模擬国内予選の参加記でも書きましたが、今年のメンバーはゆきのんさん・ha15さん・僕です。

今年は全チームがサークル顧問の先生の研究室に集まれて、3部屋に3チーム・3チーム・1チームという感じで割り振られました。

コンテスト前

当日の午前1時に起きたりして生活リズムが大変でした。細切れの睡眠を繰り返して、最終的には午後2時になってしまいました。部屋割りのために各チーム1人は午後2時半に青葉山にいる必要がありましたが、これをチームメイトにぶん投げて、ゆっくり準備して家を出ました。主な持ち物はノーパソ、キーボード、マウス、蟻本、考察用紙と筆記具です。

例年C問題に重めの問題が配置されており、それより先にDを通すことが多かったので、今年は僕がC問題を読むことにしました。リハーサルは手付かずでしたが、さすがに4年目なので大丈夫でしょう。一応問題だけ見ましたが、これも例年通りでした。

研究室にあったモニタを1台拝借して、一人だけデュアルディスプレイにしました。増やした画面にはチームで共有したいページを開いておくつもりでしたが、結局、たまに順位表を見るだけにしか使いませんでした。

コンテスト中

問題文：

icpc.iisf.or.jp

今年も、最初しばらくページが見れない状態が続きました。両隣のチームメイトが問題文を開けてからも、僕のブラウザはずっと応答待ちを続けていました。向こうのサーバーの問題だと思ってそのまま待っていたのですが、F5を何度か試してみるとか、テザリングに切り替えるとかしてもよかったのかなと思います。5分くらいしてトップページが開けたので、問題文pdfへとアクセスしたのですが、そこからもさらに読み込み時間がかかりました。

C問題

C問題の読み込み途中で止まってしまったのでリロードしたところ、やっと文面が読めるようになりました。画像はまだ読み込めておらず、文章を読んだ感じは画像がないと理解に手間取りそうだったので、先にD問題をチラッと見ましたが、よくわかりません。C問題に戻って、画像のキャプションから手作業で図を復元していましたが、ゆきのんさんに言われてページをリロードしたところ、今度こそ画像ごと読み込むことに成功しました。

特殊な形をした構文木を操作して値を最大化する問題のようです。許されている操作はちょっとややこしかったですが、どうやら根をその子に取りなおしたり、子の順番を入れ替えたりすることが可能なようです。葉でない任意の頂点を根に持ってくることができますが、このとき残りの木は子の順番を入れ替えるだけの自由度しかないのではないでしょうか。直感的に正しそうで、これを認めればあとは全方位木dpするだけなので、深く考えず実装に入りました。コンテスト後に知ったことですが、ノードたちの接続関係が変わらないことから言えます。

構文解析して構文木を作る部分では、一瞬構造体のポインタを考えましたが、そんなのは嫌なので頂点番号を振って配列と隣接リストで持つことにしました。全方位木dpでは引き算の頂点の処理が面倒でしたが、次数が3で固定なので全通り書き下しました。

コピペを駆使して実装し、サンプルを試すと合ったので、そのまま提出し、無事ACを得ました。ha15さんに言われて気づきましたが、CのFAだったようです。しかし、開始からすでに30分が経過し、Cの代わりにD問題が大量に通されていて、びっくりしました。

D問題

僕がコーディングしている間にチームメイト2人はそれぞれABを通し、Dに進んでいたので、僕も合流します。正直、こんなたくさん解かれているんだから真面目に一瞬考えれば解けるだろうと思っていました。しかしなかなか思いつきません。

とりあえず、サンプル3つ目の5 2 8 3でなぜ風船を配り切れないかを考えることにしました。サンプル1つ目の説明から、どうやら最初に風船が多いポールを置くのがよさそうだったので、とりあえず8を先頭に持ってきてみます。すると残りは5と2+3に分割するのが最適で、8-5=3個余ってしまうようでした。つまり、どれかのポールに特別風船が多いときは、それ以外のポールを2分割するのがよさそうです。2分割の場合の解き方は、要素を順番に見てdp[i][j]=iとjに分割できるかどうかというdpになります。

そういうようなことを棒を積み上げる図を描いてゆきのんさんに喋っていたら、3つの場合は3分割でdp[i][j][k]のようなことをすればよいのでは？と言われました。確かにそうです。実装もゆきのんさんに任せることにしました。i+j+kが風船の個数の総和になるので、dp[i][j]でよく、これでちゃんと時間内に終了するdpが得られます。

E問題

D問題の実装を横から見つつ、haさんと一緒にE問題を読みましたが、題意を頭に入れたあたりでD問題の実装がひとまず完成していたので、考察を放り投げてデバッグの様子を眺めたり口出ししていました。

E問題に対する自分の直感として、車道で連結成分に分けてそれぞれで拡張dijkstraするというものがありました。これをha15さんに話しつつ、連結成分を何度も行き来するようなケースがあるかもしれないと考えていたところ、ある程度以上タクシーを乗り降りする場合はできるだけ回数を減らすように動いていいのではないか、ということをha15さんが言い出しました。正しそうです。

適当なしきい値を定めて、タクシーを待つ回数がそれ未満の場合は拡張dijkstraで、以上の場合はタクシーを待つ回数と経過時間をペアで持ってdijkstraをします。しきい値としては、距離が最大で2\times 10^{10}くらいになるので、これを待ち時間が越えるくらいで定めればよさそうです。実装をha15さんに任せて、F問題に進みました。

F問題（解けず）

Dを通したゆきのんさんとF問題を読みます。作ったグラフの各辺がありうる最大マッチングのうちどれかに含まれる、という言い換えは、すぐ元の問題に戻ってきてあまり筋がよくありません。見切りをつけるまでに、すでにかなり時間を使っていました。

1つ最大マッチングを固定して、それに含まれない辺を使おうとしたときどのようにして新たな最大マッチングを作成するかを考えることにしました。増加道のようなものを考えると、今指定した辺を含み、最大マッチングに含まれる辺と含まれない辺を交互に通るような閉路が存在すればよいです。

最大マッチングで結ばれた相手の頂点から、ほかに（最大マッチングに含まれない）辺が出ている場合、自分も1本以上辺を持つ必要があります。実はこの条件だけで、サンプルで新しく辺を張る頂点は検出しきれます。なので、それらをうまく繋ごうとしましたが、2つ目のサンプルの繋ぎ方は1通りしかないようで、これがなぜなのかがわかりませんでした。また、2つ目のサンプルにさらに2 1と4 3という辺を足すことで、先ほど述べた条件を満たさない頂点からも辺を張る必要があるケースが作れてしまいました。

確か上の考察の途中あたりで、E問題が書きあがっていました。サンプルを試したところ出力が合っていたので、提出してもらいましたが、WA。急いでコードを共有してもらって眺めていると、コスト計算にミスを見つけたので、そこを修正してもらって再度投げなおすとACでした。サンプルに、そう何回もタクシーを待つケースが含まれていないのは考えてみれば当然のことなので、焦って投げる前にチェックさせてもらえばよかったです……。

F問題の考察に戻ります。ここで僕は二辺連結成分分解を考えました。橋となるような辺ができないようにうまく辺を張れればよいと思ったのです。二辺連結成分分解した後の木の葉たちを繋いでループを作ります。そのようなことが可能かはちょっと怪しいですが、可能ならば木dpの要領で作れるはずでした。残り時間も10分くらいになったので、とりあえず書き始めてはみたものの、全然書きあがらずコンテストが終了してしまいました。

コンテスト後

購買でお菓子を大量に買い込んでおいたのですが、まったく手を付けませんでした。封が開いていないものはチームメイトで分け、そうでないものはその場で食べていたら、他のチームが続々と帰って行きました。僕個人としてもあまり元気がなかったので、チームでの打ち上げはしないことにして、解散しました。

振り返り

結果はABCDEの5完で、全体8位、学内2位でした。

icpc.iisf.or.jp

まさか自分が学内1位から転落するとは、と愕然としています。序盤10分くらい問題文が読めなかったのに余裕ぶっこいていたのは明らかによくありませんでしたし、DもEもわかってみればあまりにも明らかな解法なので、見た瞬間解けるべきでした。

Dとsolved数の逆転が起きていたCを僕が解いたのは良かったです。また、戦略としてみれば、DとEをチームメイトに割り振ってF問題の考察に専念しようとしたのは、いかにもチーム戦という感じがして良いはずでした。

しかしこの戦略は僕がF問題を解けることが前提になっており、実際は2時間くらい考えていたのに解けなかったので、台無しになってしまいました。上に書いた考察で正しく進めているのは増加道の下りまでで、このとき辺を向きづけてループが必ず増加道となるようにするのが正しい道筋だったようです。この場合二辺連結成分分解ではなく強連結成分分解が出てくるそうです。

最近まともな精進をしていないので、横浜までにはまたAOJ-ICPC埋めを進めておきたいです。

週記（2021/10/25-2021/10/31）

10/25(月)

先週の週記を投稿してからの話。模擬国内予選の参加記を書き始め、コンテストの半分くらいまで書いたところで切り上げた。その後大学生協で本を注文した。今月は全然本を買っていなかったので、まだ手に入れていない新刊が山ほどあった。また、これまではリアル本屋に行くことを考えて本の予約をほとんどしてこなかったが、最近全然リアル本屋に行かなくなったことを鑑みて、11月発売の本も数冊予約してみた。

せっかく参加記を書くのを途中で切り上げたのに、結局昼前になってしまった。インターンの定例会に寝坊しないことを願って午前10時半、就寝。

CF div.1はそもそも定例会と被っているため不参加。午後3時半すぎに起床し、定例会直前に進捗報告のスライドを捻り出した。先週後半に帰省していた影響もあって、進捗はほぼなかった。

定例会後のKaggleチームミーティングで、参加しているコンテストがそろそろ終了しそうであることを知った。これまで1か月間、びっくりするほど何もしなかった。おそらくモチベーションの問題だろう。せっかくチームを組んでもらったのに申し訳ないという思いが強い。経験者のコンテスト中の動きを知れたのはよかった。かなり序盤に複雑な実験コードが完成しており、そのあたりのフットワークの軽さが印象的だった。

ゲームインさんしょう富山駅前店が今月末で閉店するというツイートが流れてきた。高校時代、学校から駅まで向かう道の途中にあるこのゲーセンにはかなり頻繁に通った。チュウニズムやSDVXの30日連続ログイン称号を手に入れたのもここだった。先週の帰省中に行ったのが最後になる。そうと知らなかったとは言え、閉店直前に行けたのはよかった。

今年の4月上旬に「転生したら皇帝でした」というなろうを読んだ。その読了ツイートに、TOブックスというラノベ出版元のアカウントからいいねが来た。さてはと思ってそのアカウントのツイートを見ると、案の定この作品の書籍化が決定していた。懐かしくなり、改めて即位式のあたりを読み返してみたが、やはり面白い。

https://ncode.syosetu.com/n6066gi/

信じられないくらい眠く、フラフラと布団に吸い寄せられ、そのまま寝てしまった。午後8時だった。

10/26(火)

午前2時起床。この時間から起きてしまうと、今日の夕方から予定されている1on1の前に眠気が限界を迎えてしまう可能性があるので、二度寝したい。そう思いつつ、なんとなくスマホを触ってしまい、結局そのまま朝まで起きていた。

なろうを1作読了。「この世界のヤベー奴らは大体みんな俺の弟子」。黒留ハガネさんの手になる中編で、師匠モノ。僕がこれまで読んできた黒留ハガネさんの作品はどれも非常に面白かったし、また師匠モノという設定も大好物だったので、読み始める前からかなり期待していた。実際面白く、途中で止められなくなったという訳。

https://ncode.syosetu.com/n2245gi/

10/18(月)の日記で、caburiさんのアカウントが乗っ取られたことについて言及していた。今日、本人がツイートされていて知ったが、もう@artclassifiiedという別のユーザーIDに変わって復活しているらしい。微力ながら報告しておいたが、さてどうなるだろうか……。

フォローしていた絵師のアカウントが乗っ取られたことを知った。そのアカウントは現在削除されていて、こちらからフォローを解除したりはできない。絵師のサブアカウントのツイートについていたリプライ曰く、乗っ取った直後は通報されるのを避けてアカウントを削除し、復活期限の30日ギリギリまで待つのではないだろうかとのこと。

週記（2021/10/18-2021/10/24） - kotatsugameの日記

2021/10/31追記：さらに別のユーザーIDに変わっていたので、追跡できるページを貼っておく。

idtwi.com

今日の5限の資料や課題がすでにClassroomに投稿されていたので、終わらせておくことにした。今日は、Pythonとしては関数（特に再帰関数）の紹介、アルゴリズム面ではバブルソートとクイックソートが紹介された。既知の話しか書いていないので斜め読みしたが、それでもかなり駆け足の資料という印象である。課題は100万要素の配列の中央値を求めよというもの。資料に載っていたクイックソートの関数を弄って選択アルゴリズムを書くと40秒近くかかったが、Python標準のソート関数を使えば爆速で求まる。どちらが想定されていたのだろう、来週の資料が楽しみである。

試しに資料のクイックソートをそのまま使ってソートしてみたら、なんと45分もかかってしまった。選択アルゴリズムで落ちるlogも、100万要素ともなるとこんなに違いが出るということか。あるいはデータが偏っていてよくないピボットばかり選んでいた可能性がある。実装が悪く、特に全部同じ値の配列をソートするとO(N^2)になってしまうようで、配列の要素はかなり狭い範囲に分布していたから、途中からそういう状態になっていたとも考えられる。

ちなみに、同じアルゴリズムをC++で実装したところ、クイックソート6秒、選択アルゴリズム2秒だった。

Google Colabでクイックソートを回している間、YouTubeで動画を見ていた。「絶対に笑わない男」という動画シリーズに出会い、2本ほど見た。人が笑いを我慢している様子を見るのは最高に面白い。

絶対に笑わない男 - YouTube

昨日の続きから模擬国内予選の参加記を書き上げ、投稿した。D問題の線形時間の解法がわからず、とりあえず存在だけ言及しておいたが、いつの間にか公式解説がアップロードされていて、それを見て理解した。

kotatsugame.hatenablog.com

FIFから何かの景品が届いた。おそらく2021/10/10に行われたHACK TO THE FUTURE for Youth+のものだろう。

夕方、1on1。眠気は十分耐えられる程度だった。今週も機械学習の実験を繰り返すことになりそう。学習の途中経過を見て実験を打ち切る場合、Ctrl-Cを送信する方法しか知らなかったが、これだと終了後のログ出力なども行われないという欠点がある。プログラム側の機能として、何らかの操作に対応して学習を打ち切る必要があった。これに関して、特定の名前のファイルが存在するかをチェックして停止するか続行するかを分岐するという方法を、メンターさんから教えていただいた。大変興味深い。flockと似たような発想だろうか？

「C言語関数辞典」というページを昔よく参照していて、ブックマークにもいくつか残っていた。今日ふと開いてみると、ドメインの有効期限が切れてしまったのか、謎の広告ページに飛ばされてしまってかなりびっくりした。

急激に眠くなって布団に倒れこんだが、TLを見て模擬国内予選の問題がAOJに追加されたことを知り、最後の力を振り絞って起き、パソコンの前に戻ってきた。手元に残してあったコードを提出してみると、どれもちゃんと通った。DやFは計算量的にちょっと心配していたが、ICPCのマルチテストケースは制約ギリギリを攻めてこないため、結構余裕があった。さらに僕が解いていないAとCも通しておいた。Cは枝刈りdfsが楽という話を知っていたものの、一応bitDPで書いてみた。遷移を書くのは場合分けなどではどうにもならず、結局遷移を生成するための再帰関数を書くことになった。

また布団に倒れこみ、午後9時就寝。

10/27(水)

午前4時半起床。せっかくなのでインターンの実験コードを少し手直しし、また走らせておく。

今日は昼から院試ゼミのメンバーで遊ぶ予定があって、今から二度寝するにしても微妙な時間。ついついスマホに手が伸びて、ハーメルンを読み始めてしまった。面白かったので最新話まで追いつこうと思って頑張って読んでいた結果、昼からの予定の直前になってようやく読了。そこからシャワーを浴びたりの準備をして青葉山に向かう必要があるので、大遅刻である。

読んだのは「天地神明の真祖龍」。モンハン二次創作で、主人公は祖龍ミラルーツに転生する。といっても僕のモンハン経験は3rdのみなので、この作品に登場する古龍たちの中ではアルバトリオンやアマツマガツチ、ジエン・モーランしかビジュアルが想像できない。適宜画像を検索してイメージを補いつつ読んでいた。内容は非常に面白かった。主人公最強なのも良いし、正体を隠して街に潜入する展開も良い。

syosetu.org

そこからシャワーを浴び、学食で昼食を摂ってから青葉山に向かったので、到着したのは午後1時半。昼からの予定は午後0時10分集合だったので、実に80分遅れであった。それから午後6時まで4人でボードゲームをして、山の学食で夕食を摂って帰宅。

今日はディクシット、ドミニオン、スカルという3種類のボードゲームをこの順にプレイした。それぞれちょっとした感想を書いておく。

ディクシットについて。謎の絵が描かれたカードを手札にして、順番にお題を発表し、それに沿う（こじつけられる）ような絵のカードを場に出す。お題の発表者が出したカードを当てればよいが、このとき、当てた人数が正整数の範囲で小さければ小さいほど高く評価される、というゲーム。僕が出したお題はかなりいい感じに票がばらけ、そのうえ1人のみが正解してくれたので、だいぶ上手くいっていた。しかし自分の印象としては、お題として曖昧な語彙を選んだ結果、みんなそれっぽいカードを出せて、たまたま1人だけ僕のカードを指していたというように感じられたので、運が良かっただけに思える。

ドミニオンについて。カードの効果でカードを集め、その場でデッキを作るカードゲーム。最終的には勝利点というジャンルのカードをどれだけ持っているかで勝敗がつくが、勝利点のカードはカードを集めたりデッキを整えたりするのには使えないため、プレイ中は邪魔者になる。僕はデッキを作るのに夢中になっていた結果勝利点をほとんど確保できず、最下位となってしまった。

スカルについて。各プレイヤーは3枚の花カードと1枚のドクロカードを持ち、順番にターンが回っていく。自分のターンでは、自分の前にカードを1枚選んで伏せるか、「チャレンジ」を行うことができる。チャレンジでは適当な正整数を宣言し、自分の前のカードすべてと他プレイヤーのカードのいくつかを、合計枚数が宣言した正整数に一致するように（新しいものから）めくる。めくった中にドクロカードがなければ勝ち、というゲーム。ただしチャレンジ宣言は、別のプレイヤーからより大きな正整数によって上書きされることがある。非常に面白かった。1ゲームがすぐ終わるし、それっぽい駆け引きも行える。僕も駆け引きっぽいことをしていたつもりだったが、実際には指運とクソ度胸、またビギナーズラックによって、1戦目は無傷での勝利に成功した。代わりに2戦目は微妙だった。場にある全てのカードをめくるような宣言をして成功した瞬間や、ブラフで相手に自分のドクロカードをめくらせた瞬間は非常に気持ちよかった。

帰宅してからしばらくYouTubeを見ていたつもりが、いつの間にか布団に移動して、あっという間に寝ていたらしい。おそらく午後8時だった。

10/28(木)

午前5時半起床。

僕が寝ている間にTOKIやCodeChefでコンテストが行われていたらしい。今週平日はこんな感じで、朝に寄った生活リズムで過ごすことになりそう。平日のコンテストには出られない代わり、週末のAGCはいい感じに眠気なく臨めるのではないだろうか。

今日もハーメルンを読んでいたら朝だったのが昼前になってしまった。午前10時、購買が開店したのを見計らって大学に行き、昼食を摂りつつ注文していた本を受け取った。今週月曜日の部分で書いていたものだ。

4年後期の時間割をツイートした。ずいぶん前に確定していたのにツイートするのをすっかり忘れていた。このリプライツリーとも長い付き合いになったものだ。

昼過ぎから1on1。火曜日の時点で生活リズムが朝に寄っていることが分かっていたので、普段通り夕方に行おうとすると寝ている可能性が否めず、この時間に入れてもらった。今日は火曜日から断続的に回していた実験の結果を報告した。Lossの値だけ見ても下がっていることはわかっていたが、改めてビジュアライズしてみると思った以上に学習できているようでびっくり。いくつか改善点を議論して、また実験を回していくことになった。

1on1が終わってから外出し、ゲーセンに向かった。今日は新曲埋めと、11/04に迫った大型アップデート前に消えてしまうもろもろの整理。8月の時点で99枚あった「もう1曲遊べるチケット」だが、無心でプレイを続けた結果ついに使い切れた。つまり、少なくとも99回チュウニズムをプレイしたということで……まあ、ほぼ3か月と考えれば多くもないか。実際は7曲プレイチケットも使ったりしているので、もっと多い。

「もう1曲遊べるチケット」は、なんとなくもったいない気がして上限ギリギリまで貯めているので、非常にまずい。

週記（2021/08/02-2021/08/08） - kotatsugameの日記

今日の進捗としては、これまたアップデートで消えてしまう「Memories of 〇〇」系マップの称号を全部集めたのと、「《運命》 〜 Ray of Hope」で99AJを出したこと。アップデートで削除される曲に関連する称号も、1人で手に入るものをだいたい集めておいた。残りは2つで、どちらもMASTER譜面をSPEED SONICでAJすることが求められる。

SPEED SONICとは、チュウニズムで譜面が流れてくる速度を限界まで速めた状態の名称だ。以下にYouTubeに上がっているプレイ動画を添付するが、譜面がまともに見えないので、運指の暗記が求められる。

www.youtube.com

この状態でAJすることが称号獲得の条件になっているのは「シュガーソングとビターステップ」「Sparkling Daydream」で、前者は普通にプレイしてもAJが安定しないため、とりあえず後者を詰めてみることにした（のが昨日くらいのことだった）。譜面を家で覚えてきたつもりが全然できない。とりあえず通常速度でプレイして、速度を速めてプレイして……を繰り返し、譜面を覚えるのに専念した。15速くらいでプレイしていたら普段の10速で精度が取れなくなったので、10速＋フィールドウォールで譜面の見えなさを再現しようともした。結局先駆者のアドバイスを受けて、17速でプレイを繰り返すことにした。17速だと、流れてくる譜面の判定と認識がだいたい同時になって、見えないことには変わりないが、間違えた場合本来どういう譜面だったかはわかるという寸法らしい。17速でSSSを出し、SPEED SONICで3k弱を出して、今日は終了。

帰り際、今日のマップ進行でかなり増えたゲーム内通貨でショウニスタチュウを購入したところ、所持数が3桁に突入した。チケット系が99枚で制限される中、これは3桁まで行けるらしい。びっくりした。

帰宅してから残りの「Memories of 〇〇」系マップをどう進めるか考えていた。TiamaT:F minorのゲージ10本を達成できる目途が立たない。今日試しにプレイしてみたら、赤以下が150を超えてしまったので、勇気のしるしで完走できるかどうか不安がある。

寝ている間に回す実験コードをセットして、午前2時半就寝。

10/29(金)

午前9時半起床。ずっと布団でウネウネしていたが、正午あたりに身を起こしてゴミを出した。これまでの生活の経験から、ゴミ回収は結構遅めの時間に行われることが分かっており、今から出しても間に合う。

以下のブログ記事を読んだ。内容もそうだが、合間合間に挟まれる画像も含めてオモコロっぽさがある。内容も負けず劣らず良かった。中盤は理解を放棄しそうになったけど、オチがツボに入ってしばらく笑っていた。

umector.hatenablog.jp

大学に行って昼食と散髪を済ませ、サークルの時間になるまで談話室でラノベを読んでいた。

チュウニズムのアップデート情報が連日追加され続けている。今日公開された情報で、判定タイミング音が追加されることがわかった。これを使うと、ATTACK以下の判定時に音を鳴らせるようになる。アップデートで、ATTACK以下の判定時にスキル音が鳴るという理由からAJ狙いの時に愛用していたスキル「パニッシュメント」が消えると知って絶望していたが、この機能で（強制終了は別として）同様のことが行えるため、安心。

談話室がある棟の2階に、仙台に旅行に来ていたなぎの（@makonagix）さんがいるらしかったので、連絡を取ってエンカした。パチスロの設定に関する興味深い話や、計算機数学に絡めた話題があって、非常に良い体験だった。

サークルの時間に少し遅れて教室にたどり着き、バチャに参加。今日のAOJ-ICPC500点枠は「街を駆ける道」という問題で、一度解いたことがあったので問題文は斜め読みしたのだが、見事に誤読してしまった。結ぶべき街はABそれぞれ1組ずつであるということに気づかず、すべての街を連結にしようとしていた。この状態で昔解いたときの考察を復元しようとした結果、「AとBのどちらかは直線で結ばれる」が「AとBのどちらかは最小全域木で結ばれる」になってしまい、当然答えが合わずに苦しんでいた。

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2334

学食でホスフィンと合流し、夕食を摂ってゲーセンへ。金曜夜ということでチュウニズムが8台全部埋まっていたりしたが、少し待って空きができ、マッチングができるようになった。1時間くらいプレイしてフルチェインを2つ出した後は自分のことに集中。昨日から引き続き「Memories of 〇〇」系マップを進めようとしたが、インド人を無の境地AJしても10マス届かなかったり、TiamaT:F minorを勇気のしるし完走したのにギリギリ10マス届かなかったりで、今日はちっとも進められなかった。

残り時間は今日もSPEED SONICでSparkling Daydreamを詰めていた。昨日家で動画を見て運指を組んだり覚えたりしてきたのでなかなか調子がよく、もはや噛み合い待ちであった。が、最後150ノーツくらいまでAJ通過し、緊張で運指が飛んだ回などあって、閉店まで粘ったものの結局この日はAJを出せなかった。せっかく譜面を覚えたので、忘れないうちに、明日は朝からゲーセンに行きたい。運指は↓これ。手の位置を動かさなくてよいのが楽だった。

f:id:kotatsugame:20211102012047p:plain
51-52小節

yukicoderで1問テスターを行った。詳細は当然書けないが、面白い問題だと思った、くらいは言っていいだろう。

「ワールド・ティーチャー」15巻を読了。いよいよクライマックス、なのに前巻の内容を覚えておらず、人名などもあやふやなまま読んでいた。この巻は主人公の活躍がそれほどでもなかったが、次巻すごいことをやってくれるんじゃないかという引きで終わっている。何事もなければ、その次巻が最終巻になるらしい。

布団に入った後もしばらくYouTubeで動画を見ていた。「絶対に笑わない男」という動画シリーズを火曜日に見つけて、それからもしばしば見ている。

ここから20秒くらいが本当に好き。左下のワイプに写っている「鈴木さん」が笑いをこらえきれないシーン。映っている画面自体は右下の人のものであるため、このとき鈴木さんが見て笑ってしまった画面がどのようなものだったかは定かでないが、なんとなく想像はつく。一度持ち直したはずなのに、石を掲げて近づいてくるキャラクターを見てだろうか、とんでもない顔面になるのがたまらない。またこの30秒ほど後でキャラクターがじりじり立ち上がっている様子は、画面にも映るのでより直接的な面白さがある。

午前5時就寝。

10/30(土)

午前10時半起床。食事してすぐゲーセンに向かう。今日は初めからSPEED SONICのAJ詰めを頑張る。

ラストのトリルに癖がついた状態でそこまでAJ通過してしまい、案の定そこでATTACKを出して開いた口が塞がらなかった。

と、そんなことをやっていたら、次のクレで出た。称号「邪王真眼の使い手」獲得である。久しぶりにチュウニズムを頑張り、成果も得られてうれしい。

MASTERのSPEED SONIC AJには、曲を問わない称号「邪気眼」もあって、それも同時に獲得できている。同様のものが1速AJにもあるので、簡単な譜面で出してみたが、以前すでに出して獲得していたことをすっかり忘れていた。

その他は、TiamaT:F minorでコンボエクステンド・フォーチュンを使い10マス達成したり、トライしている最中にスコア6900が出たり、久しぶりにプレイヤーレベルが100に到達したりした。今日は夕方に生協の弁当が届くので、それに間に合うようにゲーセンを離脱。本を買い、ドーナツを食べて帰宅した。

弁当は午後3時半すぎに届いた。11月発売のラノベがいくつも予約できるようになっていたので、生協で予約した後、かなり眠くなってきたので午後5時からお昼寝。

午後8時半起床。ABC225に出る。

UNICORN Programming Contest 2021(AtCoder Beginner Contest 225) - AtCoder

6完79位。Gが五億人に通されていて非常につらい。

AはRakuですべての順列を生成しようとしたが、リストのリストを持った状態で重複を省こうとしたら一致判定がされず、しばらく試行錯誤して文字列に直す方法に至るまでしばらく時間がかかった。重複を省く際は2つのリストを===演算子を使って比較することになるが、このときobjectとしての一致を見るため中身の比較はされないらしい。BはPerlで書いた。CからはC++。Cの問題設定は、S8PCで2回出題されたCalendarという問題に一致している。Dはかなり難しく感じられたが、双方向連結リストっぽく持てば良い。Eは偏角が区間になるので、区間スケジューリングを行う。

A - Calendar

Fはdpで、最近模擬国内予選のFの解説でわざわざ「後ろからdpする」と指定してあったことを思い出し（この問題は実際は前からdpしても通るが）、その方針で考えてみた。各文字列を1度しか使えないので、dpを更新する文字列を使う順番を考える必要がある。これについてはS+T\lt T+Sを比較関数にして降順ソートすればよい。この比較関数が比較関数としてvalidであることは典型。また比較関数の形から、ある解を構成する文字列たちのうち、先頭からこの順番に並んでいないものがあれば、隣接文字列のswapを繰り返すことで辞書順で小さい文字列に置きなおせる。よって、今得られた順番でdpを更新していけば正しい解が得られる。シンプルな問題でありつつも2つの典型が組み合わさっていて面白かった。

Gは解けなかった。盤面を45度回転すると、斜めの条件が縦横の条件に言い換えられる。上下のどちらかと左右のどちらかが塗られているなら、そのマスはコストを支払わずに塗れるので、結局最後に塗られた形は長方形の集合になる。この観察をもとに、すべての長方形領域に対して分割を試し、最適な塗り方を求めるdpを書いた。計算量はO(H^2W^2(H+W))だが定数倍がそこそこ小さいと思ったので、一番内側のループでアクセスするdp配列がメモリ上で連続している領域になるよう添え字を入れ変えてみたり、いくつかpragmaを指定した上で投げたが、全然通らなかった。

コードゴルフ。A問題は1、3、6を埋め込んだコードが最短だった。よくよく観察すると、2進数に直せば1、11、110である。つまり110を3-(文字の種類数)だけ右シフトすれば正しい答えが得られるようだ。このことをRakuで実装したコードが最短になっている。BはRaku。CはOctaveで書いておいた。

2021/11/01追記：A問題は1から(文字の種類数)までの総和でも答えが求まるらしい。これを使ったコードは+1Bになっていた。

途中で切り上げて、午後11時半からCF #752 div.1。

Dashboard - Codeforces Round #752 (Div. 1) - Codeforces

Aは、まず先頭の要素は偶数でない必要があって、2番目の要素は3または2で割り切れない必要があって……と考えていくと、i番目の要素が{\rm LCM}(2,3,\dots,i+1)で割り切れなければよいとわかる。念のためこの値を前計算しておいた。あまりに大きくなっても困るので、109を超えたタイミングで残りの要素はすべてそれで埋めておいた。

Bは場合分け。y=pn+r=p(qx+r)+rとおいてみると、y\lt xのときはr=yを考えてn=x+yとするのが条件を満たす。それ以外は、例えばp=q=1を考えるとr=\frac{y-x}2、n=\frac{x+y}2が条件を満たしそう。しかし、サンプルで正しく構築できたのを見て勢い込んで提出したところ、WA。冷静になるとx\le rになってしまう場合があった。これを修正するため、q\gt 1も許すことにして0\le r=\frac{y-qx}2\lt xとなるようにしてみた。n=qx+r=\frac{qx+y}2であり、0\lt px\le yからn\le y\lt 2nとなり、y\bmod{n}=y-n=\frac{y-qx}2=rが満たされる。

Cは後ろから全探索。商の種類数が少ないので、同じ商に対して場合の数をまとめて持つことによって高速に計算できる。商をまとめるところで毎回vectorをソートしてしまったが、1secを切る十分な速さで通った。実はソートされた商たちで特定の値を割るとこれまた降順ソートされた値になるので、並べ替える必要はなかったらしい。Dは2^k\gt nなら答えはn。残りの場所について、普通にdpを書くと時間がかかってしょうがないが、同じ値の箇所がたくさんあったので、その階差を埋め込めるんじゃないかと思ってやってみた。結果1e6Bくらいのコードが完成したのだが、CFは65536B制限で絶望的。dpの遷移を勘で絞ると計算時間を削減できたため、2回ほど提出したが、どちらもWAだった。

45位で2998→2990(-8)。厳しすぎる。D問題が全然通されなかった結果崖ができており、BのWAがなければもうちょっと順位は上だったが、それでも+2には届かなかったのだろう。Legendはいまだ遠い。

ABCのコードゴルフの続き。D問題はRubyで縮めていたが、AWKにすると40B近く縮んだ。EはCFの間にRubyの分数を使ったコードが提出されており、短すぎてどうしようもない。座標を(+1,+1)することでゼロ除算を回避できるのでは、と思ったが、偏角がずれるらしくそもそも答えが合わなかった。FもRubyで負けてしまったので、Vimで書いて無理やり縮めた。

布団にもぐってYouTubeをしばらく視聴し、午前7時就寝。

10/31(日)

午後0時半起床。

KUPCに出る。コンテストの難易度が高いことが予想されるため、チームを組もうと思っていた。以前からTLを眺めて数人目星を付けており、そのうち直前になってもチームを組まれていないようだったりーふ（@leaf_1415）さんに突撃して無事チームを組んでもらった。

京都大学プログラミングコンテスト 2021 - AtCoder

結果はABCDEFGIKMの3100点で7位。最後にMが通ったのが159分のことで、その前後しばらくは1位だったのに、そこから何も通せず人生が終了した。

Aはりーふさん。僕はBから読んで、焦ってよく確認せず実装した挙句テスト出力を見てミスに気付くことを2回繰り返した後、公式解説の再帰的に構築する方法っぽいものを思いついて通した。りーふさんがCを読み始めていたため、Dに移動。Dは実験コードを書くとすぐgrundy数の規則性が見えて、手でもやってみた感じ正しそうだったので、証明はほとんどせずに通し、すぐE問題に移った。

E問題は、青色の辺(u,v)に割り当てられた重みが、赤色の辺からなる木のu-vパス上のどの辺よりも重ければよい。つまり、重みの小さい辺の番号から大きい辺の番号に辺を張ったDAGのトポロジカルソートを求め、特に順列のinverseが辞書順最小になるように構成できればよさそう。順列のinverseが辞書順最小という条件は、辺番号が小さいものをできるだけ早く使いたい、つまり逆に辺番号が大きいものをできるだけ遅く使えばよいということで、（DAGの辺を逆向きにして）後ろから貪欲すれば求まる。さて、このままではDAGの辺がO(NM)本程度になってしまうが、ここで赤色の辺は必ず入次数がゼロで、逆に青色の辺は出次数がゼロになることに注意すると、後ろから貪欲するとき青色の辺は常に自由に使える状態になっていることがわかる。それらのうち番号が大きなものから使われていくのだから、赤色の辺の番号から出る辺のうち最も小さい番号に向かうものだけ辺を張っておけばよいことになる。赤色の辺からなる木をdfsして、関係する青色の辺の番号たちをsetで管理し、マージテクを使うことで求めることができる。この問題はFAだった。

りーふさんがFに進んでいたため、Gを読んだ。2回開く箱を少なくしたい感じがする。ここで、当たり前のことだが、箱に入っているボールの行き先をもとにグラフを作るとfunctional graphになることに気づいた。これをもとにループごとに分解して考えてみると、自分の箱に入るべきボールが最初入っていた箱、つまりループにおいて自分の1つ隣の箱の開くタイミングと自分が開くタイミングの兼ね合いでコストが決定できることに気づいた。つまり、直前の箱がいつ開かれたかを持ってループ1周ぶんdpすればよい。ループの最初の箱がいつ開かれたかはdpの別の次元で保存しておけば、ループを閉じる部分は最後に処理できる。

Hに進んで30分ほど格闘していたが、全然光明が見えないためIに進んだ。IはHLDすることを考えると、セグメント木で区間加算し、負になった要素があるか確認できれば良い。負の要素を数えて云々、ということを考えていたが、普通にセグメント木全体のminが負であるかを見るだけでよかった。りーふさんのFとほとんど同じ時間に通った。

ここから、順位表を頼りに進むのが難しくなってくる。とりあえず全部目を通して、Kを考えてみることにした。別の要素の決定を阻害しないような遷移をまとめるようなdfsを思いつき、これでヤバいケースが想像できなかったため、りーふさんに確認を取って投げてみると爆速で通ってびっくりした。

次にMに進んだ。Mはsolvedがそこそこいて、後ろから解く異常者たちが通しているのだとばかり思っていたが、よく見るとそうでもなかったのだ。考えてみると、「これまで作れた式の数、式の値の総和、掛け算のみでつながった項の総和、まだ演算子で区切られていない数の総和」を持つとdpが可能であるようだ。遷移は、数字を1文字追加するか、演算子と数字を組みにして2文字追加するか。遷移を行列で表して行列累乗するとすぐサンプルが合って、そのまま通ってくれた。

残り時間、僕はL問題を、りーふさんはJ問題を考えていたが、双方通せず終了した。りーふさんが担当してくれた問題たちは順位表を見ても結構通せていないチームがあって、実際僕はまだC問題すら解けていないため、そこを通してもらえて非常に助かった。解法の共有や相談は行わなかったが、こうやって問題を分担できただけでもチーム戦を組んだ甲斐があったと感じられた。

その後、KUPCのコードゴルフをいくつか行った。A問題はRakuが強い。B問題はOctaveで書いた。文字列の添え字として行列を使うと、結果も2次元の文字列になってくれるのが便利。Cを飛ばして、DはAWKが短くなった。残りは手付かず。

ふぁぼん氏が言及していたのを見て、カクヨムで「おいしいピザトーストの作り方」という日常の謎短編を読んだ。氏も触れているが、キッチンで不自然な状態を目にし、どのようにしてその状態が作り出されたかを推理するというのは、米澤穂信さんの小市民シリーズに収録された「おいしいココアの作り方」という短編とまったく同じである。僕はその短編が結構好きで、カクヨムのほうも楽しく読めた。

おいしいピザトーストの作り方（十一） - カクヨム

午後9時からAGC055に出た。

AtCoder Grand Contest 055 - AtCoder

A問題はもはや恒例の天才パズル。天才のフリをし損ねた瞬間ゲームオーバーだ。最初に、ABCそれぞれの文字を先頭から順に組にしていき、6通りの順番で場合分けして別の文字列に組み分けることを考えた。3!=6という意味の制約なんだなあと興奮。あまりの興奮に、よく確かめずサンプル2が合っていないことに気づかず提出してしまった。WAが出て心臓が止まりそうになった。しかし3!=6という意味は間違っていないはずだ。そのあと20分くらい考えて、N文字ずつに分割するとうまくいきそうだということを以下のような計算をもとに確かめ、提出してACを得た。証明は途中だったが、おそらくもうちょっと計算してAとBを同時に使いきれることを確認した後、ホールの結婚定理を使えば言えるのだろう。

B問題は、まず文字列の隣接項の差分を取っていろいろ考えてみた。a,1,1,bという列をa+1,1,1,b-1に置き換えられるらしい。これを使って先頭からマッチさせていくことを考えると、1が2つ連続している場所を探して、それを動かして特定の位置の値を弄ることはできる。では、所望の値をセットし終わった後は？動かしてきた1,1という部分列は再利用できるのか？……このことは隣接項の差分を取った状態では何とも言えなかったため、元の文字列に戻って考えてみた。1,1を動かすことは、ABCやBCAやCABを動かすことと同じである。XABCから適当に置きなおすことで(ABC or BCA or CAB)X、その後ABCXに変化させることができるので、この操作を考えていたのだろう。こうやって文字列で見てみれば、3文字が一塊になって文字列中を自由に動いているとも考えられる。それで特定の位置にたどり着き、さらに何度か置き換えて所望の文字をセットした後、残った2文字はまた自由に動けるだろうか、ということが知りたい。これは明らかに不可能である。例えばAABCがあって、Aは所望の文字ではないから代わりにBCAAと置きなおしたとすれば、一塊になっていた3文字には異なる文字との入れ替えが発生し、残りCAAのように必ず2文字が重複してしまって動かせない。つまり、このような3文字は1か所の文字を交換するのにしか使えず、使った後はその場に特定の順序でとどまることが分かった。ここまでわかれば、あとは操作をdequeでシミュレートできて、AC。

C問題は非常に難しかった。数列の値は1種類か2種類の場合しか考えなくてよく、このうち1種類の場合は別に計算できる。つまり、ある3\le k\le Mであって数列がk-1とkのみで構成される場合を考えればよい。k-1という要素が必ずLISに含まれる一方、kという要素は基本LISに含まれないが、2つ連続していれば含めることもできる。k-1の個数をa、2つ連続しているkの個数をbと置くと、a\le k\le a+bなるkを当てはめることができそう。とりあえずO(N^3)のdpを書き、\max(0,\min(a+b,M)-\max(a,3)+1)を掛けて足し合わせたら答えが合った。さらに、M\gt 2かつa\le Mの場合だけ計算することにすれば、0とmaxを取る必要もなくなった。2\lt M\le N-1よりa+b\ge 2となるらしい。これで寄与が分解できたので、a+bをキーに持つdpとaをキーに持つdpをそれぞれ書けばO(N^2)で求まりそうだったものの、実装してみたところ答えが合わなかった。どうやらa+bをキーに持つほうでa\gt Mの場合を含めてしまっているのが問題らしい。ここで、a\gt Mの場合\min(a+b,M)=Mであることに気づいた。よって、最後に各a\gt Mについてa+bの値を任意とした場合の数をcombinationで表し、Mを掛けて答えから引いてみたところ、見事にサンプルが合った。祈るように提出し、AC。1時間以上粘って通せたので非常に気分がよかった。

残り時間はふわふわした気持ちでDを読んでいたが、そもそも判定問題すらまともに解けなかった。結果は37位、パフォーマンス3080でレートは2821→2850(+29)。当然最高値である。

コードゴルフ。Aは適当にRubyで書いてある。Bは解説の方針が天才すぎた。差分を取るのは典型操作だが、このようにインデックスを引いてみるのも見覚えがあって、今回はそちらが正解だったらしい。その方針で、これまたRubyで書いてある。

夜中はずっと日記を書いていた。普段寝る前に日記を書いているが、今週は倒れこむように眠ることが多く、なんと一週間まるまる溜めてしまったようだ。もう全然書き終わらないので、途中であきらめて寝た。午前9時半だった。金土日の分は11/01(月)に書いている。

ICPC模擬国内予選 2021 参加記

2021/10/24に開催された模擬国内予選にチームAobayama_dropoutで参加しました。今年はメンバーに変更があり、碧黴さんが一足先に引退されて新たにha15さんが加わりました。つまり、ゆきのんさん・ha15さん・僕です。碧黴さんはコーチとして関わってくださいます。

jag-icpc.org

昨年の参加記を読むと、どうやら当時は部室にチームで集まって参加したようですが、今年は完全にオンラインでした。ツールはSlackとHackMDを用意したものの、僕が一人で考察を抱え込んでしまい、HackMDのほうはあまり活用できませんでした。国内予選本番では集まりたいと思っていますが、どうなるんでしょう。今年のICPC準備は新サークル長に任せて、自分はあまり口出しをしていないので、参加場所の確保がどうなるか・そもそも確保されるかがわかりません。

ha15さんは用事があって今日不参加とのことで、ゆきのんさんと2人でコンテストに臨みます。特に何も相談をしていませんでしたが、僕は初めにB問題を読むことにしました。

B問題

さすがにやるだけなので、書きながら考えます。和を取る配列を用意しましたが、書いているうちに定数個の変数でよいことに気づきました。適当に割り算するとサンプルが合ったので提出作業に入ります。ここで、普段コンテストに出るときのディレクトリで作業していることに気づいたので、icpcディレクトリに移動しました。中には今年3月の横浜大会の残骸が残っており、非常に懐かしい気持ちになりましたが、コンテスト中なのでとりあえず全部削除しました。

提出するとAC、7分弱でした。

D問題

次にどの問題に進むか決めるとき、A問題を担当してくれる（と自分が勝手に思っている）ゆきのんさんの音沙汰がないことに気づきました。いないならC問題を読もうかな、と思いつつメンションを飛ばしてみると反応があったので、Dを読むことにしました。どうやらログインに少し手間取っていたそうです。

Dは文字列長が10000文字以下という微妙なサイズの制約で、テストケース50個を含めても2乗が通りそうです。何でもできる気になり、文字列の後半を見て、今何文字目まで処理したかをキーに持つdpを書くことにしました。キーと遷移がそれぞれ文字列長のオーダーなので、全体で2乗……と思っていたら、遷移のチェックをする必要があることに気づきました。幸い、Z-algorithmを遷移前に計算することでチェックを定数時間で行えるため、そのまま実装を進めます。添え字がちょっとややこしいですが、適当に書いたらサンプルが合い、そのままACしました。

1ファイル5sec弱で実行できているので、定数倍はかなり軽めのようです。22分弱でした。

コンテスト後に気づきましたが、遷移先としては最も近いインデックスのみを考えるので良いですね。manacherアルゴリズムと同様に考えると、遷移が2種類以上あるなら、長いほうの遷移は短いほうの遷移を使って2つ以上に分解できます。線形時間の解法があるようで、この事実を使うのでしょうが、まだ遷移を探すフェーズをどうするのかわかっていませんこの記事を書いている間に解説が公開されて理解しました。

僕がZ-algorithmでチェックしていた文字列一致は、ローリングハッシュを用いたり、あるいは文字列全体を使って接尾辞配列を作ることで、線形時間の前計算が1回で済むようになります。また遷移を探すのも、短い文字列から順に試して見つかった瞬間に更新すれば、全体で線形時間になります。

E問題

適当に読むと、例えば列の左右から貪欲にそろえていくとか、1とNから貪欲にそろえていくとかが思い浮かびます。自分の勘はよさそうだと言っていたので後者を実装してみましたが、サンプルすら合いません。2つの要素を1個ずつずらすよりも、1つの要素を2個ずらすほうが安いからです。

貪欲の実装時、「移動しない」要素の処理のためにif文を書いていました。通常は移動距離+1だけコストがかかるのですが、移動しない要素はコストがかからないからです。このことを鑑みると、移動しない要素を先に決め打っておけば、あとは貪欲に操作してよいようになりそうです。これを信じて、移動しないと固定した要素の最大値をキーに持つdpを考えることにしました。

dpの遷移は、今見ている要素を新しく固定するか、あるいは左に飛ばすか、右に飛ばすかです。移動しない要素を固定している以上、残りのコストについては「飛ばす」側と「飛ばされる」側のどちらに注目して計算してもよいです。よって僕の実装では、自分より左にある自分より大きな要素の個数を数えて、dpの全ての値にコストとして加えることにしました。あとは、要素を固定しないならコストに+1する、要素を固定するなら新しく値をセットする、の操作が必要で、結局区間ADD区間MINの遅延セグメント木で対応できます。

サンプルが合ってそのままAC、結構考察が難しく65分くらいでした。

書いている途中に薄々感づいていましたが、固定する要素はLISと一致し、残りのコストは転倒数のようです。固定するものがLISであると決め打ってよいのかすぐにはわからなかったので、間違いなく計算できそうな上のアルゴリズムを実装しましたが、コストを「移動距離」と「+1」に分けて計算していることをはっきり自覚していれば、それはそうという気持ちになりました。

また、途中でゆきのんさんが書いてくれていたC問題が微妙に炎上しかけていました。僕は一読してbitDPだと感じたのですが、どうやらゆきのんさんもそれで実装していて、結構大変なようでした。単純なdfsで通らないかということを聞かれ、特に計算量を見積もれたわけではないですが通りそうだということを伝えると、しばらくして、爆速で実行が終了したということが報告されました。

F問題

問題文を読むと、dpだろうなという直感がありました。その方針で考えます。まず必要なのは0と1の個数で、これでO(|t|^2)かかります。ほかに交換回数が求まるような情報を持つと安心ですが、遷移がO(n)種類あることや、交換回数がO(|t|^2)くらいになりうることを考えると、これ以上dpの次元を増やせません。

しかし冷静に考えると、交換回数というのは2つの文字列における1のインデックスを取り出して、それぞれ先頭からペアにしつつ差の絶対値を足し合わせたものに他なりません。つまり、途中まで確定した文字列があったとき、それ以降どんな文字列が来るかというのは現時点での交換回数の計算に影響しないことがわかります。

このことから、交換回数を毎回求めつつ最小値を達成するもののみを保存することで、文字列が完成した時の交換回数の最小性が満たされることが言えました。さらに考えを進めると、dpの各値を達成するような文字列については辞書順で最も小さなもののみを保存しておけば、辞書順最小という性質も満たされると言えます。前半の文字列で、0と1の個数が等しいにも関わらず交換回数や辞書順に差がついていれば、後半の文字列がどう頑張っても取り返せないということです。

0と1の個数を持つ代わりに、現在構築した文字列長と1の個数を持ってdpしました。状態数は変わらずO(|t|^2)、遷移はO(n)種類で、各遷移で交換回数を求めるのにさらにO(|S_i|)かかるので、だいたい1004になります。定数倍はかなり軽めなものの、代わりにさらにテストケース数が100個あり、手元で少し時間をかけて回しました。ただ解法に至るのがかなり速かったのでACは75分くらいでした。

解説では、文字列を後ろから構築しなければならないと書かれていましたが、その必要はありません。

G問題

問題文に全方位木dpだと書いてあったので、読んですぐ実装に入りました。実は想定解は全方位木dpではないらしく、びっくりです。

まず、各頂点に対して「親に戻ってこないときの最大値」「親に戻ってくるときの最大値」を求めました。頂点uについて、それぞれdp_{u,0}とdp_{u,1}とでもしておきましょう。初期値はそれぞれ1で、uの子vを見ているときの更新はdp_{u,0}\leftarrow dp_{v,0}+1と、x[u]=='2'のときdp_{u,1}\leftarrow dp_{v,1}+2です。\leftarrowはchmaxの意味です。

X[u]==2のとき、dp_{u,0}についてはもう少し考える必要があります。つまり、uからv_1に行って、戻ってきてからさらにv_2に行くようなケースがあります。後から述べるようにv_1=v_2であるケースが存在して今の状態では対応できませんが、当時はv_1\ne v_2だと思い込んで実装していました。

とりあえず、v_1\ne v_2なるv_1,v_2を選んで、dp_{u,0}\leftarrow dp_{v_1,1}+dp_{v_2,0}+2としたいです。僕はdp_{v,1}のargmaxを求め、それがv_1になる場合とv_2になる場合をそれぞれ求めました。

あとはこれを全方位木dpにします。親から子に遷移するときの値を求める際、上の計算が邪魔をして、単純に左右から累積maxを取るだけでは対応できません。そこで、子らを区間MAXのセグメント木に乗せることにしました。ついでにargmaxも求まるようにしておけば、計算に使えない要素が遷移先の子とdp_{v,1}のargmaxで2種類になっても、区間を3つ用意して調べるだけで対応できます。

実装が完了してサンプルを試すと、最後のケースだけ答えが1小さくなってしまいました。先ほども述べた通りv_1=v_2となるようなケース、つまり途中で親と子を往復してまた子の先に行くというようなケースです。これに対応するため「親に戻ってこず、頂点uも1回しか通らないときの最大値」としてdp_{u,2}を定めました。

初期値はこれまた1で、更新はdp_{u,2}\leftarrow dp_{v,0}+1です。また往復するケースに相当するのは、x[u]==x[v]=='2'のときのdp_{u,0}\leftarrow dp_{v,2}+3になります。uを2回、vを1回通ることになるので、dp_{v,2}ではvは1回しか通らないことを保証したかったのです。x[u]だけでなくx[v]も見る必要があるので、親から遷移するときに親のxも渡す必要がありましたが、全方位木dpにおける遷移の計算自体はこれまでのもののコピペで十分対応できました。

サンプルを試すと合ったのですが、提出のためデータセットを落としてくると、途中でセグフォしてしまいました。どう考えてもスタックオーバーフローです。いろいろ調べて、コンパイル時のオプションに-Wl,--stack,104857600を指定すると、ちゃんと最後まで実行されました。

できた出力ファイルを恐る恐る提出したところ、WAでした。一人黙々と実装してしまっており、このときゆきのんさんに言われてようやくコードを共有しました。

とりあえず適当なケースを試そうと思い、3頂点の直線グラフでx="222"としたケースを投げると、9が返ってくることに気づきました。初手でHackケースを引き当ててびっくりしつつ、デバッグ出力を挟んで確認してみます。dpの値は問題なく計算できていましたが、そこから全方位木dpにするにあたって、親からの遷移の値がおかしいようでした。

よくよく見ると、dp_{v,2}の値をセグメント木に乗せる際x[v]=='2'であることを確認していなかったのと、確認していても、そもそもセグメント木の初期化のため用意したvectorの中身がintのデフォルト値0になっていて、それに遷移で+3するものだから、このような値になってしまったようでした。乗せるモノイドの単位元をより小さな値にして、初期化のためのvectorも作成時にその値で埋めるようにしたところ、ちゃんと正しい値である5を返すようになり、再度提出するとAC。132分でした。

残り時間はHを考えていて、bを固定した時のaとしてありうる値の区間幅を積分するとかそういう方向で計算していましたが、うまく区間になってくれるかもよくわからないし、適当に出した式はminなどが入っていて積分が面倒そうだったしでやりたくなさが物凄かったです。結局その後はコードも書かずコンテストが終了しました。

コンテスト終了

結果は総合・現役5位、学内1位でした。G問題がただの重実装だったので、差がつく問題がそれで望外に良い結果が出たという印象です。

立ち回りは相変わらず下手くそで、チーム戦ができていません。大体ずっと一人で問題を抱え込んでいて、今回は解けたからよかったものの、E問題などちょっと間違えば考察で詰まりかねないものは積極的に共有するべきでした。

G問題のコードを貼っておきます。ACLのsegtreeを使用します。そういえば、G問題の木の入力は各頂点の親を与えるもので、dfs呼び出しで親の頂点番号を渡す必要がなかったり、子らにインデックスを割り振るとき隣接リストから親をわざわざ抜く必要がなかったりするのが便利でした。

#include<iostream>
#include<vector>
#include<algorithm>
#include<atcoder/segtree>
using namespace std;
int N;
string X;
vector<int>G[1<<17];
int dp[1<<17][3];
void dfs1(int u)
{
    dp[u][0]=1;
    dp[u][1]=1;
    dp[u][2]=1;
    int mx2=-1;
    for(int v:G[u])
    {
        dfs1(v);
        dp[u][0]=max(dp[u][0],dp[v][0]+1);
        dp[u][2]=max(dp[u][2],dp[v][0]+1);
        if(X[u]=='2')
        {
            dp[u][1]=max(dp[u][1],dp[v][1]+2);
            if(X[v]=='2')
            {
                dp[u][0]=max(dp[u][0],dp[v][2]+3);
            }
        }
        if(mx2==-1||dp[mx2][1]<dp[v][1])mx2=v;
    }
    if(X[u]=='2'&&mx2!=-1)
    {
        int n0=0,n1=-1e9;
        for(int v:G[u])if(v!=mx2)
        {
            n0=max(n0,dp[v][0]);
            n1=max(n1,dp[v][1]);
        }
        dp[u][0]=max(dp[u][0],max(dp[mx2][1]+2+n0,dp[mx2][0]+2+n1));
    }
    //cout<<"dp["<<u<<"] = ("<<dp[u][0]<<", "<<dp[u][1]<<", "<<dp[u][2]<<")"<<endl;
}
using dat=pair<int,int>;
dat op(dat a,dat b){return a<b?b:a;}
dat e(){return make_pair(-1e9,-1);}
int ans;
void dfs2(int u,int p0,int p1,int p2,char pc)
{
    //cout<<u<<" <- ("<<p0<<", "<<p1<<", "<<p2<<")"<<endl;
    {
        int now0=max(dp[u][0],p0+1);
        ans=max(ans,now0);
        if(X[u]=='2')
        {
            int n0=0,n1=-1e9;
            for(int v:G[u])
            {
                n0=max(n0,dp[v][0]);
                n1=max(n1,dp[v][1]);
            }
            ans=max(ans,max(p1+2+n0,p0+2+n1));
            if(pc=='2')
            {
                ans=max(ans,p2+3);
            }
        }
    }
    int n=G[u].size();
    vector<dat>in0(n+1),in1(n+1),in2(n+1,e());
    in0[n]=make_pair(p0,n);
    in1[n]=make_pair(p1,n);
    if(pc=='2')in2[n]=make_pair(p2,n);
    for(int i=0;i<n;i++)
    {
        in0[i]=make_pair(dp[G[u][i]][0],i);
        in1[i]=make_pair(dp[G[u][i]][1],i);
        if(X[G[u][i]]=='2')in2[i]=make_pair(dp[G[u][i]][2],i);
    }
    atcoder::segtree<dat,op,e>P0(in0),P1(in1),P2(in2);
    for(int i=0;i<n;i++)
    {
        int np1=1;
        if(X[u]=='2')
        {
            np1=max(np1,max(P1.prod(0,i).first,P1.prod(i+1,n+1).first)+2);
        }
        int np2=max(1,max(P0.prod(0,i).first,P0.prod(i+1,n+1).first)+1);
        int np0=np2;
        if(X[u]=='2')
        {
            np0=max(np0,max(P2.prod(0,i).first,P2.prod(i+1,n+1).first)+3);
        }
        if(X[u]=='2')
        {
            dat tmp=op(P1.prod(0,i),P1.prod(i+1,n+1));
            if(tmp.second>=0)
            {
                int l=tmp.second,r=i;
                if(l>r)swap(l,r);
                np0=max(np0,tmp.first+2+max({P0.prod(0,l).first,P0.prod(l+1,r).first,P0.prod(r+1,n+1).first}));
                np0=max(np0,P0.get(tmp.second).first+2+max({P1.prod(0,l).first,P1.prod(l+1,r).first,P1.prod(r+1,n+1).first}));
            }
        }
        dfs2(G[u][i],np0,np1,np2,X[u]);
    }
}
int main()
{
    while(cin>>N,N)
    {
        cin>>X;
        for(int i=0;i<N;i++)G[i].clear();
        for(int i=1;i<N;i++)
        {
            int p;cin>>p;
            G[p-1].push_back(i);
        }
        dfs1(0);
        ans=0;
        dfs2(0,0,-1e9,0,'1');
        cout<<ans<<endl;
    }
}

週記（2021/10/18-2021/10/24）

10/18(月)

先週の週記のページで「が、」を検索すると、なんと70件も存在した。先週は14000文字と少しだったので、実に200文字につき1回のペースでこの接続詞を使っている。文章ごとに読み直した限り、少なくとも自分にとって不自然な言葉遣いにはなっていない一方、全体として見ればあまりにも多すぎる。というわけで、今週の週記はこの接続詞をできるだけ使わないように書いてみたいと思う。逆接なら別の接続詞を採用し、そうでない微妙な用法の場合は、その文章の語順をもう一度推敲するようにしたい。

先週の週記を投稿してからは、Kaggleのチームメイトにもらったスクリプトをぶん回し、ファンの音を感じつつ布団に入った。少しだけハーメルンを読み進めていたら、午前4時過ぎに寝落ちしてしまったようだ。火曜日の同じ時間の空を見る限り、ちゃんと白む前に寝られたはず。

午前8時半くらいに目を覚ます。眠気がかなり残っていたので二度寝できそうな感じだったのに、トイレに立ったついでに回していたスクリプトの様子を見ようとパソコンの前に座った結果、目が冴えてしまった。スクリプトは全然終わっていなかった、どころか、KFoldで5分割したうちの1つすら終わっていないという始末であった。Kaggleなので、ここでどれくらいの実行時間かに言及するくらいはよいだろうと期待している。

atgolferの更新を確認すると、昨日のABC223Cが縮められていた。dcのループ部分に改善があったようだ。そこから入力の1行目もまとめて処理することで-1B、さらにループ部の改善の影響でスタックに2つの値を持つ必要がなくなっており、そのおかげでわざわざ下の値を先に計算しなくてよくなり-4Bと、合計-5Bで取り返した。前者はともかく後者の改善は自力で式を弄ってたどり着いたアルゴリズムだからこそという印象がある。

布団に戻ってからも案の定眠れず、ハーメルンを1作読了した。「レウスはレイアを拒めない」。

レウスはレイアを拒めない - ハーメルン

リオレウスに転生した主人公の視点の話よりも、むしろハンターに転生した別の転生者視点のほうが好みに合った。どこかの話の後書きで言及されていた、狩猟笛使いが主人公のハーメルンを探そうと思い、原作：モンスターハンターで検索して総合評価順に並べてみると、一番上にあったので、次はこれを読もう。しかし総合評価上位はどれも話数少なめなのが気になる。

ちょっとだけ読んで、昼前になったのを見て寝るのを諦めた。大学の昼休みが始まる前に学食に行って、帰ってきてからはしばらくネットサーフィンをしていた。ICPCのチームのコーチから登録情報にエラーがあると言われて自分のものに問題がないことを確認した。チームの画面を見ると、エラーの内容が表示されていたので、先にこれを確認すればよかった。昨日の深夜回し始めたスクリプトは、ようやく5分割のうち1つが終了していた。実に8時間かかっているようで、これを後4回行うのかと思うとめまいがする。

午後1時、今更耐え難い眠気が襲ってきたので布団にダイブ。ちょっとばかりハーメルンを読み進めた後午後2時から午後4時まで昼寝をした。起床後はかなり眠くて、布団の上でしばらくウネウネしていた。

午後4時半からインターン先の定例会。進捗報告のスライドは10分で捻り出したので、話す内容を考えておらず散漫な話題になってしまった。作ったヒストグラムやビジュアライズの結果を見せたので、見栄えはしたのではないか。あとは他の人の発表を聞いて、勉強会に参加して終了。直後にKaggleのチームミーティングが少しだけ行われ、そこで今回しているフルで学習するスクリプトじゃなくても実験はできるということを確認した。データのサイズを減らしたり、KFoldを1回で抜けたり、そういう感じでもモデルや特徴量の相対的な評価は十分に可能。

フォローしていた絵師のアカウントが乗っ取られたことを知った。そのアカウントは現在削除されていて、こちらからフォローを解除したりはできない。絵師のサブアカウントのツイートについていたリプライ曰く、乗っ取った直後は通報されるのを避けてアカウントを削除し、復活期限の30日ギリギリまで待つのではないだろうかとのこと。正直僕はこのことを30日間覚えてはいないだろう。なのでここに書いておいて、もし何かの拍子にこの日の日記を見て思い出したらキチンとフォロー解除しておきたい。

乗っ取られたアカウントは@caburiakiで、新アカウントは@caburibbonである。R18の絵を描く方なので、注意されたい。

ハーメルンを1作読み終えた。今日の昼から読み始めたもので、「笛吹いてたら弟子に推薦された」。

笛吹いてたら弟子に推薦された - ハーメルン

ほぼ再序盤でエタっており、主人公の強さみたいなものは全然描写されていない。錚々たる顔ぶれの古龍と知己を得ているという設定や、強豪ハンターの師匠役であるという設定は好みだった。

CADDIのコードゴルフに挑戦してみた。1、2問目はパーを下回るくらいわけない。3問目はパーが設定されておらず、解ければそれでいいという問題で、こんな感じのブログに乗っている問題なのだから簡単だろうと臨んだのに結局解けなかった。

コードゴルフのキャディをやってみた - CADDi Tech Blog

「科学の力使いまくって隠居生活」の新作が投稿されていた。最近めいさんのはてなブログを読んでおり、ゆっくり実況よりも生身の人間に近づいた感じがしていたところ、逆に動画のゆっくりたちの掛け合いをどことなく冷めた目で見るようになった自分に気づいて愕然とした。僕のインターネット歴としてはそれなりに昔からずっと見ているゆっくり実況者なだけあって、めいさんも現実に存在する人間であるという認識が薄かったのだろうか。

www.youtube.com

最近本を読んでいないことに危機感を覚え、1冊手に取って半分ほど読みつつ、先週金曜日のyukicoderを解いた。とりあえず前4問。

yukicoder contest 318 - yukicoder

Aは非常に面白かった。1回操作すると、そこから別の操作をどれだけ行っても数列は変わらない。よって高々1回操作する場合だけ考えればよい。Bは問題をジャンルごとに分け、各ジャンルで最もクオリティが高い問題のクオリティにXを加算し、あとは貪欲。Cは0の位置が決まり、そこからmexが確定する区間を繋げて伸ばしていけばよい。Dは包除原理などいろいろ悩んでかなり迷走した。最終的には上の桁から見て行って、最小値を作る際に選べる要素数を持ちながらdpして解いた。

布団に入ってハーメルンを読んでいたら、午前6時過ぎに寝落ちした。

10/19(火)

昨夜は学食に行くことを夢見て午後1時に目覚ましをセットしたようだ。一応その時間に目を覚ましたものの、明らかに眠すぎる。結局布団の上で身動きが取れず、うつらうつらとしているうちに学食は閉店してしまった。しかし二度寝できているわけでもない。学食が閉店した後も少しハーメルンを読んだりして、結局午後3時近くになってようやく入眠できた。

午後4時半起床。午後5時からの1on1には余裕を持って起きられて、進捗も産めるだろうと思っていたのに、結局乱れた生活リズムが何もかも吹き飛ばしてしまった。焦りつつデータのビジュアライザを少しだけ改修してみると、少しの時間のコーディングに比べて視覚的な変化がかなり大きく、満足。

1on1。機械学習が上手く行っていないという話になりそうでビクビクしていたところ、モデルのパラメータばかり弄るのではなく、ラーニングレートやその変化のさせ方についても気を配らなければならなかったとメンターさんに教えていただき、ちょっと希望が見えてきた。しかしその周りのことはサンプルコードを写したきりなので、なんにもわからないなあと不安がっていたら、メンターさんも実験してくださるそうなので、後半ではデータセットをAWSにアップロードして共有する作業を指南してもらった。その過程でパスワードやアクセスキーを2回ほど共有・録画していた画面に表示してしまい、そのたびに再発行していただくことになって恐縮しきりだった。

1on1が終わってから学食に行った。注文を迷っていたら後ろから人が来たので譲ったところ、その人が僕が頼もうと思っていた定食を注文して、品切れの予感に震えた。実際は僕が注文したところで品切れになったので、危ないところだったと冷や汗を拭った。

帰宅してしばらくコードゴルフをしていた。Octaveのglpkという線形計画問題を解く関数を使う問題がいくつも縮んだ。glpkはデフォルトで目的関数を最小化するように動く。一方競技プログラミングでは最大化した値を求めることが多く、その場合は最後の引数senseに-1を渡す必要がある。keyword argumentではなくpositional argumentとして渡せるのでまだマシなものの、それでも+3B、またそれ以前の引数がデフォルト値で良かったならばさらに増える。代わりに、目的関数を符号反転することにした。その符号反転で+1B、得られた解をまた符号反転して+1Bで、-3Bと合わせて都合-1Bの短縮であった。

昨日から手を付けていた本を読了。「探偵は教室にいない」。午後の時間は、文章中では「十六時」「十七時」といった24時間表記で書かれ、対してルビはツイートの画像のように「よじ」「ごじ」と振られていたのが特徴的に思われた。確かにこちらのほうが現実に即している。

内容は非常に面白かった。日常の謎としてちょうどいい感じ。設定について、探偵役（とその周りの人）がみんな中学生だというのが気になった。やっていることは高校生でも成立しそうに見えるものの、それでも思考や許される範囲の行動に中学生らしさが伺える。考えてみれば、すでに成人した人間が無理なくイメージできる下限は高校生なのかもしれない。中学生まで下がると、その年代特有の感覚だったり様々な制限が表面化してきそうなものだ。それらもこの作品では描かれていたように思う。

火曜5限のPythonの講義スライドを流し見た。二分探索法が紹介されていて興奮するも、以降特に関係ない話題に移ってしまい残念。Pythonのsetはhash setなのだ……。課題は非線形方程式を解くもので、講義ではニュートン法と、その微分係数の部分を差分で近似した割線法が紹介されていた。課題になっている非線形方程式は微分可能なので、無難にニュートン法を実装した。講義スライドに書かれていたヒントの式が誤っており、しばらく首をひねっていた。ちゃんと自分で考えればわかる。

明日から数日、帰省することにした。その間もインターンの実験コードを回したいと思い、マシンにSSHで接続できるよう設定することを思い立った。とりあえずルーターの設定からIPアドレスを固定して、これで内部ネットワークからのログインは成功。高校生の頃、仮想環境でサーバーを立てたいと思い立ち、ひとしきり唸って諦めたことを思い出すと、かなりの進歩である。現在は仮想環境を作らずともマシンをいくつも持っているのが嬉しいところ。

そのあとノーパソを取り出し、これにテザリングして外部ネットワークからのログインに挑戦しようとした……と、それをする前に、以前からずっと音が出ない状態なのが気になって、これを直そうと3時間弱格闘していた。

ノーパソから音が出ない（スピーカーがダミー出力しか選択できない）ことが発覚。ちょっと格闘してみたが直らなかった

週記（2021/07/19-2021/07/25） - kotatsugameの日記

直った。ちょっと記録を付けておこう。最初はalsamixerが起動しなかったり、/proc/asound/cardsに何もなかったりしていた。lspciではMultimedia audio controllerの存在を確認できる。dmesg|grep sndをしてみると、snd_soc_sklがエラーで落ちているらしい。これはlspci -vから見ることのできる、今現在使われているKernel driverであった。また、そのちょっと下にsnd_hda_intelが見える。もしかして使っているドライバが違うんじゃないかと考え、それからはなんとか使うドライバを変えようと試行錯誤していた。ドライバ名をキーワードに入れていろいろ検索した結果、alsa-base.confにoptions snd-hda-intel dmic_detect=0と書いて再起動したらドライバが代わり、音が出るようになった。感動……！

SSHの話に戻る。そこからさらに3時間ほど格闘したものの、結局ポート開放すらできなかった。ファイアウォールを設定して、ルーターの設定もして、sshdのconfigもちゃんと合わせたはずなのに……。nmap localhostで見てもsshが待機しているという表示が出なかったので、最後はそれを出そうとして、諦めたのだった。

午前7時になってしまった。しばらくなろうの更新を追ってから、帰省の準備を始める。とりあえず時刻表を眺めたところ、親に新幹線駅まで迎えに来てもらおうとすると、かなり急がなければならないことに気づいた。しかもどれもこれも接続が悪く、うまい具合に乗り換えようとすると今から40分後に出発する新幹線に乗るしかないようだ。

ひょっとして間に合うんじゃないか？と思い、急いで着替えて準備をし、家を飛び出した。家から地下鉄駅までを爆走し、朝なので結構頻繁に走っている地下鉄に乗り、仙台駅に到着。地上に上がるエスカレーターも早歩きしたので、残り10分ある。ATMで素早くお金を下ろし、みどりの窓口のテープで区切られた待機列をウネウネ走って、息も絶え絶えになりながら切符を買った。みどりの窓口の時計を見ると残り3分くらいで、焦って改札に駆け込もうとしたところ、その上の電光掲示板でまだ微妙に余裕があることに気づく。もしかしてみどりの窓口は少し時計を早めているのかもしれない。ニクい心遣いだ……。しかし逸る気持ちは抑えられず、売店で朝ご飯を買うのをスキップしてホームまで上がってしまった。

飲み物がないのは厳しいので、途中待ち合わせでしばらく停車すると聞き、そこで買うことを思いついた。しかしうっかり先頭車両に乗っていたので、自販機との往復はホームをオタクダッシュする羽目になってしまい、これまた大変だった。

大宮で乗り換え。仙台から乗ってきたやまびこはかなり空いていたので、やはり平日の昼間は人がいないかと思っていたのに、大宮から乗ったはくたかの自由席は1つ飛ばしでほぼ埋まっていた。なんとか空いているC席を見つけて座る。周りが人だらけの中、申し訳なく思いながら売店で購入してきたパンやおにぎりを詰め込み、やっと人心地が付いた。

黒部宇奈月温泉駅からは親の車で自宅に向かう。途中、本屋に寄って帰省中に読む本を4冊購入。全部読めるわけはないものの、これくらいなら自分の手で持ち帰れるだろう。

午後2時半、実家のこたつに潜り込んで就寝。

10/20(水)

午後7時半起床。

TwitterのDMでインターン面接についての質問が来ていたので、当時の日記などを読み返しつつ自分語りをした。改めて振り返ってみると、自分がなぜ受かったのかわからない。特に、何度もやりたいことを聞かれていて、その度曖昧な答えしか返せていなかったのが気になる。やはりレートで殴ったということだろうか。

チュウニズムの超大型アップデートの情報が流れてきていた。公式ページを舐めるように読んで内容を確認する。楽曲の削除は恒例行事、LEVEL表記の細分化は驚きの一方で納得もできる。スキルのシステム変更も、これまで通りコラボマップのキャラに対して毎回特別スキルを割り当てているとデータが増えて大変というのは伺える。しかしそれにしたって残すスキルが少なすぎやしないか。個人的にはパニッシュメントが消えてATTACK以下でスキル音を鳴らせなくなったのが辛い。

info-chunithm.sega.jp

あとは、楽曲の削除に伴ってスピソニ称号がいくつか消えることも特別注意しておきたい。1速は一応「見える」のでその場で粘着すれば取れるのに対し、スピソニは入念な研究が必要だろう。消える前に取れるよう頑張る。

「りゅうおうのおしごと！」15巻を読んだ。今回も非常に良かった。シーンとしては序盤に雛鶴あいがYouTuberをやっているのが好みだった。ただ、この巻の主題は当然そこではない。表紙を見ればわかるとおり、一冊通して供御飯万智が九頭竜八一と仲を深めるのを中心に展開しており、序盤はその2人と雛鶴あいが交互に描かれ、ラストで激突して云々……。その後のエピローグも含めて大満足の巻だった。と、良質な読書体験に満足しつつ、巻ごとに最後に付いてくる感想戦を読んでいたら、そこでさらに驚くべき展開が描かれびっくり。作中で九頭竜八一が出した本の反響も含め、次巻がとても楽しみである。

寝る前に、部屋の本棚を探し回って「浅草鬼嫁日記」の1巻を発掘した。最近同作者の別作品「かくりよの宿飯」シリーズを読んだので、こちらを読み返して大旦那様が登場しているシーンを探そうというわけだ。

記憶が新しいうちに同作者の「浅草鬼嫁日記」のほうを読み返して、リンクしている箇所を探してみたいと思う。今は本が実家にあるので、そのうち帰省したらやってみよう。

週記（2021/09/13-2021/09/19） - kotatsugameの日記

実際、見つかった。114-115ページだ。かなり丁寧に描写されているにも関わらず、記憶が正しければこちらの作品で特別な役割を果たしたりはしなかったはず。おそらく当時は何かの伏線だと思い、そのまま忘れてしまったのではなかっただろうか。こういうネタは作者のファンとしては嬉しい一方で、知らない読者を置いてけぼりにしがち。

見つけた後も読み進めて、結局1冊まるごと斜め読みしてしまった。やはり僕が好きな見せ場を作るのが上手い作者であると感じた。2巻以降もチェックするつもりでいたけれど、思ったより時間が経ってしまったし、本棚にバラバラに刺さっているようでそもそもどこにあるのかわからないため、切り上げて寝ることにした。

午前4時半就寝。

10/21(木)

正午起床。今日は帰省の主目的である免許更新と、ついでに参院選の期日前投票に行く。

食事して準備して、さあ出かけようとしていたところに、LINE通話がかかってきた。訝りながら応じると4年ゼミの友人からで、曰く「ゼミ始まってるけど起きてるか？」……ちゃんとゼミの休みを確認して帰省したはず、と慌てて以前送られてきたメールを見返すと、ゼミが休みなのは今週ではなく来週だったらしい。

もうどうしようもない。明日は免許更新できないし、それ以降にずれ込むと生協の弁当配達やコンテストにぶつかって嬉しくない。ということで今日は休むことにして、とりあえず友人から教授に欠席を伝えてもらい、自分も移動中の車内で謝罪メールを作成して送信した。

まず投票。選挙権を得てからすぐ仙台で下宿を始めたので、投票するのはこれが2回目である。投票用紙は特殊な紙でできていて、折り曲げてもすぐ戻る……ということを覚えており、試しに端を折り曲げて感動していた。しかし思いっきり伸ばした状態で投票箱に入れてしまい、横目で見えたらしき母に注意された。

その後免許更新へ。お金を払い、設問に答え、視力を測り、写真を撮る。ところで、僕が3年ほど前に入院したことを覚えている人はいるだろうか？

実はこのとき診察中に意識を失ったことがあって、そのことを申告したら別室に連れて行かれてひとしきり問診を受けた。免許を取ったときも同じ理由でちょっと手間取った記憶がある。自分でもなぜ意識を失ったのかよくわかっていないので、曖昧な受け答えしかできなかった。前回も今回も、最終的には許してもらえた。

初回の更新ということで、2時間コースの講習を受ける。講習が始まる直前にJOI一次予選（第2回）の過去問が公開されているのを見つけ、心臓が飛び跳ねた。URL自体は推測できるので、先週日曜日からずっとスマホとパソコンの両方で以下のページを開いており、起きている間は数時間に一度リロードしていたのだった。

JOI 2021/2022 一次予選 (第2回) 過去問 - AtCoder

A、Bはdcでサクッと通す。僕が一番最初に過去問を見つけたようで、ちゃんと最短が取れていた。その後CとDを読み、すぐにはわからなかったので、講習中に考えることにしてその場は放置した。講習中はスマホ禁止である。1時間くらいして休憩時間になり、そそくさとスマホを取り出してコーディング。さらに1時間講習を受けて終了、そこから家に帰る車の中でもまた縮めていた。Cは肯定先読みをgrep -Pで行い、Dは適当にRaku。めちゃくちゃ車酔いしてしまった。

免許証の写真には寝癖が付いていた。

電車に乗って富山駅に出て、夏から会うタイミングを計っていた卵生みらーじゅ（@asakaakasaka）さんと、彼が連れてきてくれたカーニ・カ・ニーカニ998244353世（@kani_kanichann）さんと会った。なんと呼べばいいかわからなかったのでとりあえずTwitterにおける現在のユーザー名を書いておいた。もし別の文言に置き換えたほうが望ましいなら、そのことを教えてほしい。

まずゲーセンに行く。音ゲーが3階から1階に降りてきておりびっくりした。更にチュウニズムの台数も1台減って2台に。カーニ・カ・ニーカニ998244353世さんはプレイしないそうなので、お言葉に甘えまくって卵生みらーじゅさんと3クレくらいプレイした。

その後サイゼリヤに移動。恒例の間違い探しは、最後の1つだけネットで答えを見た2人にヒントをもらってしまった。食事後、やることがないなら……といそいそとソートなぞなぞを布教して、1時間ちょっと遊んだ。今日はかなり素早く答えが出る問題が多かった気がする。これまで飲酒しながらやっていたのはまずかったのかもしれない。

会計は別々に精算するのだとばかり思っていたところ、卵生みらーじゅさんが奢ると言ってくださって、ありがたいやら申し訳ないやらでモゴモゴしているうちに支払いが完了してしまっていた。また機会があったら、次は僕が奢るらしい。望むところだ。電車に乗って帰宅。

帰宅してから、行き帰りの間に読んでいた本を読み切った。「異世界でチート能力を手にした俺は、現実世界をも無双する」9巻。主人公がひたすらインフレし続けて、毎回新たに登場する敵をバッタバッタとなぎ倒している。少し前の巻からあとがきでも「作者でもどうなるかわからない展開」と書かれており、正直もう内容は気にしていない。イラストレーターが好みなのと、たまにある現実世界のシーンが気に入っており、また読むのに負荷が一切かからないこともあって、読み続けている。

さらにもう1冊手を出し、3分の2くらい読んだところで就寝。午前4時半だった。

10/22(金)

午後1時半起床。

食事してちょっと読書してから、高校生のとき通っていた塾に出向いた。帰省時の恒例行事。先生としばらく話した後、1時間くらいプリント採点のバイトをして、雨が降りそうだったので急いで帰った。生徒から「何も見ずに1分計ってみて」と言われ、心の中で数えているうちになんとなく速い気がして心配になり63秒の時点で答えたところ、タイマーでは62秒だったらしくかなり残念な気持ちになった。自分を信じられていない。

TCB41に出た。例によってこの日記が公開される頃にはイベントが終了しているから、ここに各問題の感想を書いておこう。この回は3連覇がかかっていると思ってかなり気合いを入れていたのに、WAを出してしまったし、それでなくとも解くのが遅くて減点されていた。しかし解き終わってから改めて確認してみると、TCB38-40ですでに3連覇を達成していたらしく、安心。

https://techful-programming.com/user/event/2274

6問目まではよい。7問目は、最初O(N)で解いてから制約をよく見ると間に合わないことに気づいた。焦りつつWolframAlphaに投げるとO(1)になってくれた。8問目は3bitのフラグを持って桁dpした。9問目は、重要でない要素のインデックスを引いていくことを考えれば、クエリをソートして遅延セグメント木でゴリゴリすることで計算できる。この問題に時間がかかったのと、尺取り法っぽいことをするときに最後に区間の左端を右まで寄せ切っておらず、1WA。計-18pt。10問目はベクトルの内積の最大化と考えれば、最大値を達成する点は凸包に含まれるため、クエリを偏角ソートして凸包上を回りながら計算できる。

解き終わるとちょうど夕食が完成していた。食事中、テレビにイナガキヤストさんが出ているのを見た。

1冊本を読み切った。「クールな月城さんは俺にだけデレ可愛い」。帯に紙城境介推薦と書いてあり、「文章上手すぎない？」という感想が乗っていたので身構えて読んだものの、僕としては正直期待はずれだった。文章の上手さとはなんなのだ。内容としてもほとんど記憶に残らなかった。読了ツイートにふぁぼん氏からリプライが来て、やっとタイトルに「クー」「デレ」が入っていることに気づいた。ヒロインは主人公に対してほとんどクールな様子を見せず、結果主人公視点が多いこの巻ではクール要素がゼロになっていたと思う。

読み終わった直後からyukicoder 319。全然わからなくて、考えているうちに微妙に意識を飛ばしたりしていた。

yukicoder contest 319 - yukicoder

Aはよい。Bはグリッドを二部グラフと考えると、最初に2人が同じ側の頂点にいれば捕まえられないことがわかる。ではそうでないときは……どうせ捕まえられるだろうと適当に投げたら通った。その後Cを読んでしばらく考え、しかし解けず、Dに移った。山が2つの場合に実験すると、石の個数が同じ場合だけ負けることが分かった。また、片方がコインを取ったらすかさずもう片方もコインを取らなければならないことが分かり、Nが奇数の場合は先手勝ちであることも分かった。この後、僕は残りの山が2つになったときにどうなっているかをずっと考えて解けなかった。2つの時にゲームが決まるわけではないのだ。

どうにも解けないのでEに移った。隣接項の差を-1,0,+1と表して、これがどう変化するかを確認すると、2ステップ後でも非ゼロなのは-1,-1,+1,+1\rightarrow +1,+1とその符号反転のみであることが分かった。つまり、最初の状態が-1,-1,+1,+1,-1,-1,\dotsとその符号反転なら-1か+1で、それ以外なら0になる。サンプルを合わせて投げたら通った。残り時間はCに戻って、貪欲でWAを出していた。終了直前に二分探索+最後に使用した要素を持つdpを思いついたものの、遷移を詰める暇もなかった。

CodeChefでSnackDown R1Aが始まっていたので参加した。4問解けば通れそうなsolved数とはいえ、ギリギリで通るのも嫌なので念のため5問解いておいた。

https://www.codechef.com/SNCK1A21

Aはよい。Bは{\rm lcm}(X,2X)=2Xと{\rm lcm}(XK,XK-1)=XK(XK-1)を答える。Cは上位K人が勝てる回数の総和の最大値を求め、Kで割って2を掛けた。Dは難しかった。片方が1要素しかない場合は別に計算しておく。残りは最小値を含む数列のmaxと最大値を含む数列のminを決め打つとどちらかを増やす・減らすことで一致させることができ、実際には片方を決め打ったらもう片方は二分探索で求めた。Eは連続する1の個数の増減を考えると、\pm 2^iしていく問題に言い換えられる。ところが構築の際は、文字列の外を操作しないように中途半端な位置にクエリを投げる場合があった。そのように操作すると、Kが奇数なら必ず構築可能である。Fはほとんど考えていない。いかにも難しそうであったので早々に諦めた。

明日は仙台に帰るのに、結局朝まで起きていてしまった。日記を書いて午前5時半就寝。

10/23(土)

8時半くらいに親に起こしてもらい起床。今日は仙台の部屋に生協から弁当が配達されるので、午後3時以降のそれに間に合うよう帰ろうとしたら、この時間に家を出なければ間に合わないような新幹線になった。

今日は新幹線の車内で寝てしまうだろうから、乗り過ごし対策にとスマホのアラームをイヤホンからのみ流す方法を調べていた。適当なアプリをインストールして試してみる。確かにイヤホンにしかアラームが流れていないものの音が小さく、音楽を流していたら聞こえない可能性があって困った。

結局、大宮までは十数分ごとに目を覚ますような微妙な寝方をしてしまい、せっかくインストールしたアプリの出番はなかった。大宮で仙台終点のやまびこに乗り換える。これなら乗り過ごす心配はないぞと思っていたのに、こちらではずっとハーメルンを読んでしまい、一睡もしなかった。乗客数については、大宮までは結構いたように思う。大宮からはガラガラだった。

仙台駅に着くと午後2時過ぎで、少しだけ時間があった。ゲーセンに行くのは現在の疲労度を考えれば無意味だったので、駅前でラーメンを食べて素直に帰宅した。

新幹線車内と帰ってきてから少しでハーメルンを1作読了。「龍の恩返し」。

龍の恩返し - ハーメルン

モンハン二次創作。主人公の寿命がめちゃくちゃ長く、話の進みも大胆に数百年飛ばしたりしていて、その辺りはかなり好みだった。ただ主人公と妻のイチャイチャは僕にとって必要ない要素。また、文章がやたら説明的で読みづらかった。

最近3回分でサブモニタがキャプチャされているのに気づき、非常に残念な気持ちになった。以前同じ現象が発生して、ちゃんと直したはずだったのだが……。パソコンを再起動すると元に戻ってしまうとか、そういうことだろうか。

週記（2021/10/11-2021/10/17） - kotatsugameの日記

まだ弁当が届かないので、↑を解決しようと試みていた。ケーブルの差込口を交換するとよいという話を聞いていたので、キャプチャされてしまうモニタとプライマリモニタで交換してみると、驚くべきことに何も変わらなかった。何もというのは言葉通りの意味で、Windowsにおけるメインモニタも移動したりしなかったのだ。モニタの情報がどこかに記録されていて、どんなケーブルで接続しようとモニタの識別には影響しないということだろうか。それっぽい情報はregeditで消してから再起動したはずなのに。

しょうがないので、前回と同様「ケーブルを外してから起動し、ちゃんとプライマリモニタがキャプチャされることを確認してから戻す」方法を取った。直った状態で試しに再起動してみると、やはりサブモニタがキャプチャされるようになったので、本当に再起動すると元に戻ってしまうらしい。

弁当が届いたので、ABCまで昼寝することにした。具体的には午後4時半から午後8時半まで寝ていた。起きてから食事しようとして、結局弁当を食べきれず放置したままABC224。

AtCoder Beginner Contest 224 - AtCoder

Aは出力するべき文字列を取り違えて1WA。sedだった。Bからもう面倒なのでC++、愚直にO(H^2W^2)。Cも愚直で、通した後ABC181C「Collinearity」と似ていることを思い出し、最短コードをコピペして提出したらTLEしたので放置して次に進んだ。Dはbfs。状態をarray<int,9>で持ったら1secくらいかかった。Eはa_iを降順ソート。FはARC061C「たくさんの数式」と同じ問題設定で、制約が強化されている。ARC061Cの最短コードが線形時間で動作することを覚えていたので、それをコピペしようとした。しかしdcなので実行時間に不安があり、自分の提出を漁っても別の言語で書かれたコードがなく、Pascalで0msを出した時もO(|S|^2)で解いていてどうしようもなかったので、dcのコードを読解してC++に直すことになった。Gは、サイコロを振りなおすときの期待値を変数で置いて立式するとその変数の値を二分探索できるようになったので、それで解いた。

C - Collinearity

C - Many Formulas

コードゴルフ。Aは末尾の文字列が2種類しかないため、sedでも最後の1文字だけ見れば判定できる。またそれ以上にVimでうまいこと文字列を削除するのが強かった。コンテスト中に9Bは達成したものの、同じ長さのコードが開始4分もせずに提出されており、勝てない。Bは解説を読むとO(N^2)だけ調べる方法が書かれていたので、それをOctaveで実装しておいた。Cは、コンテスト中にコピペしてきたコードが複素数の割り算でTLEしていたので、そこを共役な複素数を掛けるコードに直したらギリギリ間に合ってくれた。しかし慌てていたのか典型テクで-1Bできることを見逃していた。Dは手つかず。EはRubyで、文字列の配列を'.map{...'でjoinしてevalするテクからさらに進化し、".sort\n.map{..."でjoinしたあと必要ないsortをコメントアウトするというものが使われており、すごい。

Fは、ARC061Aからコピペしてきた式をRubyに書き直していたら、998244353と119<<23|1が等しいことを利用して縮められてびっくりした。modの値を初期化するのと別の変数を1で初期化するのが同じ場所で行われているので、それをまとめられたようだ。ほかに同様の手法で縮められるものがないかしばらく探してみるも、見つからなかった。その後Haskellの最短コードを見てみると別の漸化式が使われており、Rubyに写すと-1Bできた。最初に使っていた漸化式において、出力する値を直接持つように変数を足して立式すると得られるようだ。Gは二分探索をRubyで書いた。

Hを解説ACした。双対性は昔から超高度典型という感じで捉えていた。解説で紹介されている双対定理のステートメントは見るだに強そうである、しかし証明はあまり読んでいない。とにかく、整数性を外して式変形して、双対定理で書き換えて、整数性を戻すという具合だろうか？解説の通りに実装したら魔法のようにサンプルが合って感動した。

線形計画問題なのでOctaveのglpkが使えないかと思い、試しに提出してみたら通ってしまった。変数の整数性を課していないのに答えが整数になるのは、先に述べた整数性を外せるという条件からだろうか。変数の条件を行列で記述するのがかなり面倒で、最初は2重ループを書いていた。非ゼロ要素のインデックスなら簡単に得られることに気づき、試しにそのインデックスたちからsparse行列を構築して渡してみると、問題なく動いてくれてコードも結構縮んだ。

atcoder.jp

日付が変わったあたりでSnackDown R1Aが終了した。終了数時間前からE問題のACが異常に増えてびっくりしていた。聞くところによると、解説動画がどこかに上がったらしい。終了直前に5完しないといけないことに気づいて焦っている人が何人もいて、昨日気が向くままに5完しておいてよかったと安堵した。

布団に入ってハーメルンを1作読了。「貴方に好きと言いたくて【完結】」。

貴方に好きと言いたくて【完結】 - ハーメルン

またモンハン二次創作。最後まで読み切ってようやく、主人公がなかなかすごい奴だったことが分かった。それまでは、短いので最後まで読み切りはしたものの、よくわからない主人公がウダウダしているのを流し読みしているだけだった。

さらに別のなろうを開いて数話読み、午前7時就寝。

10/24(日)

午後1時半起床。食事して午後2時から模擬国内予選2021。

2021/Practice/模擬国内予選 - ICPC OB/OG の会

7完5位。自分はBDEFGの考察と実装を行った。E問題で微妙に詰まったものの、終わってみればかなり解けたコンテストだった。問題が解けると楽しい。

Bは式を分解すると直ちに求まる。Dは2乗が通るので、Z-algorithmでチェックして遷移するdpを書いたら5secくらいで終わった。冷静になると、manacherみたいな考察を行うことで、遷移先としては最も近いものだけ考えてよいことがわかる。しかしそこから線形にするのはまだわかっていない。

Eは1とNから貪欲に並べていくのが最初に思い浮かんだ。あまりに単純すぎるのでさすがにダメそうだなと思いつつ実装すると、案の定サンプルが合わない。しばらく考えてみると、k個先に動かすときにコストがk+1かかることが効いていて、うまくコストへの寄与を分解できないことに気づいた。これは動かさない要素を決め打つことで解消できる。動かさない要素として最後に選んだ要素をキーに持つdpを考えると、更新が区間addで書けたので、それで実家dpしたら通った。コンテスト後に、動かさない要素がLISとなり、残りは転倒数に一致するということを知ってびっくりした。

Fはdpのキーにこれまで作った文字列の長さと1の個数、値にこれまでのコストと文字列を持つと、単純にpairのminで更新できる。解説を読むと後ろから構築と書いてあって、嘘解法だったかと震え上がった。しかし前から構築しても正しい答えが求まることは証明できた。文字列の長さと1の個数が決まっている場合、それを達成する具体的な文字列によらず後ろに追加する文字列のうち最適なものは一意に定まる、ということから言える。

Gは全方位木dpをした。最初、親から来て、子と親を1回往復して、また子のほうに抜けていくという遷移を考慮に入れ忘れていた。これはちゃんとサンプルで落ちてくれるのでありがたい限り。1WA出すも、その後適当に試したケース（3頂点の直線グラフ、x="222"）がHackケースになっていて助かった。サンプルを見て慌てて追加したdpの値の初期値をちゃんと設定できていなかったのが原因だった。Hはbを固定した時のaの区間幅を積分というのを考えて、やりたくなさすぎてクネクネしているうちにコンテストが終了した。

2021/10/26追記：このコンテストの参加記を投稿した。

kotatsugame.hatenablog.com

直後、午後5時から午後10時まで久しぶりのOpenCup。チームで6完で、僕はAとCを解いた。

Aは表の1行目と1列目を取り出し、それぞれ隣接項のdiffを2回取ると、行（または列）におけるAの和が求まる。それらを反映してもう一度隣接項のdiffを取ると、端の値も求まる。行と列でAの和が等しくなるように両端に値を追加し、さらにこの状態でAを復元した後入力の値と同じになるように左下・右上に値を追加する。それぞれやり損ねて2WA。

Cは辺全てを重みの降順に並べて、同じ重みの辺を同時に処理した後、毎回UFの一致判定ができればよい。UFで扱う代表点を集合のうち最もインデックスが小さい点に定めると、計算量を犠牲に、更新が入った集合における更新前の代表点と更新後の代表点のpairをソートすることでUFの更新の様子を一意に表すことができる。あとはこれを更新が入った各木に対して求め、それらをさらにソートして隣接する要素が等しいか見れば、UFの一致判定に替えることができる。2回目のソートはvector<vector>のソートとはいえ、文字列のソートが文字列長の総和の準線形時間で行えるのと同じ要領で、これも十分高速にソートできる。この一致判定にたどり着くまでに2WA重ねてしまった。

他にチームではEHJKが解かれた。Kについては、僕は実際にグラフを作ってもいいんじゃないかということを指摘し、それ以降のことはコンテスト当時あまりよく考えていなかった。有向グラフの到達可能性を判定することになって、通常はbit並列による定数倍高速化くらいしかできないのでまずそうだった。実際には、作成したグラフは有向完全グラフのような形になるので、必ずハミルトン路が存在し、トポロジカルソート順で前の要素は後の要素に必ずたどり着けることになる。

dcの切り上げで新手を考案し、2つほどコードが縮んだ。割ったあまりが0なら0を、非ゼロなら1を商に足すとき、これまでは~d/++としていた。これはスタックをいくつ消費するかが確定せず、少し使いづらかった。しかし~d~++とすれば、スタックを消費する量が確定する。これを利用して、スタックの下に後々使う要素を積んでおき、変数を使う手間を省いたり、rotateして引き算する手間を省いたりしたのが2つの短縮の正体である。前者のコードのリンクを下に張っておく。

atcoder.jp

久しぶりにインターンの業務を進めようと学習を回してみたら、謎のエラーが出てtorch.cuda.is_available()がFalseになってしまった。エラーで検索してみると、とりあえずnvidia-smiで様子を見るべきらしい。実行してみるも、GPUドライバのバージョンが合わないと怒られてしまった。最近apt updateをしたので、それで何かバージョンが食い違ったのだろうか。よくわからなくなったのでとりあえずPytorchを更新するも、まだ直らない。さらにCUDA Toolkitを更新してみると、同時にGPUドライバのアップデートも行われたようなlogが表示され、見事に直った。

TCB41が終了していた。4位だった。1位は理論値だし、時間の総和でも負けている。しかしWAさえなければ2位になれたのに、と悔しい気持ちが大きい。7問目は数列の平均値が\frac K 2になるらしく、これを使うと僕がWolframAlphaで出した式が直接得られるようだ。9問目の微妙に小さい制約は、Mo's Algorithmが想定されていたらしい。当時少し考えて棄却した覚えがある。今改めて考えなおしてみると、確かにそうだなあという気持ちにしかならない。なぜ思いつかなかったのか……。

午前1時からCodeChef、10月のCook-Offに出た。これで今日のコンテストは合計10時間半になる。それなりに全力投球していた結果頭が回らなくなったらしく、C問題でめちゃくちゃ詰まってペナルティが崩壊した。全完もできず、div.2で3位と残念な結果に。

https://www.codechef.com/COOK134B

ABはよい。Cは斜めにつながってボードを横断（あるいは縦断）しているマスがあるかチェックすればよいと思うも、右と下にしか進めないという制約から、微妙に繋がっていないマスたちによってもたどり着けなくなってしまうのではないかと心配になり、結局「存在できる区間」をvectorで持って更新していった。この区間は高々2つにしか分かれない。

コンテストが始まったときはEの位置にあった気がするDについて（もしかして、こうやって問題の順番が変わるのでみんな問題名で呼んでいるのか）は、Xを聞くとN\mid X-(X\bmod{N})が求まるということで、これを2種類行ってgcdを取ることにした。単純にX=2\times 10^{18}とX-1だと不可能、XとX-(X\bmod{N})-1ならうまくいくようだ。コンテスト後にTLを見て、(X-(X\bmod{N})-1)\bmod{N}=N-1から直接出せばgcdを計算する必要がなかったことに気づいた。

Eは適当に左右の警官でそれぞれ偶奇が異なるものが連続している人数を数えて出力したら通った。Fはfunctional graphの閉路を縮約することになって、使用回数が残り1回の頂点を直前の頂点に吸収させるという操作をstackを使って行った。GはO(N^2)のdpを書いて出力し、OEISに投げるも見つからず、結局解けなかった。どうやら出力結果の比を取るとエスパーできるらしい。

朝方まで日記を書いていた。今週の週記は、過去の週記の引用部分を除き、実際に逆接の「が」を1つも使わず書けたはず。代わりに「しかし」や「～ものの」といった語彙が増えている。思うに、文章を切ろうと思えば切れる箇所でも安穏と「が」を使っていたのがよくなかったのだろう。しかし一方で、文章を切るのが不自然な箇所も存在し、そこにはやはり「が」が入らなければスッキリしないのであった。というわけで、今週の週記には（自分にとって）不自然に文章が切れている箇所がいくつか存在する。来週からはまた「が」も使って書くことにしよう。

週記（2021/10/11-2021/10/17）

10/11(月)

先週はかなり久しぶり（あるいは初めて？）に、日付が変わる前に週記を投稿した。その後は人の日記を読んだり、ちょっとコードゴルフをして、布団に入った。新しく1作ハーメルンを開いて読もうとしたが眠気には勝てず、いつの間にか寝落ちしていたらしい。直前まで意識を保っていて、寝る前には就寝報告のツイートをするぞと心に決めていたのに、本当に一瞬で意識を落としたらしい。

Chromeの履歴からは、午前2時過ぎに寝落ちしたことが分かった。

午前8時頃目を覚ます。どう考えても睡眠時間は足りていないのだからすぐ眠れば良かったのに、昨日読み始めたハーメルンを開いてしまった。そしてそのまま、なんと午後0時半まで延々読み続けていたようだ。1話当たりの文字数こそ少ないものの、実に150話近くを読み進めた。眠気が耐え難くなってきたこと、一方夕方からインターン先の定例会があることを鑑み、この時間には寝ておかなければならないだろうということで、頑張ってハーメルンを切り上げて寝た。

次に、午後3時半に起床。午後2時から30分おきに目覚ましをかけていたはずだが、眠すぎて結局この時間まで起きられなかった。先週はインターンの進捗を全く生やせていないため、今日の定例会の前に少しでも進めておこうと思ったが、すべてが無に帰した。仕方ないので内容がない進捗報告のスライドを作った。それを発表して、特に何も言われることなく終了。

定例会やそれに付随する諸々が終了して、そこで話した内容からちょっと業務モチベが上がったのだが、ハーメルンの前に人は無力。また開いて先ほどの続きから読み始めた。午後9時から2時間読んで、途中でうっかり布団に移動したのがまずかったのか、また寝てしまった。

午前1時起床。atgolferの更新を見てしばらく頑張っていたが、どれも縮められなかった。またハーメルンの続きを読み進める。パソコンの前と布団を往復しつつ、なんと午前7時半までかけて現在の最新話まで一気読みしてしまった。

syosetu.org

「俺は竈の女神様」。原作が「ダンジョンに出会いを求めるのは間違っているだろうか」というまだ触れたことのない作品でちょっと敬遠していたのだが、ちょうどダンまちが始まるあたりでエタっているということで、読んでみると前半分はほとんどオリジナルだった。後半はクロスオーバーが主軸だが、それも知っている作品が多く、問題なく読めた。最初はクロスオーバーだと気づいておらず、ダンまちの二次創作だと言っているのに東方古代スタートが始まりそうになったときはびっくりしたものだ。

内容は非常に面白い。少し前にハーメルンの捜索掲示板を漁っていた時期があったが、その頃「上位存在」みたいなワードの捜索に頻繁に登場していた作品で、その名に恥じぬ立派な上位存在っぷりであった。ただ人の発展を見守っているかというとあんまりそんな感じはせず、同じく上位存在たちとワイワイしていた、という印象。もちろん信仰を集めたり畏敬されたりという描写はあったものの、メインではなかった。

しかし、Fate/系の話はどこにでも出てくるものだ。他の作品でも、何の脈絡もなく「作品キャラがサーヴァント化したら」みたいな文脈で謎の展開が挿入されることがあって、そのたびにほとんど知識のない自分は読み飛ばし気味になっていたのだった。しかし、しょうがないのかもしれない。ゲームもプレイしないしアニメも漫画も見ない自分であってさえ、主にはTwitterで流れてくる絵経由で、伝説上の人物たちのビジュアルをFate/系列のもので固定しつつある。影響力が大きすぎるのだ。

エゴサーチをしていたら、去年のTCO Regionalで僕がACRushと1対1を行い、勝利したことについて言及している中国語の投稿を発見した。競プロ歴10年以上のACRushに対して僕のことは「后浪」、検索すると「新人」のような言葉で表現されていて、むず痒い気持ちになった。まだICPCも現役であるのだから、心だけでも若くあらねばならない。

zhuanlan.zhihu.com

なんとなく興が乗ったので、インターンの業務に手を付けることにした。とりあえず1つモデルを実装してみる。本当はそれくらいで切り上げるつもりだったのだが、思ったよりうまくいったし、学習自体もデータ数を絞ることで短いスパンで試せるので楽しくなって、昼過ぎまで延々コーディングしていた。今日は1on1の予定があったわけではなかったのだが、無理を言って昼から急に予定を入れてもらい、今日コーディングしていた成果を報告した。またいくつか疑問点を解消したり、自分の認識の正しさを確かめたりした後、次に進めることを決めて終了。

学習を進めればランダム値の具合によらず一定の結果を出すものだと思っていたが、うっかり同じプログラムを何回も回してしまうことがあって、その結果が思ったより異なっていたので、モデルの性能を評価するために乱数のシード値などを固定することにした。randomやnp.random、torchのシード値を設定し、torch.backends.cudnn.deterministicをTrueに設定することで結果が一致したモデルと、それでもなお一致しなかったモデルがある。後者はライブラリを呼び出しているだけなので、その中で何かやっているのだろうか。

日記を書いてから布団に入り、ハーメルンを開いたが、すぐに寝落ちしてしまった。午後4時だった。

10/12(火)

午後9時半起床。またしばらくハーメルンを読んでいたものの、その作品は序盤で読むのを止めてしまった。

ハリーポッター二次創作だったが、どうやら連作のクロスオーバーの一部らしく、主人公が別作品由来で、しかもそこからいくつもの二次創作を経てチート能力を身に着けてきた……という設定らしい。こういうのも最初から読んでいけば受け入れられないことはないだろうが、見た感じ僕の知らない作品ばかり渡り歩いているようで、読む気にはならなかった。さらにチート能力を振りかざして原作キャラをおちょくっているのもあまり気に入らなかった。

食事して午後11時半からCodeChef Starters 15 div.2……と思ったら15分こどふぉった。

https://www.codechef.com/START15B

全完して優勝した。1766→1969(+203)。div.2を抜けるにはあと1回コンテストに参加する必要があるようだ。

Aはよい。Bは109以下の数を2000回素因数分解する必要があったので、念のため\sqrt{10^9}以下の素数を求めておいた。3500個程度しかないらしいので、余裕で通る。冷静になると毎回\sqrt{10^9}まで見ても間に合いそうだ。Cは上位桁から貪欲。

Dは面白かった。f(R)-f(L-1)として答えを求めることを考える。下の桁を担当する値を決めると、上の桁として対応させられる値の上限が決まるので、これをソートして尺取り。実際は尺取りでなくても二分探索で通ったようだ。Eは自明、Fは面倒な木dp。Fの遷移を書くのに少し手間取り、これでは優勝できない！と焦っていたが、ふたを開けてみると僕が全完した時点では5完すら他にいなかったようだ。div.2に限らなければ、unratedで参加した中の優勝者は僕より先に全完している。

div.3用の問題を含めて全部解いても1時間もかからなかったが、そのあとTwitterを見たり順位表を眺めてニヨニヨしたりして、結局さらに1時間くらいを無駄にした。

火曜日5限の講義の課題をこなす。Pythonで積分値をできるだけ正確に数値計算せよというものだった。提出方法が面白くて、すでにGoogle Colabと連携された.ipynbファイルが用意されており、それを開いて編集するらしい。Google Classroomを使っていてこそのシームレスさという感じがする。数値計算については、講義スライドにDE法というのが載っていたので、それを適当に書いておけばよさそう。

DE法は実は初めて聞いたが、なかなか興味深かった。幅が有限の区間を無限の区間に置き換えていると思ったが、そもそも幅が有限だからといって結局内部の点は無限個あるのか。また無限の区間であっても、端のほうの重要度をうまいことほぼゼロにしているのも面白い。数式としてみればその理屈もわからないことはないが、実際に計算して精度が上がるのは結構びっくり。

また布団に入って少しハーメルンを読もうとしたが、眠気が強い。午前4時半就寝。

10/13(水)

午前8時前に起床。夢うつつながら、頭皮のかゆみに耐えかねて頭をかきむしった記憶がある。実際枕が毛だらけになっていたので、手で払い落し、いまだ気になるかゆみを抑えるべくシャワーを浴びた。

火曜日の昼間1on1が終わってから（つまり日記では月曜日）回していた学習の途中経過、具体的にはLossの変化をグラフにした。こういうちょっとした作業もやる気が出ないと全然手を付けられない。しかしグラフにしてみてみるとなかなか綺麗な曲線だったので、報われた感じがした。

しばらくパソコンを触ってから布団に戻る。寝ようとしたが眠れず、スマホをずっと触っていた。途中腹を壊したりして、さすがに夏も終わったのにブランケット1枚で寝るのは無謀だったと反省。そのうち気合を入れて掛布団を引っ張り出しておきたい。そのままハーメルンを読んでいたが、正午あたりにやってきた眠気に身を任せ就寝。

次に目を覚ましたら午後7時になっていた。せっかく朝起きたのでゲーセンにでも行くつもりだったのに思いっきり寝てしまった。まあ今日は天気もあまりよくなかったようだし、その点はセーフか。ちょっと食事してからまた布団でハーメルンを読み続け、午後11時過ぎになって身を起こした。

atgolferにPAST8の問題が流れてきていた。いつの間にかPAST8がAtCoderのトップページに表示されるようになっていたらしい。どうせ表示されないのはただの設定ミスだろうと思って、専用でクロールするような設定は入れなかった。

午後11時35分からCF #748 div.3。全完3位。

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

Aはよい。Bはちょっとびっくりするが、下2桁を全探索すればよい。正数を探す必要があるので、下2桁が00だったりしたらどうするのか、という気持ちになるが、与えられる数字にleading zeroが存在しないという制約から、00を選んだとしてもその左にちゃんと非ゼロの数字が存在してくれる。Cは、猫がn-1にたどり着く前に穴に入れるネズミの数を数えればよく、これは穴までの距離が短いものから貪欲に取ることで達成できる。最初n-1ではなくnで計算していて、適当に1引いたらサンプルが合って困ったが、ちゃんと自分で納得できて提出した。D1は差のgcd。

D2は答えを全探索する。ある値gが答えになることは、a_i\bmod{g}を集計して\frac n 2個以上が同じであるか？によって判定できる。この判定はmapの代わりに配列を使えばO(n)で可能なので、それを2\times 10^6回行う。\sum n\le 100という制約から変数による剰余の計算を2\times 10^8回行うことになってしまいかなりドキドキしたが、エイヤと出すと780msで通った。Eは葉から多始点bfsかと思ったが、落ちた。冷静になると、トポロジカルソートにおけるキューに入れるタイミングを次数1以下になったときと定めたような計算をする必要があった。Fは桁dp。Gは、'['または']'のあるインデックスを偶奇に分けてカウントし、それらが同じになることがコスト0で正しいかっこ列に変化させられることの必要十分条件。累積和で求まる。

全完した後しばらくTwitterを見ていたはずだが、いつの間にか布団に倒れこんで寝たらしい。Chromeの閲覧履歴によれば、午前1時半に寝落ちしたようだ。その直前に開いていたページはTLに流れてきたブログ記事で、確かに布団に寝ころびながらそれを開いて読み始めた記憶がないでもない。

10/14(木)

意識を取り戻したのは午前6時だった。またスマホを触ってハーメルンを読み続けていた。

午前10時くらいになって、無理やり切り上げて布団から出た。今日はゲームセンターに行く。夕方から1on1があるので、それに向けて今のうちに何らかの進捗を捻り出しておくことにした。ちょっと気合いを入れれば終わるようなタスクを1つ片づけて切り上げ、しばらくパソコンを触ったあと、出かけた。

東北大学川内キャンパスの近くの交差点は、朝から夕方まで歩車分離式になっているが、交差点を斜めに渡るような横断歩道がペイントされていないため、斜め横断は常に不可能である。ほとんど無視されているような規則だが、定期的に警官が交差点に立っており、斜め横断を見るや否や止めて注意するという光景が見られる。大学生活4年目にして初めてこれに引っかかった。これまでは、自分の前を走る人が止められているのを見てギリギリで警官に気づいたりしたが、それでもセーフだったのに。

食事してゲーセン。今日は新しい靴を履いていたのだが、足首の前のほうに余裕がなく、前方に体重をかけてゲームをプレイしていると靴が食い込んで痛かった。東方の新曲については、先週譜面動画を見ながら難しそうだと言っていたが、案の定13の2つはAJが出なかった。

今日アップデートでチュウニズムに追加された新曲の譜面動画を見ていた。13に追加された2つがどちらもかなり強めに感じられる。AJは難しそうだ。

週記（2021/10/04-2021/10/10） - kotatsugameの日記

理論値が1譜面増えた。前回ゲーセンに行ったときに狙っていたもの。

午後4時過ぎにゲーセンを出る。食事でもしようかと思ったが、あまりおなかが空いていなかったのでそのまま帰宅し、シャワーを浴びて午後5時から1on1。前半で進捗を報告した後は、扱っているデータの様子と学習結果を見て次回までの課題を決める。ビジュアライズするのにちょっとしたコードを書く必要があって、すぐ書けるので今書いてお見せします！と自信満々に宣言したはいいものの、設計がすぐに思い浮かばずしばらく手が止まってしまうなど、情けない場面があった。

1on1が終わってからも少しコーディングを続けていたが、学習を回して放置するフェーズに入ったので切り上げた。しばらくYouTubeを見てから布団に入ってしまい、すぐ寝落ち。午後7時半だった。午後8時半に一瞬起きてTLを見たような記録があるが、またすぐ寝たようだ。

10/15(金)

午前2時起床。夢を見た。

またずっとハーメルンを読んでいたが、今日は夕方から院試ゼミのメンバーで飲み会をする予定。午前10時くらいになって、さすがにもう一度寝ないとまずいという気持ちになり、目を閉じてみた。しかし眠れない。結局起きることにして、とりあえず学食に行った。

昨日寝る前に回していた学習が終了していたので、結果をちょっと加工した後、パラメータを弄ってまた学習を回し始めた。この作業は10分もかからないものなので、勤務時間の記録にどう入れたものか悩む。今後学習のための時間が長くなっていったらどうすればいいのだろうか。

僕が本格的に稼働し始めた3週間くらい前から、インターン先のSlackに自分の名前がついた（ほとんど専用の）チャンネルを用意してもらっている。業務の進捗とかはTwitterと同じ感じでそこに投げ入れているが、これは自分の性にかなり合っていると感じる。そういうチャンネルは他の社員の方も持っている。以下の記事のような運用になっているのだろう。

Slackで簡単に「日報」ならぬ「分報」をチームで実現する3ステップ 〜Problemが10分で解決するチャットを作ろう〜 - 株式会社クラフトマンソフトウェア

日記を書いていたが、かなり眠くなってきてしまった。飲み会は午後5時からで今ならまだギリギリ間に合うと信じて、昼寝することにした。睡眠の周期を考えて90分後に起きることにして、午後2時過ぎに横になった。

実際にはこのツイートをした後も布団の上で眠気に耐えようとしばらくクネクネしていた。なんとか身を起こして午後4時過ぎに家を出た。店の位置と地下鉄の駅の位置をあまりよく分かっておらず、歩いたほうが早かったかもしれないところを、うっかり地下鉄に乗ってしまった。せっかくお金を払うのだからと思って2駅ほど乗ってゲーセンの最寄駅まで行ったが、1プレイする時間はなく、そのまま店まで歩いて行った。思ったより遠くて、結局地下鉄1駅分くらいは歩いて戻ったらしい。店はここ↓。

http://wabisuke.style.coocan.jp/

店の前につくと他の3人はすでに揃っていて、即座に入店。予約の関係で2時間しかいられなかったが、せり鍋に加えて海鮮サラダ、魚のから揚げ（何の魚だったか忘れた）、馬刺しなどを注文。また日本酒も店のおすすめなどを含めて3種類、それぞれ1合ずつ注文した。院試お疲れ様会ということで少し高めのお店にするべくここが選ばれたが、実際1人4000円くらいで、自費で飲み食いした中ではかなり高いほうだった。

おいしいのだろうとは思うが、味をあまり気にしていなかったためよくわからない。量については腹6分目という感じか。女将が鍋を差配しつつあれこれ話していて、そういうタイプの接客も初めて受けるもので高級感を感じる。話の内容はせり鍋の蘊蓄、来店した有名人、店でやっている落語の寄席、くらいだっただろうか。これも途中から興味を失ってしまった。以上、店についてネガティブな言い方をしてしまったが、しかし4人でお酒を飲みながら話すのは非常に楽しかった。

最初は焼肉屋に行こうという話で、僕が以前腹痛で救急車を呼んでしまったためちょっとトラウマ……と言ってこの店に変えてもらった経緯がある。多分焼肉屋のほうが飲み食いしながら話すという目的には合致していたのだろう。またそのうち別のお店に行こうという話になったので、もし焼肉屋に行った場合はちゃんと肉を焼くこと、生肉をつかむトングを分けることを徹底したい。

飲み足りないので2軒目に行く。以前2週連続で行った、1杯200円のバー。今日も注文の内容をリプライツリーにまとめた。

先週の金曜日にも行ったバーに再度入店した。

週記（2021/02/22-2021/02/28） - kotatsugameの日記

飲みながら今日もまたソートなぞなぞをしていた。QuizKnockの動画から知った人もいてびっくり。競プロer特有の文化かもしれないと心配していたが、問題なく楽しんでもらえたようでよかった。出題されたものは記録をとっていないのであらかた忘れてしまった。

店を出て別れ、ゲーセンに駆け込んで閉店まで1時間弱プレイした。これまでの感覚から言えばそこまで酔っているわけでもなかったようだったが、それでも本調子でないことは確かで、ただただスコアが出なかった。閉店後地下鉄の駅に向かって歩いているとマックが見えてきて、なんとなく入店してしまった。ポテトのLとコーラのMを頼んだが、お酒で腹を下し気味だったので、コーラのほうはSサイズでよかった。ポテトをつまみつつしばらくハーメルンを読んでいた。マックのトイレを借りるかと思ったが、明らかに泥酔している人が出てきたため敬遠して帰宅。終電もなくなっていたため、延々歩いて帰ってきた。

シャワーを浴びて布団に入り、すぐ寝た。午前2時前だった。

10/16(土)

午前9時前に目を覚まし、またハーメルンを読んでいた。今日は午後2時まで読んで、ARCに備えてまた寝た。午後4時くらいに生協の弁当配達があって一瞬起きたが、この時はまたすぐ寝ることに成功した。

午後8時起床。atgolferを確認すると、マラソンのコンテストで同じ問題3問×本選とオープンの合計6問が一気に更新されていてひっくり返った。3問あるのはいいけども、なぜ問題idを変えたのか……。どうしようもないので眺めてしみじみしつつ、午後9時からARC128に出た。

Daiwa Securities Co. Ltd. Programming Contest 2021（AtCoder Regular Contest 128） - AtCoder

3完遅めで何もかもが崩壊した。最近ヤバい。

Aから難しい。A_iのうち最も値が大きいものを考えると、その右（つまりそれ以降）にまだ交換しない日があるなら、そのうちA_iが最小の日と組みにして交換することにしても損しない。以降は選んだ組を無視して同じことを繰り返すが、銀に交換→金に交換というステップの繰り返しを崩さないように最小値を検索する範囲を制限して行う。選んだ最大値より最小値のほうが大きくなったら切り上げる。Bはつい最近インターン先の勉強会でほぼ同じ問題が扱われており、難なく解けた。といってもA問題をACしてからの時間を見る限りFAは僕より1分以上速いらしく、頭が回っていないなあという感じ。

……このツイートを引用するかどうかは迷ったのだが、多分ちょっと調べるとわかる情報だろう。

C問題は難しかった。d_i=x_i-x_{i-1}などと置いて書き換えてみても、あまり見通しは良くならない。しばらく唸っていたがどうしようもないので、元の問題に戻って解の形を考えてみると、どうにもd_i\ne 0なるiは少ないんじゃないかという気持ちになる。N\le 5000ということもあり、d_i\ne 0なるiを2つ決め打って計算するO(N^2)のコードを書いたら通ってしまった。誰かのツイートで見た言葉だが、問題を解釈して一般的な問題に落とし込むと元の問題の構造が失われてしまうことがある。今回はその一例だったかもしれない。

Dは解けなかった。隣接する要素が等しい位置で数列を区切り、それぞれ解くことにして、解き方はdp、更新先が区間になるだろうというところまで考えた。その更新の区間を求めるコードが全然違っていたようで、半分くらいのケースで落ちるようなコードしか書けなかった。スタート地点からある程度先「まで」の区間に対して更新するだろうと考えていたが、TLを見る感じある程度先「以降」の区間に対して更新するようだ。なんてこった。

コードゴルフをする。AはOctaveで、まず数列のdiffを取り、それが0より大かどうかの列を作ってまたdiffを取るようなアルゴリズムで解ける。BはRuby。高度な機能を持ち出して全探索するより、ソートして場合分けを並べたほうが短くなってびっくりした。Cは線形計画問題なのでOctaveのglpkで解けるようだ。

夜中CodeChefのSnackdownにレジってQualの問題を解いた。来週火曜日までで、週記を投稿する予定の日にまだ終わっていないため、ここでは何も言わない。

最近熱心に読んでいたハーメルンを読了。「阿礼狂いに生まれた少年のお話」。

syosetu.org

非っ常～～～に良かった。設定についてもオリキャラと原作キャラの繋がりがいろいろあって楽しめたし、前半分のほうは主人公の強さも印象的だったが、後に行くにつれて、そうした表面的な面白さの奥に潜む主人公と周囲の人妖の関わりの物語がだんだん現れてきたように感じられた。特に阿求の章に入ってからは、すぐそこまで迫った主人公の寿命があり、その中で友誼を結んだ妖怪にとっての死別のとらえ方だったり、人里の先立った人・残される人とのやり取りだったりが感傷的に描かれていた。ラストで主人公が亡くなり終了かと思ったら、幕間という形で亡くなった直後の幻想郷の様子が描かれ、僕はそういうのに弱いので泣いてしまった。

朝方はずっとコードゴルフをしていた。今日起きた時にatgolferに流れてきていた更新は取り返せなかったが、ちょっと前のコードをずっとタブに開いていて、改めて考えていたら少し縮めることができた。その後日記を書いたら午前11時だったので、布団に入る。今まで夏用のブランケット1枚を引っ被って寝ていたが、さすがに寒くなってきたので、秋用の掛け布団を出すことにした。布団カバーをかぶせてみると微妙にサイズが合っていないように見えるので、もしかしたら冬用の布団のカバーを出してしまったのかもしれないが、今更戻すのも面倒。

布団に入って昼過ぎまでハーメルンを読んでいた。TLを見て、日曜日の昼からJOI一次予選（第2回）があることを知った。第1回は大体1月前に開催されたが、その時は予選が終わって1時間もしないうちにAtCoderに過去問が公開されて、起きたころには自明な最短はすでに取られていたのだった。

今日の昼頃行われたJOI一次予選の問題が2時間前に公開されていてびっくりした。

週記（2021/09/13-2021/09/19） - kotatsugameの日記

今回はそんな失敗をしないようにしたい、ということでもうすぐにでも寝て、午後4時くらいに起きることにした。午後1時就寝。

10/17(日)

午後4時起床。まだJOIの問題はAtCoderで公開されていない。非常に眠いので寝たい気持ちが強いが、そうしている間に公開されたら悔しいので、頑張って起きていることにした。この時点では、公開されたらすぐ取り掛かって、ABCまでまたしばらく寝ようと考えていた。

atgolferの更新を見ながらコードゴルフしていたが、一向に公開される気配がない。コードゴルフでは、gets.bytesが$<.bytesに置き換えられることに気づき、検索するとこれで縮むコードが結構あったので拾ったりしていた。午後7時あたりでいったん切り上げて日記を書き、午後9時からはABC223に出た。実は今日は午後8時からCFでcombinedがあったのだが、ABCと被っていたので見送ってしまった。

AtCoder Beginner Contest 223 - AtCoder

A問題はちょっとひっかけ気味。0円に対してはNoと答える必要がある。逆にこの設定があると、正規表現/00/にマッチすることがYesと答える場合の必要十分条件となってくれる。最初は/00$/でないとダメだと思っていたが、入力される値の最大値が1000なので/00/でよい。B問題はRubyで書いた。

CからはC++。距離を二分探索して、左右からそれぞれかかる時間の差が0になる点を見つけた。Dはトポロジカルソート。Eは↓の問題からの類推で試すべき敷き詰め方のパターンを予測し、対称性からループなどでまとめて書いたらかなりスッキリした。Fは遅延セグメント木で括弧列を±1に直した累積和を持つ。Gは木の最大マッチングが葉から貪欲でよいことを元に全方位木dp。HはDisjoint Sparse Tableを貼ったがマージに602回くらいの計算が必要で、そこをどうしても落とせなかった。

atcoder.jp

もう結構な期間ゆっくり実況を出していないが、一応AtCoderのコンテストに参加するときは画面キャプチャを撮っている。撮っているつもりだったのだが、最近3回分でサブモニタがキャプチャされているのに気づき、非常に残念な気持ちになった。以前同じ現象が発生して、ちゃんと直したはずだったのだが……。パソコンを再起動すると元に戻ってしまうとか、そういうことだろうか。以前とは使っているケーブルもモニタも変わっていないはずなのだが、抜き差しすることに副作用があるのか？

ふと思い立って画面キャプチャのテストをしてみたところ、これまで真ん中のメイン画面をキャプチャできていたのが、いつの間にか左端の画面をキャプチャするようになってしまっていた。

週記（2021/09/13-2021/09/19） - kotatsugameの日記

コードゴルフ。Aはsedでよい。BはRubyで頑張っていたが、コンテストが終わってみるとVim 25Bがあって何も勝てないという気持ちに。Cは2つの火がぶつかる時間が\frac 1 2\sum \frac{A_i}{B_i}と求まることを解説を読んで知った。これを使ってdcで頑張って現在52B。符号を弄ったり式変形を繰り返した結果、なぜこれで答えが出るのか自分でもよくわからないコードになった。

DはPythonでheapqを使う問題に見えていたが、提出を眺めているとRubyでbsearch_indexとinsertを使ったコードがギリギリ通っているのを見つけた。実際書いてみると、たまにTLEするものの数回出せば確実に通っていく。そのコードを縮めることにした。連想配列を使うような書き換えをしているとC++脳ではlogがついて遅そうに見えるが、Rubyのそれはhash mapなので思ったより速かった。

Eはパターンをまとめて頑張る。.permutation.any?を3段に重ねるようなコードを書いた。どの長方形を固定するか、縦横どちらに固定するか、残りの2つを縦横どう置くか。コードを文字列のjoinで作ってevalしていたが、入力読み込みのときに改行がついてくるのに気づかず不要なセミコロンを入れており1B負けてしまった。あとは手付かず。

最短コードが1700問になった。

今日が終わってしまったが、まだJOIの問題は公開されていない。せっかく頑張って起きたのに……という気持ちもあるが、今週は生活リズムを崩し続けた一週間だったため、最後にこのような形で多少整ったのは不幸中の幸いか。せっかくなので空が白み始める前に寝たいものだ。

週記（2021/10/04-2021/10/10）

10/04(月)

正午起床。寝ている間に大学院科目の先行履修の書類が受理されたとのメールが来ていた。一安心。

手癖でYouTubeを開くと、チュウニズム14新曲のAJ動画が投稿されていた。2人目が出たらしい。

www.youtube.com

シャワーを浴びて学食に行く。先週金曜日から秋学期が始まったということで生協の営業時間も更新されており、学食の昼の部は30分伸びて午後2時まで営業しているので、かなり余裕があった。帰ってきてから1時間くらいかけて溜めていた分の日記を書き、投稿した。

それから夕方のインターン先の定例会までは、それに向けた作業をしていた。とりあえず進捗報告用のスライドを1ページ用意する。さらに、先週Kaggleのチームを組んでから何もしていないのに罪悪感を覚えるので、とりあえずコードを手元で動かしたりしてみていた。入力データを絞ってちょっと実行するだけでも結構時間がかかって辛い。

定例会は今週も普通に終了。続いてKaggleチームのミーティングも行われ、そこで少しばかり質問した結果、どんなコードのどこを弄ればよいのかが分かった。一般に特徴量を増やす関数としてadd_featuresがどこかで定義されており、ここでオレオレ特徴量を入れて学習を回しスコアを見るのだとばかり思っていたが、それももちろん重要な一方で、モデルをいろいろ弄ってみるのも、最後にチーム全員のモデルをアンサンブルするため必要なステップらしい。魔法の特徴量は見つかったら根本的にスコアに影響を与えるものの、そう簡単に見つかるわけがないから、チームに貢献したいならモデルのほうでいろいろ試してみるべきかもしれない。

機械学習のPythonコードを手元でいろいろ変えつつ動かすのは、いちいち先頭から実行しなおす手間がかかってさすがに耐えられないため、ローカルにJupyterを入れた。試しに起動してみるとかなりいい感じ。大学のPythonを扱う講義ではいっつもGoogle Colaboratoryを使わされるが、似たようなものがローカルで動いていると感動を覚える。それでもらってきた.ipynbファイルを開き、自分の環境に合わせて少し書き直した上で走らせてみた。依然として実行に時間がかかるのが嫌なので、とりあえずデータ量を絞っていたところ、生成されるべきファイルがないというエラーが出て困っていたが、それもちょっとした手直しで解決して、一通りは動くようになった。

と、かなり良い感じになってきたがここでいったん放置して、4年ゼミのスライド準備を始めた。教科書のキリの良いところまで行間を埋めることに成功したので、Beamerを使い体裁を整えながら打ち込んでいく。あまりに久しぶりすぎていろいろ忘れてしまっていたが、これまで用意してきたTeXファイルを見ながら書いていった。5時間くらいかけて、とりあえず読んでおいた部分のスライドが完成。教科書のページ数としても、スライドの枚数としても、発表のためにはこの2倍弱の分量が必要だろう。しかし教科書の次の部分は章末の演習問題である。これまでのゼミでは、演習問題はみんな無視してきたが、そうはいってもとりあえず目を通しておくくらいはするべきだろう。そうして読んで、やっぱりやらなくていいかな……という気持ちになったので、次の章に入ることにした。次の章の内容は幾分簡単そうに見えるので、どうにでもなるだろうと思って今日はここで切り上げた。

明日は1on1の予定だが、前回金曜日から一切業務に手を付けていない。学業に専念している感じなので仕方ない、明日は正直に何もやっていませんと言うことにした。インターン先は良い会社なので、学業を優先させてくれるのだが、そうはいっても何も言わず急に業務を放り出すのはよくないだろう。これからは事前に、この時期は学業で忙しくしています、ということを報告しておきたい。

14AJの手元がまた1本投稿されていた。結構前からずっと追っているチャンネル。99AJでもうなんか全てがすごい。

www.youtube.com

今日は夕方かなり眠気があったつもりだったが、それでもいつの間にか午前4時過ぎまで起きてしまっていた。夜更かしが本当に常態化しておりまずい。とりあえず完全に朝になる前に……と布団に潜り込み、午前5時過ぎ就寝。

10/05(火)

午前11時前に目を覚ます。TLをちょっと眺めていたら眠れなくなって困っていたが、気合を入れると再度意識を落とすことに成功した。確かそれが午後1時過ぎのことだったと思う。

午後2時半、1on1前の目覚ましで起床。起き抜けはかなり頭がボーッとして身動きが取れなかった。途中分割されているものの、合計の睡眠時間だけ見れば結構寝ているので、深い睡眠から無理やり起きてしまったのだろうか。ちょっと怖い夢を見たが、すでに細部は失われていた。

1on1は10分で終了。次回はゼミが終わった翌日の金曜日にお願いした。さすがに1日くらいあれば何か報告できる進捗が産まれてくれるだろう。

今日の5限に講義を1つ入れたはず、と思ってClassroomを確認したところ、初回である今週は課題なしで、スライドや動画を見るだけ。「AMATERAS RAY」（なかなかかっこいい名前だ）というサービスを使って適当な目的変数を予測してみるという内容で、プログラミングは一切行わなかった。僕らのような素人がGUIでポチポチやっている裏では、サービス提供元の作り上げたごっついモデルが動いているんだろうなあと考えていた。今回の講義で出てきた言葉から自分なりの「キーワード」を探して回答せよという指示だけあったので、「説明変数」と答えておいた。

Service Amateras

大学生協に寄って買い物をしてから、街中に出てゲーセンに行く。その前に腹ごしらえをしようと思い、一閃閣というラーメン屋に行こうとした。この店は仙台に2店舗存在する。自転車を停めた場所がその2店舗からちょうど等距離にあるように思えたので、これまで行ったことのない店舗のほうに行こうと思い、しばらく歩いていたところ、以前この辺りを通りかかったときは閉まっていた「昭文堂書店」という本屋が営業しているのを見つけ、ふらふらと吸い寄せられてしまった。

棚いっぱいに古びた大きな専門書が詰め込まれている、絵に描いたような古本屋さんだった。頭の白くなったおじいさんが店番をしていて、客は僕一人。人文学の本で埋まった棚を眺めつつ、何も買わずに出るのもアレだけど、ここにある本を買ってもなあ……と思っていたが、別の棚に行ってみるとそっちは完全に理系だった。店のちょうど真ん中を境に、いわゆる文系向けの本と理系向けの本が分けられていたようだ。並んだブルーバックスの背表紙にMS-DOSとかC言語とか書いてあるのを見て、これはもう古典だな、と思うなどしていた。数学に関する本やコンピュータに関する本を一通り確認して、「プログラマの数学」という本を購入した。ホスフィンが売り払った本である可能性があるらしい。世間が狭すぎる。

うっかり30分くらい古本屋に吸い込まれていた。出てから改めてラーメン屋を探すと、目の前に建っていたものの、閉まっていた。慌ててホームページを確認すると、どうやら平日は昼間しかやっていないらしい。そんな……と思いつつ、完全に一閃閣の気分になっていたので、一番町まで延々歩いてもう1店舗のほうに向かった。そちらは問題なく営業しており、食事にありつけた。

ゲーセン。新曲の13+、「Love & Justice」を何回かプレイしていたが、SSSは不可能であるという結論に至って放り出した。難しいところは全部8分全押しで通りそうだが、全然安定しなかった。あとは12+のAJを6個99AJに更新し、理論値を1曲出し、13AJを1個出し、さらにもう1曲理論値を狙ったが出せずに終了。

最後のトラックで「TiamaT:F minor」をプレイしたところ、1500点伸びて14では初めてSS+に乗った。序盤の鍵盤を適当に擦って大量失点しているので、ちゃんと運指を考えたらワンチャンあるのかもしれない。

ざるそばを食べて帰宅。帰る途中、大通りから分岐した脇道の横断歩道を一時停止なしで渡ろうとしてしまい、ちょうど横から車が来ており、お互い急ブレーキをかけてギリギリ接触せずに済んだ。なぜ気づかなかったのかなど反省点が多いはずだが、そのときちょうどぼんやりと考え事をしていて記憶が定かではない。

帰宅してちょっとコードゴルフをした後、昨日の分と合わせて日記を書いた。今日は結局ゼミ準備をしなかった。午前4時就寝。

10/06(水)

午後2時頃に目を覚まし、atgolferの更新を見て縮まないかしばらく考えていた。なんとなく縮みそうな気がしたのでいったんパソコンの前に座ったが、しばらく試行錯誤して、途中で別の問題が縮んだりしつつ、元の問題はやはりダメだったことが分かったので、また布団に戻った。

tatyamさんの、PAST8のバチャをツイキャスでするというツイートが流れてきた。慌ててAtCoderのトップページを確認するも、特に表示はされていない。ツイキャスを見ても画面が小さくよくわからなかったので、別の問題を解いているのだろうと勝手に納得して閉じた。しかし、他にもPAST8のバチャに関するツイートをいくつか目にして、試しに以下のURL（過去のPASTから推測できた）を直接打ち込んでみたところ、見事にPAST8のコンテストページが開けてしまった。

https://atcoder.jp/contests/past202109-open

慌ててパソコンの前に戻り、解き始めた。Aのdc 11Bはさすがに自明すぎて取られていた。Bはそもそも負け。Cはdc 22Bを書いたが、この日の夜遅くに21Bに更新された。DはPerl 53B。

Eは自分では綺麗に書けなかったが、Rubyのかなり上手いコードが夕方提出され、そのあまりの美しさにひっくり返っていた。

atcoder.jp

Fは結構頑張ってRuby 78B。GはRubyで二分探索するだけで90B。HはC++で適当に書いて、IはCython。そこから先の問題はそう簡単に縮まなさそうなので、急いで解く必要があったのもこれくらいか。午後6時くらいに一段落したと感じたので学食に行く準備をしたが、やっぱり気になってさらにコードゴルフしている間に学食が閉店してしまった。

PAST8がいつ公開されたのか提出を調べてみると、なんと日付が変わったあたりの提出が存在したことが分かった。なぜAtCoderのトップページに出ていないのか。腹が立ったので愚痴をツイートした。

しばらく別のコードゴルフをしていた。今日の起き抜けに縮んだ問題がさらに大幅に縮められていたので、それを取り返す。しばらく格闘した後にまたPAST8に戻ると、いろいろ縮められていた。先に述べたE問題のコードが提出されているのを見つけたのも確かこの辺りだったはず。他にI問題も縮められていた。I問題に関しては方針を大きく切り替え、先に3倍を繰り返した要素たちの列を作っておいて、全体をソートしてから特定の位置の値を出力することで大きく縮めることに成功した。

さらに問題を解く。JKはC++、LもC++で書いたが、二分探索の中でさらにBITを使ったらTLEしてしまった。logを2つつけたらTLEした、のようなツイートをどこかで見たので、ああこの問題だったのだなと思った。冷静になるとソートして尺取りすれば線形時間で判定が行えるので、それで通した。解説では、尺取りは上端と下端を持つというようなことが書かれているが、実際にはどちらかを今見ているインデックスに合わせておけば区間がそれぞれちょうど一回カウントされるようになり、後から半分にする必要もないし定数倍も半分になってくれる。コードゴルフしようとしたが、RubyではなくCrystalでないと通らないようだったし、そちらも謎のREが出てしまったので放置。

午後9時過ぎ、さすがに明日のゼミ準備がまずい気がしてきたので、そちらに取り掛かった。途中集中力を失ってコードゴルフに戻ったりTLを眺めたりしていたが、午前3時半くらいになって一応の完成を見た。月曜日に進めていた分に比べて、今日やった箇所は章が変わって初めのほうということもあり、かなり簡単め。それでも、教科書で直ちにわかるとか書かれている部分が微妙に怪しく感じられたので、結構丁寧に（あるいはねっとりと）証明を書いた。

ICPCのアカウント設定を済ませる。Activateが必要で最初ログインに失敗したときはちょっとドキッとしたが、問題なく完了した。アカウントに登録する情報について、去年急に「Number of Full-Time STEM Semesters Completed」という項目が増えて困惑したことを覚えている。去年は以下のような理由で5を記入し、そのことを日記にも書いたのだった。

STEMとはScience、Technology、Engineering、Mathematicsのことで、それに関連する学科を指しているのか？とりあえず、僕は数学科で2年半、つまり5セメスター過ごしてきたため、5と書いておいた。

週記（2020/10/12-2020/10/18） - kotatsugameの日記

今年はICPC横浜大会公式ページ最下部のQ&Aにおいて、この項目が初期値0のままでよいと明言されているため、それに合わせておいた。未だに「Number of Full-Time STEM Semesters Completed」で日本語サイトを検索すると僕の上の週記がトップに表示されるため、迷い込んでしまう人のためにそちらにも追記しておこう。

アカウント登録 | ICPC 2021 Asia Yokohama Regional

明日に備えて寝ようと思ったが、ふと思い立って、以前より温めていた短編小説のプロットを書き始めた。核となる競プロ関連のネタはしばらく前に何となく考えていて、加えて最近pixiv小説でテーマが合致した執筆応援プロジェクトとやらが行われているのを知り、以来数日なんとなく想像をたくましくしていたところ、ここにきて急にいろんなシーンが思い浮かんできたので、それを忘れないようメモしようというわけだ。大まかな流れを書いておけば、その適切な位置にシーンをメモ書きの形で挿入し、保存しておくことができる。

しかし、思い浮かんだもののうち覚えていたシーンだけ付け足しつつ書き上げてみると、すでにいい具合のボリュームがある気がする。これをしばらく寝かせて新たに思いついたシーンを挿入するのもよいが、それよりも今は、これを実際の短編小説として出力してみたいという気持ちが大きい。あまりに楽しみすぎて明日早いことを忘れ、4時間かけて完成させてしまった。一読して誤植などはなさそうに見えたため、そのままpixiv小説に投稿した。約8000文字。ちゃんと起承転結を意識したつもりで、12が起、345が承、6が転、7が結だと考えている。

www.pixiv.net

せっかくの日記なので、後書きっぽいことをここに書いておこう。以下の文章には上の短編小説のネタバレが含まれる。

先に話した核となるネタはもちろん、フロアの電気を全部消すスイッチの組み合わせを求める問題である。しかしそこからどういう話にするのかは非常に難しかった。導入はまあどんなものでもよいだろうけど、消した後はどうなるのか。あるいは消す過程を詳細に記述することも考えたが、これもどうもうまくいかない。貪欲などしていてはダメだから、結局基底を取るしかないのである。そこで、電気を全部消したときにビルの隠された空間を知る、という展開を思いついた。すると今度は現実味がなくなった。単純に壁が動いてお宝が……よりはリアルにありそうなことを描きたい。というわけで、全部消したはずの電気がついているという流れで発見されることにした。最初に「奥まったところから光が漏れ出ている」という気づき方を考えたが、ビルのフロア丸々使った1室という舞台に奥まったところを無理なく設定できなかったので没になり、外から見て気づくという流れになるようにした。

ここまで、つまりビルの電気を消し、外から見て隠し部屋に気づくという流れが、考えていたプロットの根幹である。あとは適当に考えたシーンを書き加えただけであり、それをどうやって思いついたかについてはほとんど覚えていない。が、「ビルの電気がついたり消えたりしているのを見て」のくだりはなかなかお気に入りである。実際のところ、フロアの光量が激しく増減しているのを見てもそういう表現にはなると思うが、多少は許してくれよな！という感じだ。相変わらずラストをどうするか決められなかったので、最初はリドルストーリーにするつもりだったが、さすがにそれは放り投げすぎだろうということで、ちょっとばかりショッキングな描写を入れてお茶を濁した。あとは伏線になるように適当に言葉を散りばめて完成。友人の感想では伏線が弱く感じたという話だったが、まあ初めて書いた小説にしては良いだろうと自画自賛しておく。

長さ8000文字は思ったより短く、もうちょっと余計な描写を入れてもよかったかも、と思わないでもない。1、2のあたりではまだ周囲の描写を入れたり、地の文と会話文の量に気を配っていたのが、だんだん文章を書くのに夢中になっていってそういう配慮は姿を消し、自分の書いたプロットに忠実に、必要なことしか書かなくなってしまった。また、自分なりの伏線回収の部分に圏点を打ったのだが、「言う事全部重要おばさん」が思い浮かんでダメだった。

投稿してすぐ、朝にも関わらず数件のいいねやRTが来て嬉しくなった。そのままTLを見ていたい衝動に駆られるが、4時間後にはゼミが開始してしまう。午前9時半就寝。

10/07(木)

午後0時半起床。眠すぎて動けないが無理やりスマホを睨みつけて眠らないようにする。何とか布団を這い出し、食事してゼミに備える。

ゼミ準備としては、スライドを元に口頭で説明したいことを紙にまとめておくのがよいのだった。幸い今日の発表は2番手になったので、1番手が発表している間に見直しを進める。すると証明が壊れていることに気づいてしまったが、教科書の参考文献を試しに検索してみると元論文が見つかったので、それを見て修正。何とか間に合ったが、土壇場の変更をスライドにちゃんと反映しきれていなかったのが悔しいところ。発表している最中に修正点をいくつか見つけたので、逐一メモを取って後から直しておいた。今回もスライドをここに載せておこう。

Apostol_Chapter4_4.10-4.11_Chapter5_5.1-5.2.pdf - Google ドライブ

発表内容としては特に問題なし、だったと思う。記号の読みとかスライドの記法とか、そういう話はいくつかされた。正直次回まで覚えていられるかは……謎。メモとしてここに書き残しておこう。句読点を．と，に置換していたが、これは別に半角でもよく、教科書に合わせて数式にピリオドを付けたりするならば半角のほうが良い。また\hat{a}は「エーハット」と読む。あと、これは僕の宗教を許容されたのだが、量化子付きの命題を書く際に\forall x\in A.\;\varphi(x)とピリオドを付けて書く、一部の数学基礎論で見られる記法についても話題に上がった。

ゼミが終わってから、今日アップデートでチュウニズムに追加された新曲の譜面動画を見ていた。13に追加された2つがどちらもかなり強めに感じられる。AJは難しそうだ。

ゼミ中に部屋のチャイムを鳴らされたが、その時は数十分以上後にまた来てくれと言ってお引き取り願った。夜ごろまた来る、というようなことを言っていたが、午後5時くらいに来たので対応。電力自由化を利用して電力料金を下げないかという話だった。面倒なので断るタイミングを伺いつつ、ついついごみ箱から電力料金のはがきを掘り出して見せたりしていたのだが、その場で入力させられそうになったので直截的に「その気はない」と言った。するとすんなり引き下がってくれたのだが、最後少しの会話で僕が親からの仕送りに頼って暮らしていることを明かすと、そういう人を勧誘してはならない決まりなのだと言う。よくわからない決まりだが、お互いにとって意味のない十数分だったことが明らかになり、ちょっと申し訳ない気分になった。

夕方はTLに人が多いことが期待されるので、昨日投稿した小説のツイートをセルフRT。目論見通り新たに数人がいいねやRTをしてくれて嬉しい。

昨日のPAST8-I問題が、昼頃さらに縮められていたようだ。これはもう、いったい何をしていたのかというレベルの典型の見落とし。非常に悔しい気持ちになった。

今日こそ学食に行く。今日初めてのまともな食事ということで、入るだろうと楽観視して丼の小にラーメンの大を合わせたのだが、全然食べきれなかった。なんとか丼とラーメンの麺だけは腹に収めたが、トッピングのから揚げは見るだけで嫌気がさしてしまったので、残した。うっかり癖で大サイズを注文したのが失敗だった……。少し膨らんだ腹を抱えてえっちらおっちら帰宅した。

しばらくTLを眺めていたが、急激な眠気に襲われて午後8時半くらいにベッドに倒れこみ、そのまま日付が変わったころまで寝ていた。

起きてからしばらくは、以前に読んだなろうの読み返しをしていた。印象深いシーンを思い出して探していたのだが、2500話近くあるとタイトルを眺めて思い出すにも結構限界がある。ずっと遡っていきつつ他のシーンも拾い読みしていたが、実は求めていた話は結構最近のものだったらしい。そういうことを、途中TLを眺めたりしつつ午前5時までやっていた。

今週日曜日のOpenCupがなくなったらしい。これで2週空いたことになる。

朝方、さすがに何もやっていなくてまずい気持ちになったので、とりあえずPASTの残りの問題を解いた。MNO。

Mはなかなか苦行枠で、奇閉路があるなら頂点の値が1つ決まり、そうでないなら適当に定めてチェックすればよいと思っていたが、サンプルを試しているときに負の値が許されていないことに気づいた。幸い修正は容易で、二部グラフの場合のみ自由度があって色が同じ頂点すべてに同時に足してもう一方から引けるので、それで負の値を消そうとしてみればよい。実は「+ Graph」とほぼ同じ問題で、解説の方針も同じだったようだ。

atcoder.jp

Nは明らか。Oは、最初順列が与えられることに気づいていなかったのでしばらく迷走したが、なんとか解けた。ある部分木の値たちは、最終的に誰に負けることになるかが上から見ていくことで決定できるので、それとの大小関係だけ考えればよい。と思っていたら解説はもっと頭がよく、情報が矛盾しないならば勝敗が決まっている戦い以外はどちらが勝ったとしても対応する色の割り当てがただ一つ存在することから、その自由度を計算するだけで木dpっぽいことをせずに解いていた。

O問題をこの方針でコードゴルフして1時間半、さらにL問題のREの原因が添え字の和のオーバーフローであったことに気づき、それを直してさらに縮めるのにまた1時間半使った結果、午前9時になってしまった。明日は午後3時半から1on1で、まだ一切進捗を産んでいないどころか起きられるか怪しい時間になってしまった。急いで布団に入ったが、そこからうっかりハーメルンを1時間読んでしまい、午前10時就寝。

10/08(金)

午後2時半起床。シャワーを浴びたりしているうちに時間は過ぎ、結局ろくな進捗がないまま1on1に突入してしまった。

インターンはそういう契約なのだから、と励ましの言葉をいただいたが、この信用を失うのは怖い。自分ができないことをできると言うべきではないが、自分ができることをしないのはさらに良くない。とにかく今日は、ちょっとした勉強会として機械学習モデルの実装の説明をしていただいて、1時間弱で終了。

10/07(木)の朝方に投稿した短編小説は、一応pixiv小説の執筆応援プロジェクト・テーマ「夜」への応募作品として書いたものであった。昨日数回セルフRTした甲斐あってかPV数がかなり伸びており、確認すると「注目の応募作品」のところに自分の小説が載っていた。これはかなり嬉しいが、ツイッターのFF数と競プロ界隈の内輪ノリを頼みに無理やりPV数を伸ばした印象があって微妙な申し訳なさも感じる。そんな中、競プロ界隈と全くかかわりのなさそうな見ず知らずの人が、どういった経緯でか僕の小説を読んでくれて、面白かったとリプライしてくださったのが一抹の救いになっている。つまり、確実に僕の小説を評価してくださったということがわかるのだ。

1on1が終わってからすぐ大学に向かう。今日はおよそ20か月ぶりに対面でサークル活動が行われるようだ。ちょっと遅刻してしまったが、バチャをやっている静かな中にシュッと入って座り、自分もコーディング。今日のバチャはAOJ-ICPCから星の多い問題を選んだということで、実はほとんど解いたことがあったのでそれを再現するだけになってしまった。最後に初見の問題に挑もうとしたところで時間切れ。

AOJ-ICPCの500点に「薔薇園の魔女」という問題があって、初めて読んでから長い間解けていなかったのだが、今日のバチャで出てしまった。僕は不可能枠だと思っていたので見た瞬間飛ばしたが、1人時間内に解いたサークルメンバーがいて度肝を抜かれた。解法を聞いて感服し、帰ってから通しておいた。細かな実装テクとして、イベントソートして値を管理しつつ最大値を取るものは、値を減らす操作を増やす操作の前に並べると、ソートした後愚直に1つずつ処理していってよい。

AIZU ONLINE JUDGE: Code Review

これで500点の残りは「Spherical Mirrors」と「凸多角形柱工業都市」。両方幾何で逃亡の構え。

午後8時から三連続でコンテストに参加した。まず第一弾としてSRM815。18位で2540→2536(-4)。厳しい。

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

EasyはbitDPやるだけ。制約が50×220で攻めてるな？と感じたが、冷静になれば余裕で間に合うことがわかる。Medは親の顔より見たグリッドを鏡写しに並べていく問題。丁寧丁寧丁寧に実装していたらルームの黄色が何人も僕より先に通していて涙が止まらなかった。Hardはよくわからない。大きい値から適当に貪欲みたいなことを考えていたが、どうにも正当性が信じられない。M^N\le 10^{18}以下という制約を各Nに対して考えてみたが、うまく分けてもどうしようもなさそう。最後に、適当に値の範囲を絞って全探索してみたが、N=7、M=372のケースでTLEしてそのままコンテスト終了。

チャレンジフェーズ前は30位台で、部屋の提出もあんまり落とされなかったので絶望していたが、システスが終わってみるとバカスカ落ちていて18位になった。特に、Medを僕より速く解いた黄色が何人も落ちていて、ひどい話だが安心してしまった。別に僕がチンタラやっていたわけじゃなかったのだ。ただレートは下がってしまった。

次にyukicoder 317。全完。

yukicoder contest 317 - yukicoder

Aはよい。Bはdcで殴ってしまった。Cは全探索だが、0個の品物を選んでしまい1WA。Dは左右からdpしてマージ。Eは男女それぞれ誰まで見たかを持つdpで、遷移で頓珍漢なことをしており1WA。Fはそれぞれのバス停にいる確率の遷移行列を累乗するが、このとき1単位時間先の確率も持っておく必要がある。Gはセグ木。HはFでバス停3つを区別していたのを、バス停1とそれ以外の2つに分けて行列累乗し、1台だけ見たときバス停1以外にバスがいる確率を求めてM乗し、1から引けばよい。

Hはかなり面白く感じられた。ただ問題文が正確でない・（一般的な書き方をしていないため）読みにくい、という理由でコンテストに対してはネガティブな印象を抱いた。CとEが特別にひどく、TLではDの良い部分列の定義も不必要であると槍玉に挙がっていた。コンテスト後にいくらか改定されたようだが、この日記を書いている時点でやはりまだ読みにくく感じられる。こういうものはテスターが排除するべきではなかったのか。特にE問題は、問題文を忠実に解釈すると絶対に以下のツイート（Cと書いたがEである）の質問文のような解釈になるはずである、が、修正を執拗に迫るほどの熱意もないので、愚痴るだけ愚痴って放置。

さらにCF #747 div.2。途中寝てしまったが何とか全完。

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

Aはギャグ。Bはkを2進数展開してn進数として解釈する。Cは2回あれば全部の要素を操作できるので、1回以下でできるかを全探索。Dは各人に対応して真偽の頂点を作り、辺を張る。このグラフの作り方は実質2-SATだが、辺の特徴から真の人数、あるいは偽の人数を最大化できるということで、このことは直接グラフを作りに行ったほうがわかりやすい。E1は根が6通り、あとは上から見ていくとき一度分かれるとその後は独立だから、各頂点で4通りの自由度がある。指数を10^9+6で割った余りを計算したが、別にその必要もなかったようだ。

E2は面倒。自由度が4とならないような頂点たちは、すでに色が決まった頂点とその祖先たちだけで、高々O(nk)頂点しかない。これらについては各色の通り数を直接計算することにして、残った頂点の個数を数えて最後に4の肩に乗せて掛け合わせる。Fは問題文がちょっと難読気味だが、n項で総和sの数列であって、どの連続部分列の和もkとならないものが存在するかを答える問題。累積和を考えると、0\dots sから0とsを含めてn+1個選び、どの2つの差もkにならなければよい。何個選べるかを考える。端から貪欲に詰めていけば、周期2kで埋まっていき、最後に余った個数とkのうち少ない方だけ使える。s=kの場合必ずYESになるが、これも処理できていると勝手に思っており、しかし全然そんなことはなく1WA。

問題が解けたので目が冴え、コンテスト後はしばらく日記を書いていた。朝方切り上げ、布団に入ってハーメルンを読んだ。1作読了。「東方古神録」。主人公のチート具合が好みで、結構面白かった。キャラも過剰に変な感じはしなくて、受け入れやすい。

東方古神録 - ハーメルン

午前9時就寝。

10/09(土)

午後8時起床。今日は夕方からCFで4hコンがあり、ちょっと興味を持っていたが、実際その時間に目覚ましで起きてみるとあまりの眠さに衝撃を受けた。耐えられず二度寝し、この時間になった。急いで食事してABC222。

Exawizards Programming Contest 2021（AtCoder Beginner Contest 222） - AtCoder

Aはどう書いていいか悩み、AWKでprintfを使った。Bは適当にRaku。ここからはC++を使った。Cはなかなか実装が重めで大変だった。Dは自明。Eは辺ごとに通る回数をカウントすると、うまく±をつけて目的の値を作る問題になって、制約をよく読むと絶対値が105で抑えられるので、dp。Fはオイラーツアーして遅延セグメント木を作り、辺を行き来するたびに区間更新でその辺の重みを足したり引いたりした。Gは式を整理すると、あるmに対して10^i\bmod{m}が1になる最小の正整数iを求める問題になって、ちょっとだけ位数のことを考えたが、合成数modのBSGSを持っていることを思い出してそれを使った。最初答えが全部0になってキレそうになったが、確かに100が1であることに気づき、耐えた。答え0を検出しないようにライブラリを適当に書き換え、祈るように投げるとAC。

Hは、まずメモ化再帰で正しい値が出ることを確かめ、ループで直接求めるコードまで書いた。これは畳み込みっぽかったので、オンラインFFTをやれば解けるんじゃないか！？と思ってこの後ずっと実装していたが、結局合わせることはできなかった。そもそもオンラインFFTはlog 2つだから、107の制約では通らないか。

H以外の解説を読む。Fは木をちょっと拡張すれば直径の両端のどちらかが必ず答えになるらしく、なるほどなあという気持ちになった。G問題で使った合成数modのBSGSだが、今回のケースでは底とmodが互いに素でない場合必ず解なしになるので、最初少し探索してgcdを処理する部分が必要ないらしく、面白い。またオイラーのφ関数の約数を全探索する方法も紹介されており、こちらのほうが素直だったなと反省。

今日の昼頃にPixivランキング事務局からメッセージが来ていて、水曜日に投稿した短編小説が小説ジャンルのオリジナルウィークリーランキング83位に入ったことを知った。嬉しい……！小説を投稿した時のツイートのインプレッションは21000ちょっとだが、そこからリンクを踏んだ人は400人にも満たないようで、PV数のもう半分弱はどこから来たのかがよくわからないが、もしかしたらランキング経由で来た人がいるかもしれないと思うとワクワクする。

コードゴルフ。A問題はVimが最短になっていた。10000を足してから左端の1文字を削っている。そういえば、dcで出力の基数に10000を設定すると、10000進数のつもりなのか4桁で表示してくれたような……？と思って提出したものの、0は常に0とのみ表示されるらしくWA。Bはdcの22B解がほとんど自明で、僕はコンテスト終了直前までH問題をやっていて提出が22時40分過ぎになったのだが、22時38分の提出があって非常に悔しい気持ちになった。そのほかもコンテスト終了時点では何一つ最短を取れていなかった。このような状況はかなり久しぶりではないだろうか。衰えを感じる。

悔しいので、とりあえずC問題をRubyで、D問題をOctaveで縮めておいた。そうしているうちに午前2時になったので、FHC R3に出た。

Facebook Hacker Cup - 2021 - Round 3

ABD1の43ptで82位。R2を59位で通過したとき、Tシャツにバッジが付くのがR3の上位200人であることを知って残念に思っていたが、結局R3でもそれなりに良い成績を残せた。

ABcCを通して59位。R3進出、Tシャツ獲得に加え、上位200人なのでTシャツが何か特別仕様になるはずR3の上位200人に対する褒章らしい。ぬか喜び……。

週記（2021/09/20-2021/09/26） - kotatsugameの日記

Aは、更新をそれぞれ区間と見てマージしていけばよい。setで区間を管理するいつものやつだが、区間の端がどうなったら区間をマージできるのかを間違えたり、区間の左にあるものとマージし損ねたりして、サンプルを合わせるのにはそれなりに手間取った。Bは3列しかないため、行って戻って行って……のようにジグザグに動くことがない。考えるべきは、2点の間の移動方法と、2点からそれぞれ端のほうに行ってUターンしてくる場合のコスト。レベルで降順ソートするのは当然として、前者はセグメント木に3x3の距離行列を乗せればよい。後者は、Uターンする地点は近ければ近いほうがよく、これはsetで取得。さらにその間が通行できるかにはこれまたセグメント木が使える。安全性をとって定数倍悪めの解法を書いたら実行に結構時間がかかり、ちょっとヒヤヒヤした。

D1も値で降順ソートしてUF。以前に使ったロボットが同じ連結成分に存在するなら、それを流用できる。D2、D3については、UFのマージ過程を木にして、これの頂点とある点の間のパスに対していろいろ弄ることができればよさそう。HLDでできると思って、beetさんのライブラリを窃盗して1時間半格闘していたが、結局サンプルも合わなかった。

またABC222のコードゴルフに戻る。EはちょっとRubyで書いてみたら当然のようにTLEしたので、C++で清書した感じにしてお茶を濁した。FはRubyで、結構な時間を使って頑張った。

午前7時半くらいに布団に入り、ハーメルンを読む。2作ほど読了。

東方古神録～幻想幼女～ - ハーメルン

「東方古神録～幻想幼女～」。昨日読んでいた「東方古神録」の続編で、エタっている。

はりまり - ハーメルン

「はりまり」。霧雨魔理沙がホグワーツに入学する話。非常に面白かった。東方Projectにおける魔法とハリポタにおける魔法の違いの考察も興味深いが、何より魔理沙のキャラと立ち位置が好みだった。しかしこちらもエタっていて悲しい。

「はりまり」を読み終わったのが午前10時半。そこから午後1時半のHTTFまで3時間しかないが、ひと眠りしようと思って一度はスマホを手放した。しかし微妙に目がさえて眠れないこと、日曜日はHTTF以外に特に予定がないことなどを鑑みて、このままずっと起きていることにした。というわけでさらにハーメルンを漁って2作ほど手を出したが、片方は文章の拙さを我慢して読むほどでもないなと思ってしまい、もう片方は知らない作品の二次創作だったために、どちらも少し読んで投げ出した。

昼過ぎだったため、少し日記を書いて時間を潰し、午後1時半からHTTF。

デジタルの日特別イベント「HACK TO THE FUTURE for Youth+」 - AtCoder

途中までは非常に調子が良かったが、最後の1時間は全然スコアを伸ばせず、結局6位まで落ちてしまった。

A問題はビジュアライザをポチポチして1265823。このスコアはずっと更新されず、もしや理論値引き当てたか！？と思ってわくわくしていたが、openのほうで終了30分くらい前にもっと良い解が提出されていた。1x1ブロックはなるべく使わないようにしていたのだが、ビジュアライザを見た感じ思ったより使われていた。

B問題とC問題は全く同一のコード。まず、置いて印をより多く覆えるようなものを、タイブレークは盤面の中心にあるものを優先的に取るようにして貪欲に置いて行った。この段階では連結性を特に考えていない。次に、1x1ブロックを置いて全体を連結にする。2つの連結成分からそれぞれの代表点を全探索して連結成分同士の距離を出すのを全ペア行い、最も距離が近かった2つを実際に繋ぐ、ということを繰り返す。最後に、1x1ブロックに被さるように別のブロックを置いて、必要なコストが下げられる場合は置き換える、という操作を繰り返す。以上の3ステップであった。Bが1500000弱、Cが1890000ちょっとだった。

ここからさらに、1x1ブロックでつなげる際に縦と横のどちらを先に動かすかを両方試して少しスコアが上がり、以上のステップ全体を座標を調べる順番にある程度のランダム性を持たせたうえで時間の許す限り繰り返すことでBは1560000弱、Cは1900000弱になった。コンテストとしては、入賞を逃したし、抽選のアマゾンギフト券も外れてしまって残念。

昨日のABC222-Cが縮んでいた。配列の値をmapで加工してpで出力するとき、mapの中で出力するとsplat演算子が必要ない、というのは何度も何度も何度も何度も何度も何度も何度も見たのにいまだに忘れてしまう。絶望。

午後6時から少し遅刻してECR115に出た。コンテスト終了直前にGが通ったがその後Hackされ、現在6完。

Dashboard - Educational Codeforces Round 115 (Rated for Div. 2) - Codeforces

Aはよい。Bは選ぶ曜日を全探索して、2日とも行ける人と片方しか行けない人を数える。Cは数列の要素から平均を引くと、足して0になるようなペアを抜き去るしかないので、ちょうど平均と一致する要素だけ特別扱いして頑張る。わざわざ尺取りで数えたが、logをつけても変わらなかったかもしれない。Dは補集合を数える。片方が3つとも同じ場合はもう片方が必ず3つ互いに異なるので、両方2つずつ同じ値であるような3つ組を数えて引けばよいようだ。これは、(A,B),(A,\ast),(\ast,B)のような組だとわかるので、(A,B)を全探索すれば簡単に求まる。

Eは英語が読めなくて苦労したが、「右下右下……」と「下右下右……」のことを言っているようだ。数え上げは非常に面倒な気分になったが、差分更新にO(N+M)かけてよいことに気づき、愚直にどこまで伸ばせるかを求めて足したり引いたりしたら通った。FはbitDP。かっこ列典型の累積和を考えると、確かに使う文字列集合を決めれば末尾における累積和の値も決定し、それ以外の情報は必要ではない。ある文字列を足したとき、先頭からの累積minと現在の累積和が一致しているような場所の数がdpの値に足される。これは前計算で求められる。注意点として、ただ累積和の出現回数をカウントすると、'('で（累積和が増えて）終了するようなかっこ列をカウントしてしまう。文字列を足して先につなげる場合は、累積minが非負でなければならないので、そのチェックもする。

Gは落ちてしまった。まずn=|X|と置くと、片方がn桁の場合はもう片方は自由、そうでない場合は両方n-1桁にならなければいけない。片方がn桁の場合はそれほど一致しまくるケースが作れないだろうと思って愚直で書いた（ここを突かれて落とされたし、冷静になってみればそういうケースはめちゃくちゃある）。両方n-1桁の場合は面白かった。繰り上がりありでn-1桁ごとに和を取った文字列を用意して、Xの先頭1文字（これは'1'でなければならない）を取り除いた文字列を先頭にくっつけてZ-Algorithmすれば、もし求める位置があるならば2桁目からn-1桁目までは必ず一致する。1桁目は自分で削除したので、最後に文字列末尾の繰り上がり処理をキャンセルして一致を確かめればよい。

しばらくコードゴルフをしていたが、さすがに眠くなってきた。先に日記を書き上げて投稿する。予定通り日曜日は消えた。

10/10(日)

消えた。