11/13(月)

午前2時前に目を覚まして3時間くらいネット小説を読んだりラノベを読んだりしていた。その後寝落ち。

午前9時半起床。PCの前で1時間ほどウダウダしてから学食に行くためシャワーを浴びたが、今から行ったら帰る頃に2限終わりの混雑に巻き込まれそうだなと思って、昼休みが終わるのを週記を書きながら待つことにした。午後1時過ぎに満を持して昼食。

またしばらく週記を書いて、午後3時半からインターン先定例会に出た。進捗報告で先週作ったビジュアライザの出力をお見せしたが、やっぱり現状では使い物にならないということで、半年取り組んで成果が出ないなら切り上げて他のタスクに移ったらどうかという話になった。それは……困る。この先しばらく新たなタスクに参入できるほどの時間的余裕はないはず。

自分が一番最初に携わった機械学習系の開発は結局形にならないまま終わっていたのだが、そこから技術的にも進歩しているし、やはり需要はあるようだからと、もう一度チャレンジしてみることになった。
週記（2023/06/05-2023/06/11） - kotatsugameの日記

まだモデルを改善する余地はあるし、出力の後処理を適切に行うのも効きそうなので、とりあえずもう1か月ほど頑張ってみることになった。成果を出すことを念頭に取り組むべしとのこと。lossを最小化するだけでなく、ビジュアライズしてデータを1個1個眺め改善していかなければならない。このことはインターン開始当初から何度も言われてきたが、やはり手間がかかるためすぐ易きに流れてしまう。

勉強会は金融の話だった。値動きにあまり相関がない資産を組み合わせて保有することでローリスクハイリターンが目指せる、という話。例として紹介された株と金（Gold）の相関が小さいという事実は興味深かった。

解散後はずっと週記を書いていた。今週もUniversal Cupまで埋めて午後11時前に投稿。しばらくラノベを読んで午前1時過ぎに寝た。

11/14(火)

午前7時起床。

布団に横たわったままラノベ「男子禁制ゲーム世界で俺がやるべき唯一のこと」3巻を読了した。2巻ラストの爆死エンドからどうやってシリーズの続きを書くのかと思っていたら、あらすじに「仇敵と一体化して蘇生」と書かれており仰天。その敵の魔力を得、さらに以前から言及されていた主人公の魔眼についても明かされて、とことん主人公が強化された巻だった。

昼前に布団から脱出。夕方まで学食に行くでもなくずっと発表スライドの修正をしていた。実は先週、作ったものをホスフィンに送ってコメントを貰っていた。特に大きかったのは文章を切り詰めて単語・記号を主体にするべしという指摘。いつも言いたいことを全部スライドに書いて読み上げるだけという状態にしていたがこれは当然良くなく、修正すると見た目もシンプルになって気分が良かった。

夕方先生からメールが届いて、先週のセミナーがキャンセルになったのは誰もセミナー原稿を送ってこなかったからだったということが明らかになった。そうか……。

合間にラノベ「北欧美少女のクラスメイトが、婚約者になったらデレデレの甘々になってしまった件について」を読了。過去に情けない行動で人を傷つけてしまったトラウマを抱える主人公だが、ほとんどヒロインたちに流されるような形で婚約なり同居なりを受け入れ、さらに誘惑されて理性を飛ばしそうになっており、設定に比べて行動が軽率すぎるという印象を受けた。

学食の夜の部に行った。カレー中2皿でかなり満腹に。よく噛んで食べるべきとは思っているが、素早く腹に流し込まないと途中で手が止まってしまう。このことを意識して早食いしてもギリギリだった。

食事 pic.twitter.com/8hJqQSHLHo
— こたつがめ (@kotatsugame_t) 2023年11月14日

帰宅して30分くらいインターンの作業を行った。その後またスライド修正に取り組んだが、眠気が強く早々に布団に倒れこんだ。午後8時就寝。

11/15(水)

午前7時半起床。今日もスライド修正に取り組む一日だったが、夕方以降はほとんどの時間をラノベに費やしてしまった。

朝、ICPCから参加者・コーチ向けの質問メールが届いた。チーム名の読みやオープニングPVに表示したいハンドルネームを聞くのは納得感がある。一方AtCoder IDを聞かれたのはびっくりした。World Finalsのチーム紹介でCFのレーティングが表示されているのは見たことがあるが、日本だからAtCoderレーティングを使おうという感じだろうか。

