週記（2023/09/25-2023/10/01）

09/25(月)

午前4時起床。

今日は留学生向けオリエンテーションの日と聞いていた。ここで学生証が配られて通学定期券を買えるようになるとのこと。買いに行く日を決めようと夜までかけて数回やり取りし、今週金曜日の正午に仙台駅で待ち合わせることになった。

午後4時半からインターン先定例会に参加。寝ている間に回していた機械学習が無事完了していたので、進捗報告ではその結果を見せることができた。現状はtrainのlossが単調減少でtestのlossは単調増加→停滞という感じのため全然ダメ。まあとりあえずで回したものだから期待など一切していないし、それより最初の数epochだけでもまともっぽい結果が出ていたことに驚いている。

勉強会はLlamaIndexの話。面白い技術だった。長いテキストをぶった切って関係ありそうなところだけプロンプトに入れる、なんて雑な方法でも動いてくれるLLMの柔軟さに驚き。プロンプトエンジニアリングとはもはや「あなたは○○の専門家です」みたいな手作業かつ手探りのものだけではないらしい。

解散後は深夜までずっと週記を書いていた。JAG夏合宿day3のコンテストとyukicoderについてが穴あきになった状態で投稿。前者は、自分は夏合宿に参加していないが内部コンテストとして09/10に参加していた。

午後11時半からCF #899 div.2。

Dashboard - Codeforces Round 899 (Div. 2) - Codeforces

Aは先頭から貪欲に決めていけばよい。BはSに含まれない要素を一つ固定すると、それを含まないS_iを全部集めてくるのが最適。

Cは取り除くカードのうち山札の上に最も近いものを固定すると、それがスコアに加算されるかはすぐわかって、その下のカードは加算するもしないも自由である。もっと言えば固定するカードとしては山札の上2枚だけ試せばよいが、全部試しても計算量は変わらない。

Dは根を一つ決めたとき、ある頂点uとその親pの値を揃えるためにはu以下の部分木に対してc=a_u\oplus a_pで操作を行う必要がある。逆にこれを根以外のすべてのuに対して行えば全体が揃うので、コストが木dpで簡単に計算できる。これを全方位木dpにするのも難しくない。aの上限が2^{20}ではなく2^{30}に見えていて__int128を使わないとダメだと思い、出力で少し手こずってしまった。

E1は、まず順列が一つの場合にどうやれば達成できるか考えた。連続部分列1\dots k-1があったときそれを1\dots kに伸ばすためにはどうすればいいか考えると、まずk-1の直後のインデックスで操作することで1\dots k-1をsuffixに持っていき、次にkがあるインデックスで操作することでくっつけるという方法が思いついた。操作回数は2n未満になる。

あとは二つの順列に対して同時に揃えられるか考える。2回の操作で順列を元通りにするのは簡単なので、操作回数の偶奇が揃っていればOK。また先頭のインデックスを選ぶと順列が1回rotateされるので、nまたはmが奇数のとき偶奇を合わせることができる。操作回数は3nや3mになるので制約にも収まった。

最後にnとmが偶数で操作回数の偶奇が異なる場合が残された。これは不可能だろうと予想が立つ。偶奇を考えるのだからと転倒数を計算してみればビンゴで、長さが偶数なら操作する度必ず転倒数の偶奇が入れ替わることが示せた。以上でE1については解けた。

E2はこの方針だと本当に不可能。小さいケースの厳密解を求めた後、適当な揃え方を実装して合わないか頑張ってみたが、長さ5くらいでもうどうしようもなくなってしまった。そのままコンテストが終了し、結果は5完最速の8位。

www.youtube.com

メインとなるアイディアがTLで流れてきたのでE2をupsolveした。順列を、先頭と末尾の間に0を挟んで円環と見る。すると操作は選んだインデックスと0のswapになるらしい。これはさすがに頭が良すぎる。自分は要素を後ろへ飛ばした後いくつかrotateだなあというくらいにしか見えていなかった。

