10/23(月)

午後4時起床。半からインターン先定例会に参加した。

進捗としては先週も延々学習を回していただけ。メモリ節約のためデータが必要になる度にファイルから読み出していたのだが、今扱っている量なら全部メモリに乗せても余裕らしい。そこでそのように書き直し、ついでに完全なランダムアクセスが可能になったため訓練データをちゃんとシャッフルしてみたら、少し改善が見られた。

最近ずっと特に計画も立てずに行き当たりばったりで実験し続けていたが、さすがに良くないということでスケジュールを考えるよう言われた。今週のどこかに1on1を入れ、そこで相談することにする。

今日の勉強会は担当者の準備ができていなかったということで有志を募るオムニバス形式になった。自分は最近学業を理由に発表していなかったが、せっかくなので手を挙げて30分ほど喋った。内容は先週の週記にも書いたUC-Jについてなので、ここには特に書かない。他にはKaggleで最近行われたコンテストについての発表があった。

先週のUC-Jを解説を見てupsolveした。
週記（2023/10/16-2023/10/22） - kotatsugameの日記

解散後はすぐ学食に行ったが、かなり早い時間でまだ競プロサークルの定例会が行われていることに気づき、そちらに顔を出した。いろいろ解法の話をしていたら午後8時を過ぎてしまったので結局学食には行けなかった。

コンビニに寄って夕食を確保し帰宅。食べてから週記を書き進め、穴あきだらけのまま日付が変わる直前に投稿した。その後ラノベを読みつつ朝方までかけて追記し、Universal Cup以外を埋めた。

「世界で一番『可愛い』雨宮さん、二番目は俺。」2巻を読了。面白かった。主人公が目立ったり活躍したりする好みのシーンがたくさんある。今巻登場のヒロインは気が強く、自信があって、その上で主人公を頼りにしている点がかなり好みだった。メインヒロインの自信のなさも改善傾向にある。

11月の新刊をチェックして注文した。今回は32冊。最近明らかに買う量が増えている。本を買うときは財布の紐を意図的に緩めているので、ネット小説を探してとりあえず1話読んでみるのととりあえず買ってみるのが同じくらいの感覚になっていそう。さらに悪いことに、本は買っても1文字も読まず積むのでネット小説より悪い扱いをしてしまっている。

シャワーを浴びて午前11時半就寝。

10/24(火)

午後7時くらいに起きて布団で論文を読み始めたが、2時間ほどしてまた寝た。次に午前1時起床。

論文に双対性に関する綺麗な結果があった。計算してみないとはっきりとは言い切れないものの、これを使うと自分の示した等式が自明になってしまうかもしれない。今修論のネタに消えられると困るが、しかしどうしようもない。応用を考えるなどしてもう一捻り加える必要がある。

先行きの不安からハーメルンに逃亡。ランキングを眺めて暗殺教室の二次創作を見つけ、読んだ。「普通に中学生してたら超展開に巻き込まれたヤツ」。E組にオリ主が混ざって、特に暗殺における中心人物となるわけでもなくわちゃわちゃしているだけというのは珍しい。ただしそれではあまり興味が持てないことが明らかになった。

syosetu.org

食事してから別の暗殺教室の二次創作を読み始めた。こちらはかなり面白い。10時間ほど読みふけって午後4時くらいに寝落ちした。

10/25(水)

午後9時起床。昨日に引き続きハーメルンに没頭して「暗殺教室　不良児は認められたい」を読了した。

オリ主が努力家の秀才というのは珍しい。タグにもある集中力チートを使って量をこなしているようだ。このチートは、最初は思考が加速するだけだったが、話が進むと加速した思考に追いつく速度で体を動かすことが可能になりファンタジーじみてきている。まあそのくらいぶっ飛んだ強みのあるオリ主のほうが好み。

syosetu.org

午前2時過ぎに布団から脱出。毎週火・水に布団から脱出できなくなるのは、週のそのあたりに予定がないからだろう。今週は木曜日にゲーセンに行こうとしており、今日のうちにセミナー準備を終わらせるため頑張って身を起こした。

昨日読んだ論文に基づいて準備を行った。また双対を利用した計算も行ってみたところ、見事に自分の等式が出てきてしまった。何もかもが1本の線で繋がったような感覚を覚える。これだけ綺麗にまとまっているなら既出だろうと思って少しだけサーベイしたが特に見つからなかった。既出でないなら、今度は誰も興味を持っていない可能性が高くなる。先は暗い。