昼過ぎにYandex Cup決勝に行くフライトの日程がメールで来た。今のところ飛行機に乗っている時間といつも出ているコンテストが被ったりはしていないらしい。また他の日本人参加者に聞いてみたところ同じ便が案内されたようだった。安心。

午後3時過ぎに大学に行き、昼食と散髪を済ませた。ラノベや菓子パンを買って帰宅。

ラノベを2冊読んだ。1冊目、「クラスで2番目に可愛い女の子と友だちになった」5巻。主人公カップルの性交渉のタイミングだったり、アラサー間近の彼女の兄とその幼馴染の関係だったり、生々しい話が多かったものの非常に面白かった。特に「彼女の兄」という微妙な立ち位置のキャラクターはこれまでスポットライトが当たっていなかったが、主人公に悩みを相談する弱さと最後には立派に覚悟を決める強さがどちらも好印象。親世代より下、同年代より上という年齢に見合う絶妙な描かれ方だった。

2冊目、「有名VTuberの兄だけど、何故か俺が有名になっていた」。ヒロインのVTuberたちが主人公への好意を全く隠していない点が気に食わなかった。いくら主人公が視聴者に受け入れられているとしても、基本的な炎上対策として最初は躊躇するべきだと感じる。VTuberとしてのプロ意識はないのか。

一通りスライド修正を終えたのでまたホスフィンに見せてコメントを乞い、先生にも送った。午前2時前就寝。

11/16(木)

午前9時起床。ホスフィンと先生からスライドに関するコメントが届いていたが、気力がなく布団でずっとラノベを読んでいた。

「レベル0の無能探索者と蔑まれても実は世界最強です」を読了。序盤、一気にスキルを手に入れて世界最強へと駆け上がるところはワクワクした。お手軽に強くなるシーンが楽しいのはこの作品に特有のことではない。その後も順調に強くなっていってくれればよかったのだが、ヒロイン二人とパーティーを組んだ後は停滞している印象を受けた。ソロのほうが強いんじゃないか。

午後3時前に布団から脱出。発表スライドへのコメントを確認した。ホスフィンからは文章とTeXの記法についていくつか指摘が来ており、言われるがまま直した。

先生からは研究の動機と意義を詳しく説明すべきと言われた。動機については自分の中でもかなり整理できているつもりで、スライドではコンパクトにまとめつつ必要に応じて口頭で補足することが可能なはず。なのでこちらについては実は追記の必要がないと考えている。

問題は意義について。もともと自分の興味本位で行った計算の結果であるため、他の研究に対する位置づけがはっきりとしていない。結構前からずっと言われてきたことなのにまだ回答を用意できておらず、泥縄式ではあるが今日は意義を探すためずっと関連する論文を読み返していた。

午後5時過ぎに学食で夕食。あとは逃避先として「人類最初の殺人」を読了したりもした。面白かった。人類最初の犯罪5種を描く連作短編集。歴史小説というにも古すぎるくらいの過去の話が展開されてかなり興味深い。五つ目の密室殺人の話が一番印象に残った。密室殺人というのはつまりトリックを用いた殺人。それを暴く過程に大変な緊迫感があり、またオチも良かった。

その緊迫感にやられて気力を使い果たした。結局今日はスライドに書けそうな文章を作れず、午前3時就寝。

11/17(金)

午前10時起床。学食で食事し、ラノベを買って帰ってきた。

セミナーまでスライド作成をもうひと粘り。意義を書くことは諦めたが代わりに関連する研究との比較を書こうと思っていて、これに関してさっき大学への往復中に重要なポイントに気づいたため、それを書くことにした。何度か読んだ論文でも別の論文で得た知識を元にするとまた新たな解釈ができて面白い。何かの締め切りに急かされなくともそういうことができるようになりたいものだ。

何とか文章をまとめてスライドを追加できた。午後2時に家を出て、天気が怪しかったため地下鉄で登校した。

まずは通常通りのセミナー。こちらに進学予定の学生と留学生がそれぞれ1時間ずつ話した。今日は特に詰まりもせずスムーズな発表で良かった。