最終的な0の位置を決めるごとに最短のswap操作の列は線形時間で求まるから、操作回数の偶奇それぞれ最も少ないものだけ取り出し、今度は2乗時間かけて実際のインデックスに書き直せばよい。順列の長さが奇数なら0の位置を全探索することでちゃんと操作回数の偶奇が両方現れるようなので、手動で偶奇を合わせることはしなくてよい。

MHCのPractice Roundが終了していた。全部提出したがA2だけ落としてしまった。ここに感想を書いておく。

Meta Hacker Cup - 2023 - Practice Round

A1はバンズの枚数とパティ・チーズの枚数がそれぞれ必要なだけあるか判定。A2はsingleを一つ買うとあとはパティ・チーズの枚数がボトルネックになるので、singleだけ・doubleだけ・single一つとdoubleの三通りを試せばよい……と思ったがsingleを二つ買うケースがあったらしい。解説を見るまで気づけなかった。

Bは難しそうな雰囲気を出しているが、結局相手より長く操作できれば良いので1歩ずつ進むのが最適。

Cはちょっと面倒。リンゴを2N個用意したら軽いほうと重いほうから順にペアを作ることになるので判定は簡単。まずN=1の場合は1が答えとなる。そうでない場合Aがソートしてあるものとして、ペアの重さの和としてはA_1+A_{2N-1}、A_1+A_{2N-2}、A_2+A_{2N-1}を考えればよい。両側から実際にペアを作ってみて、和が一致しなくなったところで必要な重さを二通り試す。

Dは面倒。どこかで奇数長のループに寄り道できればよく、そのために橋を通る必要があるならそれは行きと帰りで2回通ることになる。この辺りのことを考えると2辺連結成分分解することが思いついて、実際うまくいった。まず各2辺連結成分について奇数長のループが存在するか、つまり2部グラフでないかを判定する。次に多始点bfsで奇数長のループがある成分にたどり着くまで何本橋を通る必要があるかを各成分に対し求める。

クエリに対してはaを含む成分からbを含む成分へ向かうパスの上でいま求めた橋の本数が最も少ない成分から寄り道すればよく、その本数はHLDとセグ木で求まる。橋以外の辺を2回以上通らないようにパスを選べるかは……知らない。まあMengerの定理から成分ごとにうまく辺素パスを2本選んでくれば良いのではないだろうか。

Dの入力ファイルは20MBほどあった。ダウンロードボタンを押した直後に何も考えずパスワードも表示してタイマーをスタートさせてしまったが、ちょうど夜ということもあって回線が非常に遅く、ダウンロードに6分かかると言われて顔が真っ青になった。祈るように見守っていたら何とか5分弱で完了したので、急いで実行して提出。生きた心地がしなかった。

朝までかけて「お隣の天使様にいつの間にか駄目人間にされていた件」8.5巻を読了した。努力家なところを尊敬しますとか、あなたは優しい人ですとか、これから末永くよろしくお願いしますとか、これまで本編でも何度も描かれてきたパターンのイチャイチャを短編でも延々ループしている気がする。目新しさがなくて正直つまらなかった。

週記のyukicoderの部分を埋めた後修論のための計算に取り組んだ。考えていた方法の一つについて試してみたが、うまくいかなかった。正確には整理した結果がすでに知られているものの特殊な形式になってしまった。うまくできているものだ。さらに、これまで大事にしてきた等式が自明なものとなってしまう解釈に気づいた。何もうまくいかないまま次に試すことのメモだけして今日は切り上げた。

午前10時くらいに布団に入った後、ラノベを読んだりハーメルンを読んだりしていた。午後3時くらいに寝落ちにより就寝。

09/26(火)

午後11時起床。半からCF #900 div.3に出た。ついに900回目。

Dashboard - Codeforces Round 900 (Div. 3) - Codeforces

Aはk\in aかを判定。Bはよくわからないが10^8,10^8+1,\dotsを出力したら通った。聞いた話によれば全部奇数に揃えても良いらしい。こちらのほうが何というかそれっぽい。Cは1\dots kの和とn-k+1\dots nの和の間が全部作れるので、そこにxがあるか判定。

