週記（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巻を読んだときの日記でも言及したが、この巻でも主人公の自分語りがあまり性に合わなかった。ただ、今回はそういうものとしてかなり端折りつつ読んだため、ストーリーの面白さに目が向いて、印象は良くなった。