その後建物を移動して自分の発表。結論から言えば非常に好感触だった。非公式の発表で思っていたより規模が小さく、普段のセミナーと同じノリでかなりのびのび喋ることができた。結局発表練習をしておらずスライドの前半で時間を使いすぎてしまったのだが、後半は証明パートで単に式変形するだけだし、前提知識のあたりを入念に話せたと思えばむしろ良かった点ですらある。また発表中、先生方から今後の研究についてかなり多くのコメントを頂いた。関連しそうな話題がその場で列挙されていくのは圧巻の一言だった。

学食で食事し地下鉄に乗った。帰宅せずそのままゲーセンへ。新曲を埋めた後14+を触り計10クレプレイした。「Odin」のSSSと「Caliburne ～Story of the Legendary sword～」のAJを出した。後者はなぜか今日ずっとめちゃくちゃ精度が良かったのに、緊張に耐えかねてラストのタップで赤を出し99AJを逃してしまった。残念。

Caliburne ～Story of the Legendary sword～ AJ！！！
最後数ノーツで99AJ逃して涙 pic.twitter.com/DsmzOrabCb
— こたつがめ (@kotatsugame_t) 2023年11月17日

CF前に帰宅。Yandex CupのSemifinalのupsolveが可能になっていた。当時書いて提出が間に合わなかったEのコードをずっと保管していて、投げたら通った。残念。

https://contest.yandex.com/contest/54740/run-report/97697460/

まだupsolveが不可能なので合っているかは不明。
週記（2023/10/30-2023/11/05） - kotatsugameの日記

シャワーを浴びて午後11時半からCF #909 div.3。

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

Aは $n$ が3の倍数でなければ即座に先手勝ち、そうでなければ後手が操作をキャンセルできるので後手勝ち。Bは約数全探索。Cはsubarrayを連続とは限らない部分列だと思い込んでしまい時間を溶かした。その時書いたdpの遷移を削って対応。Kadane's Algorithmっぽくなった。

Dは各 $a$ を2べきと奇数の積に直して何やかやと式変形したが、結論は $a_i\times 2^{-a_i}=a_j\times 2^{-a_j}$ と同じ。Eは最小値が先頭に来たら操作で列が変化しなくなるので、最小値より後ろは元からソート済みであることが必要。このとき操作によって後ろに送られてきた要素は適切な位置にswapで移動するから、十分条件でもある。

Fは謎。長さ $n-2$ のパスグラフを作って適当な位置に最後の辺を生やすだけ。Gはオイラーツアーの順に $p^{-1}$ を並べる。クエリは $x$ の部分木に対応する区間内に $[l,r]$ があるか判定すればよく、データ構造でできる。自分の手持ちは $\log$ 二つだが制約が微妙に小さいので十分速い。

全完、12位だったがopen hacking phaseで上から二人落ちて10位になった。

www.youtube.com

YouTubeの動画の収益化設定について、これまで動画の前・途中・後に流れる広告を個別にオフにできたのに、いつの間にか途中しかオフにできないようになっていた。前回まで動画横に表示される広告だけオンにしていたのだが、そのような設定の動画を新しくアップするのはもう不可能らしい。仕方ないので今回から動画の収益化自体をオフにしている。

収益化の申請が通った。広告の種類を設定するところで動画の前・途中・後に流れる広告をオフにしてみたが、これで本当に広告が消えたりするのだろうか。
週記（2023/07/24-2023/07/30） - kotatsugameの日記

日記を書いて午前7時前就寝。

11/18(土)

午後0時半くらいに目を覚まして3時間ほどラノベを読んでいた。また寝て、次は午後6時半起床。しばらく布団でスマホを触ってから起き上がり、食事とシャワーを済ませて午後9時からABC329に参加した。

Ｓｋｙ Inc, Programming Contest 2023（AtCoder Beginner Contest 329） - AtCoder

Aはsedでs/\B/ /gとした。Bはよい。Cは別の位置から取り出した同じ部分文字列を区別しないことに注意。Dは直前の当選者と $A_i$ だけ比較する。

Eで結構詰まった。操作を逆から考えると、 $S$ の中で $T$ に完全一致する場所を探し、そこから微妙にずらしてスタンプを重ねていくことになる。ずらすときは左右どちらか一方にどんどん進んでいくため、両方向1回ずつ貪欲にやってみるだけで十分。Fはマージテク。