Dはちょっと難しかった。操作をよくよく観察すると、lとrで分割された区間内の中心から左右何文字分かをreverseするものになっている。中心が揃っているのだから操作の順序は入れ替えてよい。あとはどの文字とどの文字がreverse時のペアになるかを考え、reverseされた回数の偶奇によって適宜swapしていけばOK。

Eはlを決めるごとにlから右に見ていったときの累積ANDが変化するrのすぐ左しか考えなくてよい。そのようなrは高々O(\log a)個しか存在せず、lを降順に見ていくと効率的に列挙できるから、それぞれ試す。

Fはnとaが互いに素ならd(n\cdot a)=d(n)\cdot d(a)であり、d(a)はどんな正整数にもできるので、結局d(n)\mid nかを判定すればよいことになる。高速素因数分解の前計算をしておくとnを素因数分解した形で保持するのは簡単。そこからd(n)も求まり、これまた素因数分解した形で持てば判定ができる。計算量は知らないがmapを使い倒していても爆速だった。

Gは面倒だった。まずベースとなるのがg(x,y)で立っているbitの数で、ここにg(x,z)\;\mathrm{AND}\;g(y,z)で立っているbitの数が足される。後者を最大化したい。列の場合を考えると、各bitについてそれが出現する要素の両端を求め、その間の区間を集めて最も重なっている位置からzを選べば最適となる。両端を求める部分がモノイドになるのでセグ木でO(\log N\log a)。zを決める部分はボトルネックにならない。

今は木なのでHLDを使えば\log N追加して解けないことはない。しかし5secだとちょっと怪しいので、何とか\log二つで解けないか考えた。パスをLCAで分解して後からマージすることにすれば、頂点とその祖先を端点とするパスに対する問題になる。オフラインクエリなので、dfsしながら祖先で特定のbitが立っている頂点を列挙し、その上で二分探索すればよい。これで計算量が落ちた。

実装は面倒だったが書いたらすぐ合い、出すと900ms弱で通った。全完10位。Gはopen hacking phaseが終わってみたら少し伸びて1100msを超えていた。

www.youtube.com

今週末には3週間ぶりのUniversal Cupがあるが、オンサイト等と重なってフル参加が難しい状態である。これについてmaroonさんが公式Dicsordでwindow追加のお願いをしてくださっていた。とりあえず金曜日にwindowが追加されるらしい。非常に助かる。

次回のUniversal Cupは09/30らしい。この日は第四回日本最強プログラマー学生選手権の決勝の日で、夜中にCF div.1があり、さらに自分は後泊するから夜更かしできない。よってフルで参加できるwindowがないようだ。WTFと被ったときはwindowが増えたので今回もそういう対応をしてくれないかと思うが、オンサイトの格が違いすぎてお願いするのが恥ずかしい。

週記（2023/09/11-2023/09/17） - kotatsugameの日記

食事して日記を書き、ラノベを読んだ。「悪ノ黙示録」を読了。面白かった。謀略・交渉・戦闘どれも良かったが、特にどのシーンでも常にボスらしい、つまり動揺したり怯んだりしない態度を貫いていた主人公が格好良かった。ただラストはちょっと受け入れにくい。話の主題であるからして、最後まで悪を貫く必要があったことは理解するものの、自分にそういう話を読んでいるという覚悟がなかった。

それから今日も修論の研究を進めた。プログラムを書いて小さなランダムケースで成立するのを確かめることで、今わかっている等式の一般化した形のエスパーを試みた。手計算による式変形も組み合わせることでちょっとずつ適用できる範囲を広げ、最終的にはしばらくプログラムを回しても一向に落ちないものを作ることに成功。証明は後日やってみることにした。