準備と数式のTeX打ちに時間を取られ、正午就寝。

10/26(木)

午後3時前起床。1on1に臨んだ。月曜日に書いたような話の流れでセッティングしてもらったもの。

まず最近の実験結果の取りまとめから付き合って頂いたが、改めて確認してみるとあまりうまくいっていないようだ。出来の良いデータがいくつかあって、それに印象が引きずられていた。あとはまとめた結果を見ながら今後の予定や改善案について相談。修論執筆が本格化したらまた実験を回すだけの人間になってしまうので、それまでにやっておくべきことを列挙した。

この後すぐの予定はないとのことだったので、時間をオーバーしても会議を続けさせてもらった。最後の雑談の時間で修論や博士課程について体験談をお伺いし午後5時過ぎに解散。

地下鉄で街に出てホスフィンと合流し、とんかつ屋に行った。近くによく利用するATMがあって存在は知っていた店。常連の客がたくさんいて古い感じの印象を受けた。

食事 pic.twitter.com/qwD7D3rIil
— こたつがめ (@kotatsugame_t) 2023年10月26日

分かれた後はゲーセンに移動し閉店まで25クレ遊んだ。今日は新曲や通常解禁された譜面を埋めた。

今日通常解禁されたのはバージョンSUNの最初のマップ。ボス曲「グラウンドスライダー協奏曲第一番「風唄」」は小粒のみで構成された鍵盤譜面ということでチュウニズムらしさがなく、公開当初から非常に難しいと話題になっていた。実際chunirecで見てもSS率・SS+率はダントツで低い。

Record stats · chunirec

自分の全曲SSもここまでかと覚悟していたし、実際最初のプレイはS+にすら乗らなかったが、ちょっと粘着したら何とかSSまでは出た。16プレイ。以下意識した点を軽くメモしておく。

41-42、49-50、74-79小節の片手3鍵は何となくでべちゃっと押しても案外通る。82-93小節は真ん中少し右で切って両手を使う。98-101小節はスライダーを押さえた左手の親指も使う。102-103小節は右手でスライダーをベシベシ叩き、反動で2回押す。106-109小節は早入り気味なら後ろのノーツを巻き込みにくい。110-111小節の押せる4鍵は押す。

どうしようもないところもある。特に11-17小節の鍵盤は3鍵に移行するタイミングがよくわからず、結局運ゲーのまま。32小節は本当に意味不明だがSSが出た回ではここをなんとAJで抜けた。再現性ナシ！94-97小節はがむしゃらにやっていたら結構うまくいく。112-115小節は無理なので、試行回数を増やして指が耐えることをお祈り。リズムはもう知らない。

風唄SS！！！ pic.twitter.com/eVW5JH8nWV
— こたつがめ (@kotatsugame_t) 2023年10月26日

ラーメンを食べて帰宅。しばらくTLを眺めた後シャワーを浴び、明日朝のSRMにレジって寝た。午前3時だった。

10/27(金)

午前9時半起床。午前10時からSRM850に出た。div.1に33人しかいなかった。~~統計情報が週記公開時にまだ用意されていないため、リンクは前回のものとなっている。~~

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

Easyは桁数を固定するごとに先頭桁からdfs。下の方の桁は数え上げで適切にスキップしていけばよい。なぜか桁数を求める部分だけ数え上げで解いた後は愚直にdfsをするしかないと思い込んでおり手間取ってしまった。 $N$ が小さいので数え上げのオーバーフローはあまり気にしなくてよい。

MedはDAGの最小パス被覆になる。自明。

Hardはvaluesの累積和を取って考えると広義単調減少という制約を忘れられる。stunningはこれですぐ求まる。tolerableについては単調性を破壊するインデックス $i$ を決めたとき、 $i-1$ までの累積和は使わず、かつvalues[i]を一つ以上使うと表現できるため、dpの巻き戻しで計算できる。

1時間弱で全問提出。以降のフェーズをサボって昼食・買い物のため大学生協に行ったところ、今日から学祭ということで休みになっていた。公式ページの営業時間お知らせには特に何も書いていなかったのでびっくり。仕方がないのでコンビニに寄ってパン類を買い、帰宅した。

は？営業時間の表に書いとけや pic.twitter.com/GuirFugrnU
— こたつがめ (@kotatsugame_t) 2023年10月27日