Gは木dp。遷移を紙の上で詰めるのが面倒だったので書きながら考えた。入ってくるときのカゴを空だと見なし、そこからの差分のMAXを状態としたが、かなり苦しい方針だったようだ。例えば子が一つのとき、子の状態 $i$ から親の状態 $\max(A,B+i)$ に遷移するという形になるため貰うdpが書きにくい。配るdpだと子が二つのとき大変なことになる。それでも頑張って実装したら、最後の最後に配列外参照して1ペナ。

71分で全完。直後は4位だったものの、ペナルティを消化している間に二人ノーペナ全完が出て6位となった。3位とはかなり差が開いており、タイミングが悪いと言わざるを得ない。その二人はどちらも日本人かつ学生のようなので学生2位から4位に転落し罰金2万円……と思ったら一人は日本在住でないとのことなのでギリギリ賞金圏内に留まった。

Eは公式解説のBFSが一番頭を使わなくて済みそう。直前に $T$ の何文字目を使ったか持つdpでも解けるらしく、その方針でupsolveしておいた。上に書いたような考察をするよりは楽。Gについては、貰うdpが書ける解説のような状態の持ち方が楽なのは言うまでもない。自然な定義でもあるのにコンテスト中は一体何を考えていたのだろうか。

コードゴルフはCまで。AはAtCoderのジャッジの仕様上改行区切りでも問題ない。Nibblesで1次元の列をtransposeすると1要素ずつに区切った列が手に入るため、そのまま出力すればよい。BもNibbles。group byでuniqueとソートを一気に行った。列の先頭要素を取り出すのはsubscriptよりfoldr1。CはとりあえずPerlで書いておいた。

nibbles/Ops.hs at 62a912f5fead02162ccb77a9d4a553a180a7f685 · darrenks/nibbles · GitHub

www.youtube.com

午前0時からUniversal Cup 10回目、Harbinセットに出た。

The 2nd Universal Cup. Stage 10: Harbin - Dashboard - Contest - QOJ.ac

書く（C upsolve）

スマホの内部ストレージがいっぱいになったのでファイル操作アプリから画像ファイルを手動でSDカードに移動した。コピーの順序がバラバラだし、途中でSDカードがいっぱいになって中途半端に終わったし、ファイルのタイムスタンプも更新されてもうめちゃくちゃ。しかし写真管理アプリはメタデータでも見ているのかちゃんと表示してくれているので助かった。

しばらく日記を書いて午前9時半就寝。

11/19(日)

今日もまた午後2時という中途半端な時間に目を覚まし、2時間ほどラノベを読んだ。

二度寝してから午後7時半に布団を脱出。食事して少し日記を書き、午後9時からARC168に出た。

ALGO ARTIS Programming Contest 2023 Autumn（AtCoder Regular Contest 168） - AtCoder

Aは<の度に思いきり大きくすればよい。連続する>による転倒数だけ数えると答えになる。

Bのゲームは有名問題で、 $A\bmod{(k+1)}$ が山のGrundy数。 $k$ が十分大きければこれは $A$ と一致するから $\bigoplus A$ が非ゼロなら最大値なし。そうでないとき $k:=\max A-1$ とすることで $A$ の最大値だけGrundy数を0にできる。これで総XORが0からずれるかと思いきや、 $A$ の最大値が偶数個あるとダメ。

冷静になると $A$ の同じ要素をペアにして削除できる。真似っこ戦略のことを考えれば自明だが、問題を読んですぐGrundy数の話にしてしまったためすぐには気づけなかった。削除を行った上で残った最大値を使って $k$ を決めればよい。 $A$ が空になったら解なし。

Cはまず左からdpすることを考えた。操作前後で文字がどう変化したかをA、B、Cの3頂点の有向グラフで表し、最後にサイクルに分解して操作回数が足りるか調べる。ところがこれは状態数が多すぎる。ここで有向グラフを決め打つことを思いついた。異なる有向グラフからは必ず異なる文字列が得られるので、重複なく数え上げられる。

有向グラフは長さ3のサイクル1種類と長さ2のサイクル3種類で $O(K^4)$ 通りあり、それぞれどの位置の文字を変化させるかをcombinationで考える。有向グラフの全列挙は定数倍が軽いタイプの4重ループであり、数え上げ部分の定数倍があってなお高速だった。

Dはかなり迷走した。最初に区間dpを考えたが、1回操作した後分かれる左右の区間を独立に扱うことができない。それで長い時間左からdpしようとしていた。提出したらWAが出たのでランダムケースを試したら、小さいところでもボロボロ落ちてしまう。落ちるケースとにらめっこしているうち、これは不可能だなという気持ちになってきた。