午後2時になってTLに学振の結果が流れてきたので、自分も見に行った。落ちていた。しかも申請書の評価がほぼ最悪だった。落ちるのは分かっていただとか、当時ひねり出した研究計画と今やっていることが結構違うから通っても困るとか、そういうことを言うのすら憚られるレベル。まあここは日記だから言ってしまうが……。とりあえず、今度DC2に出すときは書類作成にもっと時間をかけたい。

布団に入ってラノベやハーメルンを読み、午後7時前に寝落ち。

09/27(水)

午後11時半から午前3時くらいまで、起きてネット小説を読んでいたらしい。

09/28(木)

午前7時に起床し二度寝もせず昼過ぎまでなろうを読んでいた。シャワーを浴びて食事した後、少しインターン関連のコーディングをして学習を回し始めた。

生協に行って本とお菓子を買い、散髪。床屋で流れていたラジオ番組にちょうど緑仙さんが出演していた。

帰宅して修論の計算。火曜日にエスパーした等式の証明をやってみたらあっさりできてしまった。誰でもできる内容だったとはいえ、今のところは結果が出たことを喜びたい。しかし真に喜ぶためにはこの等式が既出でないことを確かめる必要がある。この悪魔の証明はどのくらい調べれば十分なのだろうか。とりあえず論文をいろいろ検索してみたがパッと見て判断できるわけもなく、よくわからない。

午後6時からひと月ぶりの1on1に臨んだ。現状lossが爆発してまともな状態になっていないので、それを改善するためどこを弄って実験するか指南してもらった。ほぼ予定通りの1時間ちょっとで終了した後、早速1点変更して実験を回し始めた。

布団に入ってラノベ「クラスのプライド高めなお嬢様。家では俺のメイド」を読了。文章が合わなくて内容どころの話ではなかった。たまにそういうラノベがある。この本はセリフ回しに違和感があってなんとなくテンポが悪い気がした。

午後9時から2時間半ほど仮眠した。起きて午前0時からSRM849に参加。

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

Easyから詰まって大変だった。障害物の周囲の行・列だけ取り出して座圧するテクを思い出し、とりあえず到達可能性の判定が可能に。どうせこの上で移動しても3000命令の条件はクリアできるだろうと思い、一応証明をつけてから移動コストを命令列の長さとしたときの最短経路を求めて出力した。

方向転換するのを障害物や端にぶつかったときだけとすると、経路は50個ちょっとの直線に分解できる。一つの直線の長さは109以下であり、このとき最大でも53命令で移動できるようだ。よって確かに命令数は十分少なくなる。コンテスト中はこの証明ではなく、縦横それぞれ合計で109しか移動しないことから長さが2べき引く1の移動が続いたときどうなるか考えていたはず。

Med。頂点数が同じ木は同じ彩色多項式を持つので「C色以下」で塗り分ける方法はすべて等しい。よってそこから包除原理で求まる「ちょうどC色」で塗り分ける方法も等しくなるから、あとはそれを実際に計算すればよい。ところがこの包除原理がどうなるのかわからなくなって時間を食った。しょうがなく実験したら係数が二項係数のやつだった。

Hardは1-3-5-\dots-2-4-6-\dots-1が答えの並び方だと予想した。またある並び替えを実現するためには「切らなければならない辺」と「繋がなければならない辺」があり、頂点をいくつか選んでこの辺をカバーすれば十分だろうから、最小点カバーのサイズを求めてみた。

チャレンジフェーズでHardが落とされた。何も証明していないので落ちるのは仕方がない。それ以外はシステスも通り、結果は7位でレートは2860→2846(-14)。Medが遅いのが悔やまれる。超典型的な包除原理なのになぜ混乱してしまったのか。

日記を書いて午前5時半就寝。明日は月曜日の日記で書いた留学生のチューターをする日。

09/29(金)

午前10時半起床。1時間ほどなろうを読んでから出発した。仙台駅に着くと集合時刻まで微妙に時間があったので、バス定期券売り場の下調べをしておいた。