システス結果を見たら全員のEasyが落ちていてひっくり返った。さすがに何かおかしいということで現在修正中らしい。MedとHardは問題なく通っていた。なかなか典型っぽさが強いように感じたが、まあ一時期頻出したようなクソ小さい制約で重実装やるだけ問よりは100倍マシ。

11/03追記：Easyの修正が完了し統計情報も公開されていた。上に貼ったリンクは修正済みである。問題なく通って全完3位、レートは2846→2862(+16)。

Amazonで注文した古典部シリーズ愛蔵版の第2弾が届いていた。第1弾は無事だったが、今回は残念ながら角が潰れてしまっていた。こういうことがあるからAmazonで本を買ってはならない、というのは何度か聞いた話である。大切なものなのだから面倒がらずちゃんとリアル本屋で注文・受け取りを行うべきだった。

Amazonで本を買うのは止めよう！ pic.twitter.com/UCywNdrrCc
— こたつがめ (@kotatsugame_t) 2023年10月27日

仮眠しようと布団に入ったのにうっかりスマホを触り続けて眠れなかった。午後2時半くらいに出発。降水確率40%だが空模様が信用ならないため地下鉄で登校した。

午後3時からセミナー。最初2時間は留学生の発表だった。今日も具体例の計算を指示されて手こずっていたが、先週とは異なり分かりやすい概念を扱っているのだからできてほしかった。

次の1時間半は自分の発表。水曜日に行った計算と得られた式については、結果だけTeX打ちしてあっても具体的な発表の形にまとめられていなかったので、その前の基礎的な事項を確認するにとどめた。

次回の予定を決め学食で夕食を摂って解散。駅の近くをウロウロして写真を撮ってから帰宅した。初めてTwitterアプリのフィルター機能を使った気がするが、手軽に印象を変えられて良い。

#東北大学深夜徘徊サークル pic.twitter.com/WOC5NyEvS5
— こたつがめ (@kotatsugame_t) 2023年10月27日

午後9時20分からyukicoder 410に出た。

yukicoder contest 410 - yukicoder

Aは何も考えず外積を計算した。Bは等比数列の和で直接求めた。Cは円周角の定理。Dは $0,2\in A$ であり、さらに $1$ を無視したとき交互に現れていなければならない。

Eは $\gcd(x,y)=1$ なら $f(x,y)=(x-1)(y-1)$ でありそれ以外は0になる。0が最小なので $0,1\notin A$ なら互いに素でない2数を作るのが目標。奇数と奇数で操作すると必ず偶数になるので、偶数二つ、偶数一つと奇数二つ、奇数四つのどれかが取れる場合OK。どれもダメなら $N\le 3$ なので全探索が可能になる。実装は最初数手を毎回 $O(N)$ かけて処理し、末尾に $0$ を作ったらあとはそれに全部くっつけていった。

Fは45度回転して座圧。いつもの $(x,y)\rightarrow(x+y,x-y)$ では縦横 $\sqrt 2$ 倍になっているが、単に答えを2で割ればよい。Gは実験すると $|X-Y|=1$ かつ $\min(X,Y)$ が奇数であることが条件。ひたすら場合分けして負け状態に遷移させた。条件の後半に気づいておらず2回ほどWAを重ねた。

Hは条件が付いている人だけbitDPで処理した後算数。面倒。Iは答えを二分探索。判定は $i\rightarrow C_i$ という辺に沿って足りない花の数を伝播させた、がオーバーフローで1WA。Jは分割統治。

全完6位。日記を書いて午前4時半に寝た。

10/28(土)

午後1時半起床。午後2時からUniversal Cup 7回目、Two Capitalsセットに出た。

書く：UC

午後9時からABC326に出た。

Panasonic Programming Contest 2023（AtCoder Beginner Contest 326） - AtCoder

A、Bはよい。Cは尺取り法。Dは枝刈りdfsをした。一つ目の条件を読み落としており各行・各列に出現しない文字があって1WA、2個以上出現するものがあってもう1WA。2回目のWAでは場合の数が大きくなるようで1ケースTLEしていた。Eは $i=1\dots N$ の順に $x=i$ となることがあるか確率を求めていく。 $x=0\dots i-1$ から一斉に遷移してくるため貰うdpがかなりシンプルになった。

Fは次元ごとに分けて半分全列挙。つまり $N$ が2回半分になって $2^{N/4}$ 通りの全探索をすることになるが、この結果をmapに入れていたらTLEギリギリになってしまった。コンテスト後にvectorとソートに書き換えてみたら450msくらいだった。Gは「スキル $i$ のレベルが3以上である」のような変数を $4N$ 個用意して燃やす埋める。