再度区間dpに戻ってきたら一瞬で見えた。区間における最初の操作を考えるから左右が独立にならないのであって、最後の操作によって白から黒になるマスを固定するとちゃんと分割できる。見ている区間に収まる操作で固定したマスを黒く塗れるようなものがあるかチェックするのは前計算。

Eは解けなかった。Mongeっぽさがかなりあったので総和が $S$ 未満のときコスト1、 $S$ 以上のときコスト0となる辺を考えたが、残念ながらMonge性を満たさなかった。あとはslope trickを考えており、こちらは単に傾きを追加するような遷移にならないため不可能だった。

4完遅めで94位。AをNibblesでコードゴルフしておいた。文字列を<でsplitし、長さ $L$ の文字列に対し $1+\dots+L$ を計算すればよい。 $L(L+1)/2$ より格段に短くなる。

www.youtube.com

午後11時半からCF #910 div.2に出た。

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

Aは高々1回でできる。Bは値を大きくすることができないので、後ろから順に直前の要素を超えないよう均していく。直前の要素を $p$ とすると $q:=\lceil a/p\rceil$ 個に分割する必要があり、 $\lfloor a/q\rfloor$ と $\lceil a/q\rceil$ を適切に並べれば $\lceil a/q\rceil\le\lceil a/(a/p)\rceil=p$ より条件を満たす。

Cは $k-(n-1+m-1)$ の値を見る。負なら長さが足りない。奇数なら二部グラフ性より不可能。あとは長さ4のサイクルをぐるぐる回ったり2歩寄り道することで調整可能なので、構築は $k$ の値に依らないものが可能である。出力にかなり手間取ってしまった。

Dはおそらく同じ問題を何度か解いたことがある。 $a_i,b_i,a_j,b_j$ の大小関係を手で試した結果、改善するのは $\max(a_i,b_i)\lt\min(a_j,b_j)$ またはその逆だけだと分かった。このとき $|a_i-b_j|$ や $|a_j-b_i|$ の絶対値を外せるので、 $i$ と $j$ に分離して片方をセグ木に乗せた。

Eはソートをswapだと思う。 $t$ の先頭から順に $s$ で対応する文字を決めたとき、それより前にある辞書順で小さい文字は以降使えなくなる。このことからできるだけ先頭に近いものを取る貪欲が正当で、実際にチェックしてみた。

Fはタイプ1と2が自明でタイプ3が本質。スタートと二つの出口を連結にするため何マス必要か知りたい。連結にするならどこかに三叉路みたいなものができるのでそこをベースに考える、という典型がある。ただし今回出口がどこか決まっていない。そこで、多始点BFSで一方の出口からもう一方の出口に向かって進みながら、途中でスタートまでの距離を加算するようにしてみた。

同じ出口に戻ってくるケースを取り除くため、始点が異なる距離を二つ管理する。またスタートまでの距離を加算する必要があるため01BFSにはならずdijkstraが必要。ひいこら実装して出したら1400msで通った。

システスでFがTLEし5完50位。やはり $O(nm)$ 頂点のdijkstraはダメだったらしい。ただ答えが見つかった瞬間breakすると800msで通ってしまって非常に残念。Dは $|x|=\max(x,-x)$ で分解すれば手計算の必要がなかったようだ。さらにそこから必要ないものを取り除くと、 $+a+b$ と $-a-b$ が1回ずつできるdpにまでなる。

www.youtube.com

ラノベ「双子まとめて『カノジョ』にしない？」を読了。序盤から主人公に重めの過去があることは匂わされていたが、終盤で急に向き合い、あっさり決着がついてびっくりした。それまではずっと双子ヒロインとイチャイチャしていた。実際それこそがこのラノベのパッケージングを見て求めていたものだから、満足である。

シャワーを浴びて日記を書き、午前8時就寝。

今週初めは珍しく朝方の生活を送っていた。これだと街に出かけやすいが残念ながらそのような余裕はなかった。代わりに積読を消化できて、今週は7冊読んだらしい。そこから週末に向けてどんどん寝る時刻を遅らせ夜中のコンテストに焦点を合わせたのに、成績が悪くてがっくり。Universal Cupもちょっと振るわなかったなという印象だし、日曜日のARC・CFは言うまでもなくダメダメだった。