無事合流し、まず昼食として近くの牛タン専門店「青葉亭」に行った。ここは両親が仙台に来た時によく行くところで、駅3階に軒を連ねている店と比べると空いていて便利。付け合わせの南蛮味噌はかなり独特な味わいだと思っていて留学生が食べられるか不安だったが、しっかり完食していてびっくりした。

次はバス定期券の購入。申込用紙が日本語オンリーで不親切だと思ったが、よく考えると定期券を買うレベルで日本に住むならこのくらいは読めないと逆に困るのだろう。まず記名するよう促したところ、あらかじめ配信されていたらしい名前のカタカナ表記が載ったメールを取り出して書き写し始めたので、住所についてはさすがに代筆した。学生証の有効期間が10/01からだったので少し躓きつつ何とか入手に成功。

あとは寮費振り込み。こちらは諸々記入済みの振込用紙が大学から渡されていたようで、記名して銀行窓口に提出するだけで驚くほどあっけなく終わった。午後2時くらいに解散。自分はその後ゲーセンで10クレ遊び、理論値を一つ出して帰宅した。

なろうの「とある魔球のダウンザライン！」を読了。主人公が強くて面白かった。作者はテニス未経験、と言いつつテニスに関する思想が結構強めに出ていたのは気になる。

https://ncode.syosetu.com/n9419ez/

CGR21のTシャツが届いた。

机に突っ伏して20分だけ仮眠し、午後8時からUniversal Cup 3回目、Binjiangセットに出た。

書く

食事して少し日記を書き、午前3時就寝。明日はオンサイトのため朝から東京に移動する。

09/30(土)

午前8時前起床。荷造りして出発し、午前9時半の新幹線に乗り込んだ。自分の席に人が座っていてびっくりしたが、降り忘れだったらしくすぐに空いた。その間自分は車両を間違えたかと思って通路をうろうろしていただけだった。こういうときは積極的に声をかけるべきなのかもしれない。

車内ではずっと寝ていた。午前11時過ぎに東京駅に着き、会場近くの田町駅へ移動。予め声をかけていたへのkとたまたま同じ新幹線だった仮の人さんと一緒に近くのカフェで食事し、会場に向かった。

受付して30分くらい懇親したところで開会式が始まり、すぐにコンテスト開始。

第四回日本最強プログラマー学生選手権 -決勝- - AtCoder

書く

企業プレゼンテーションの時間を使ってEのデバッグをしたら通った。ロスタイム20分といったところか。BCDは感触的にどれももっと速く解けたはずだと思っているので、このくらいの時間でもひねり出せないことはなかったのかもしれない。惜しかった。

表彰式前の休憩時間で、kotamanegiさんと学振の申請書を見せ合った。kotamanegiさんの申請書は網掛け・下線・太字など文字の強調表現が自分よりかなり多かった。それでいて読みやすさは損なわれていないので、かなり絶妙な塩梅なのだろう。自分の申請書については空きスペースが多いこと、「ずっと」という口語表現が残っていること、マイナスの意味の言葉は取り除くべきであることを指摘された。苦しい。

表彰式。正直4完時点の提出状況を見て入賞は確信していたので後は何位かということだったが、結果は5位。予想外に高かった。後ろのほうの問題に特攻した人が全員失敗したのが効いたようだ。

書く：懇親会

午後7時くらいに解散した後、へのk・maspyさん・Rubikunさん・potato167さんとビル地下にあったレストランに入った。

書く：二次会

午後8時半過ぎに退店し、駅に向かう面々と別れてホテルまでダッシュしチェックインした。午後9時からABC322。

AtCoder Beginner Contest 322 - AtCoder

書く

CFまでの時間でシャワーを浴びた。今回泊まった部屋は洗面台・トイレと浴室が扉で仕切られており洗い場付きの快適な環境。しかし今は悠長に湯船に湯を張る時間もないし気力もない。寝間着を着たら完全に寝るモードに入ってしまったが、何とか耐えて午後11時半からCF #901 div.1に出た。

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

書く

午前5時前就寝。

10/01(日)

書く