36分で全完。速度としては2位だったが2ペナが響いて7位まで落ちた。一応学生賞圏内ではあるらしい。

www.youtube.com

コードゴルフはAとB。Aは微妙に扱いづらい設定。dcで $|X-Y-1/2|\lt 3$ を判定したが $5/|X-Y-1/2|\ge 2$ に負けた。出力切り替えにRコマンドを使うので、2以上と未満で分かれると非常にやりやすくなる。BはとりあえずNibblesで書いただけ。

午後11時半からCF #906 div.1に出た。

Dashboard - Codeforces Round 906 (Div. 1) - Codeforces

Aは両端を見て相異なるなら削除、そうでないなら01をどちらかの端に挿入して前者に帰着するというループを回した。300回操作しても文字列が空にならないなら不可能と判定。両端を貪欲にマッチさせるのが最適だと信じ込んでいたが正しくないかもしれない。ともかく、01を挿入して両端を削除する操作を文字列のrotateだと思えば、そんなぐるぐる回し続けるわけもないので可能なケースは必ず300回以内になりそう。

Bはなかなか気付けなかった。 $i,j\ge 2$ に対し辺 $(i,j)$ を張れるとき、 $2\max(a_i,a_j)\ge a_i+a_j\ge cij\ge 2c\max(i,j)$ より辺 $(1,i)$ または辺 $(1,j)$ も張れる。そして片方を張れば連結成分が大きくなってもう片方も張れるようになるから、結局頂点 $1$ を介して繋げられる。ということで片方の端点が頂点 $1$ であるような辺だけ考えてやってみればよい。

C1はバグらせて大変だった。街を昇順に見つつ雨が降る日を管理すれば、その日数が2以下であるような街と日付の集合が求められる。日数がちょうど2である街を全探索することに気を取られて、日数がちょうど1である街をたくさんカバーするケースを忘れていた。他にも大量にバグを埋め込んでいて3WA。

C2は最後にdryとなった街の番号を状態とするdp。新しい街をdryにする場合、以前の街も同時にカバーする日はカウントしなくてよい。そもそもその新しい街がカバーされるのは $k$ 日以下としてよいため、貰うdpの遷移元としてはカウントしなくてよい日数が $0\dots k$ のどれかで区間に分かれている。操作回数も状態に持つことにして、長さ $k+1$ の配列をセグ木に乗せれば取得できる。

Dは実際に操作をシミュレートしてみて、途中で同じスタックに戻ってきたらその間を削除してよい。そのループではスタックのトップにあった値だけ見て遷移していたはずで、このときどのスタックから始めても一周して元に戻るからである。これを、削除した値はそのままにして始点を変えながら繰り返した。すでに答えが求まっているスタックにたどり着いたらその答えをコピーしてよいため、スタックの各要素は高々1回しか見られない。

C1で大変な目に遭ってレートの大幅な減少を覚悟したが、結果的には5完22位と大健闘。レートは2969→3014(+45)で3回目のLGMを達成した。

www.youtube.com

日記を書いて午前10時過ぎ就寝。

10/29(日)

夕方から何度か寝たり起きたりしていたが、日付が変わるくらいに目を覚ました際、体中寝汗まみれになっていることに気づいた。不快だし冷たいしで到底横たわっていられる状況ではなく、たまらず起床してシャワーを浴びた。

午前0時半からYandex Cup Algorithm部門のQualificationに参加した。どのくらい問題を解けば通過できるか書かれておらず不穏。去年参加していたOpenCupと同じプラットフォームに久しぶりに触れて懐かしい気持ちになった。

https://contest.yandex.com/contest/54452

Aはよい。Bはある値 $x$ 未満の要素は全部取り、追加でちょうど $x$ の値をいくつか取ることになる。 $x$ だけ抜き出して調べた。Cはbitごとに見るド典型。Dは累積和を考えたら牛ゲーになり、負閉路があるか調べればよい。Eはセグ木。

ここまでは簡単だったがFが解けなかった。Stern-Brocot tree上で分母分子が10⁶以下のノードを探索し、判定には $X$ または $Y$ を舐めてもう片方をBITで数える $O(\min(n,m)\log\max(n,m))$ の方法を採用した。ちゃんと一方向に潜り続けるケースを二分探索でスキップしたがTLEが取れなかった。