06/03(月)

午前6時半、緊急地震速報で目を覚ました。スマホを見たら富山湾で発生したとのことで、仙台でも速報が出るくらい大きな地震なのかと震え上がったが、結局ここは揺れなかったし、実家の揺れもさほどではなかったようだ。また寝た。

午前11時起床。しばらく週記を書き、昼休みが終わった頃合いを見計らって学食に行った。食後にラノベを受け取って帰宅。来るときは青空が見えていたのに食べている間に一気に曇ってきて、一雨降るかと焦った。

午後3時半からインターン先定例会に出席。進捗はない。待ちのフェーズではあるものの、できること・やっておいたほうが良いことは当然あるので、そういうものを進めていきたいところ。

勉強会は短期AHCにおける戦略の話だった。聞きながら自分の戦績を振り返ってみて、貪欲でうまく行った回がほとんどだということを改めて認識した。しかも強い貪欲を作れた先のマラソンテク、例えばプレイアウトやビームサーチで負けているようだ。自分はその間貪欲の些細な改善に固執し続けていた。だからまあ、まずはマラソンを頑張りましょうということになってしまう。

解散後は週記を書いていたが、途中で少しハーメルンに手を出した。先週から読んでいた「最強の魔法使い(自称)が暴れるそうです。RE：」を読了。リメイク前後で文章の質がガクッと下がり失速してしまったものの、何とか読み進めていくと徐々に改善されてきた。あるいは自分が慣れただけかもしれない。とにかく無事最終話までたどり着くことができた。

その最終話で主人公が死んでしまった！ありとあらゆる能力が剥奪され、苦しみながら死んでいった！まさかチートオリ主ものがバッドエンドになるとは思いもせず、まったく身構えていなかったので深い衝撃を受けた。救いを求めて続編をチラ見しても状況は変わらず、しかもエタっている。絶望。能力元の「東方異形郷」も悲惨な話らしいが、わざわざ再現してくれなくてもよかったのに……。

syosetu.org

落ち込みながら週記の執筆に戻り、午後11時過ぎに投稿。半からCF #950 div.3に出た。

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

Aはよい。Bは出力の説明を読まないと正確な問題がわからない。コードを書き上げてから読んだらMAYBEも判定する必要があってひっくり返った。Cは上書きなので後ろから見る典型。最後の操作以外はキャンセルできると思ってよいため、最後の操作が行えるかと、必要なだけの操作があるかをそれぞれチェックすればよい。Dは削除した位置の周りだけ真面目に計算し、残りは前計算した結果を使って判定する。

Eは行を値の集合と見て揃えた後、列の並び替えを求めてすべての行で一致しているか調べた。FはF1を飛ばし、直接F2を解いた。 $c$ の昇順に並べて $r$ の累積MAXを取ると経路が求まる。累積MAXの更新点を一つ消したとき、新たに更新点となるのがどこかわかればよく、候補がdisjointなので線形時間で解いても合計 $O(k)$ で十分高速。F1とF2は微妙に異なる問題だが、F2のコードをそのままF1に出しても通るようにしてくれていてありがたい。

Gは適当に決めた根からのパスのXORとして管理すると、深さが奇数の点に対するXOR更新と、定数をXORしたときの最大値の取得になる。深さの偶奇で分ければbinary trieで対応可能。ライブラリが空集合のMAXを取ろうとすると壊れる実装で、手元では動いたため気づかず提出してしまったが、幸いサンプル1で落ちてくれたためペナを逃れた。

1時間で全完して4位。

www.youtube.com

森見登美彦さんも参加されているアンソロジー小説が近く発売されるらしい。慌てて注文した。

tomio.hatenablog.com

ところで、大学生協で受け取るための注文サイトが「大学生協のオンライン書籍注文サイト」から「オンライン書店Honya Club.com」に変わる。すでにアカウントがあって何事かと思ったが、メールを掘り返してみると2020年の9月くらいまで使っていた形跡があった。サイトが変わって、4年越しにまた戻ったということらしい。注文履歴は消えていて残念。「書籍注文サイト」があり得ないくらい重かったので、快適になってシンプルにありがたい。

オンライン書店Honya Club.com

シャワーを浴び、洗濯して午前5時就寝。

06/04(火)

午前9時半起床。降水確率40%だが原付で登校した。

午前10時半からZoomでオンラインセミナー。4月にお越しいただいた先生に、再度セミナーをしていただいた。前回紹介していただいた論文を指導教員以外の先生も交えてセミナーで精読しているため、話の内容もよくわかり、多少の議論もできて有益だった。特に大局的な話、他研究と比較しての位置付けについて話していただけたのが非常にありがたい。

午前10時から2時間弱は招いた先生によるセミナー。
週記（2024/04/08-2024/04/14） - kotatsugameの日記

解散後、指導教員の先生と教室で話していたら、次の利用者の先生が来たので退散した。この先生には自分がB2の頃、群論の講義と演習でお世話になったことがある。今日、自分の顔を見てすぐ演習で解いた問題を言い当てられ、本当にびっくりした。5年前のことなのによく覚えていらっしゃるものだ。当時発表で炎上してしまい苦い思い出となっているのだが、それを理由に覚えているという雰囲気ではなかったので救いになった。

セミナーで紹介していただいた本を資料室で借り出した後、学食で食事。ICPCの国内予選ルールが変更されたのを知った。特に事前準備の許可が大きいと思った。多分ライブラリのコピペがOKになったということだろう。

今年の ICPC 国内予選のルールですが、昨年から大きな変更があります。入力データのダウンロードから6分以内に正答を提出しなければ、得点とはなりません。また、ライブラリ等の事前準備を許可するほか、問題数が全9問となります。各自、ルールをご確認ください。https://t.co/tAY2RR4FEJ
— ICPC2024JP (@icpcjapan) 2024年6月4日

午後2時過ぎに帰宅。ひとまずPCの前に座ったものの、なんとなく眠くて何かする気にならず、布団に戻った。午後3時半から午後7時くらいまで寝ていた。目を覚ましてからもPixiv小説を読んだりYouTubeを見たりで、さらに3時間くらいダラダラ過ごしていた。

再来週の月曜日にインターン先勉強会での発表を控えているため、題材を探し始めた。最近解いた問題から何かないかと調べてみたものの、どれもピンと来ない。前回の2次元遅延セグ木は同様の考え方で決めたテーマだった。それがTwitterで少し話題になって嬉しかったから、今回も興味深いものを……と思っているものの、暗雲が漂う。

日付が変わり、TCBの2024/05回が終了した。3位。

https://techful-programming.com/techful/event/5706

5問目まではよい。6問目は冷静になると $k$ として $N$ の約数だけ考えれば十分なので、愚直にチェックできる。7問目は各行各列のpopcountだけ覚えていれば総和の差分更新が可能。10分かかってギリギリではあったものの、何とかここまで理論値で通せた。

8問目は問題文がカス。まずスタートマスが定義されていない。 $(a,b)$ と $(c,d)$ が入力で与えられて片方がゴールならもう片方がスタートだろうとは分かるものの……。また、氷の床みたいな設定で移動できるか聞くのだからそのマスにピッタリ停止できるか判定するものだと思ったが、違うらしい。ここの定義が曖昧なのはどうしようもなく、解釈に失敗して1WA。時間ボーナスも少し削られて-12ptとなった。

9問目は操作が可逆なので、それぞれ辞書順最小になるよう操作して比較した。実験から見出した規則を頑張って実装しても全然合わなかったが、改めて考えると2連続の1を作って削除・挿入する方針で説明がつくことに気づき、そこそこシンプルな実装に落ち着いた。実は削除し切った段階で比較しても同じであり、辞書順最小の列を作ることに固執する必要はなかったらしい。ランダムケースで試して提出。WAこそ出なかったものの73分かかってタイムボーナスが消え、-42pt。

10問目は行列累乗。 $N$ がクソデカ整数だが、2分の1のために毎回桁数に対する線形時間をかけても間に合うので適当に実装してよい。これは20分で実装が終わり、理論値だった。

11問目はbitを別の数の同じ桁に移すことが可能なので、増やせるか考える。 ${00}_{(2)},{10}_{(2)}$ を ${11}_{(2)},{01}_{(2)}$ にできるので、最上位bit以外ならかなり自由に扱えそう。最上位bitは一度減らすと戻せないので、全部の数でそこが立った状態を保ちたいなら一つ下の桁以降を見て解くことにし、そうでないなら先ほどの議論からほとんど何でもできるということになった。愚直と比較して提出。27分かかって-6pt。

12問目はとんでもない時間がかかってしまったが、結論はシンプル。aa...aとbb...bを取り除けるだけ取り除いて残る文字列が同じものをすべて作れるので、逆に残った文字列に挿入する方法を考えて数え上げる。重複して数えないようにするため、ある文字の前に挿入する際は、それと異なる文字が来るようにした。

あとは削除できる文字列の数え上げとなる。FPSで立式すると $f=x\left(\frac{1}{1-f}\right)^{K-1}$ になって、収束が遅すぎるしニュートン法もうまくいかなかったものの、小さい $K$ に対してOEISで検索したらそれぞれ一般項が出てきて、 $K$ に関しても一般化できる形だったためうまくいった。 $[x^i]f=\binom{Ki-2}{i-1}/i$ らしい。

ちなみにその後 $g:=\frac{1}{1-f}$ を計算しており、こちらで式を書き直すと $g=1+xg^K$ とよりシンプルな形が出てくる。まあ一般項は大して変わらない。 $K=2$ では意味的にもカタラン数だとわかるが、その一般化として研究対象になっているようだ。

$f$ が計算できるようになった段階で、それを使ってdp遷移するコードを提出したものの、TLEしてしまった。冷静になって見直すと、やっていることは $g^c(1+(g-1)+(g-1)^2+\dots)$ の計算に他ならない。ここで $c$ は残った文字列の長さに1足したもの。二分累乗法を使って出しなおしたら通った。3時間と1ペナで-68pt。タイムボーナスもないのになぜ焦って提出したのか理解不能。

potato167さんの解説ブログも貼っておく。

potato167.hatenablog.com

午前1時頃に寝てしまった。

06/05(水)

午前8時起床。しばらく布団でゴロゴロした後、セミナー準備に取り掛かった。今日の夜は競プロサークルの確定新歓があるため、それまでに完成させたいところ。

……のはずが、完成間近で論文の証明にミスがあるのを発見し、修正が間に合わなかった。仕方ないので中途半端な資料を、夜中に更新するかもと言いつつセミナー参加者に送信。シャワーを浴びて午後6時頃に家を出た。

確定新歓は昨年と同じ店の同じ焼肉食べ放題。ただし今年はホスフィンが来ておらず、ほかのM2も軒並み不在にしていて、自分だけちょっと歳が離れていた。調子に乗って昔話、それこそコロナ以前の体験談を喋ってしまったが、良くない老人仕草なので控えめにするべきだったかも。競プロの実装に関して質問されて嬉しかった。

食事 pic.twitter.com/hRui6yVxZX
— こたつがめ (@kotatsugame_t) 2024年6月5日

今日はサークルの確定新歓の日だった。
週記（2023/05/22-2023/05/28） - kotatsugameの日記

特に二次会もなく解散。その足でゲーセンに行き、閉店まで18クレプレイした。未プレイだったLv.15 4譜面を触り、LUMINUSバージョン稼働以来およそ半年ぶりにレーティングポゼッションが復活した。オーバーパワーが99%をギリギリ超えるくらいで、今の基準だとプラチナらしい。

特に「Makear」と「ラストピースに祝福と栄光を」が体力譜面で大変だった。前者は前半がうまくいった回で後半耐えたスコアであり、伸びしろがない。後者は最初の数回だけ大宇宙ステージ地帯の両手トリル餡蜜がうまくいったのだが、後半が振るわなかった。逆に後半が慣れてきたころには前半でポロポロ失点するようになってしまい、なんとも噛み合わない結果に。

15を触ってポゼ復活 pic.twitter.com/it1cbnNlnb
— こたつがめ (@kotatsugame_t) 2024年6月5日

満腹なので食事はせず、ドンキにも寄らずに帰宅した。シャワーを浴びようとしたものの眠気に負け、しばらくカーペットに横たわって寝ていたらしい。午前2時くらいに目覚め、何とかシャワーを浴びて再度就寝。結局セミナー準備の続きはできなかった。

06/06(木)

午前11時起床。昨日できなかったセミナー準備を行い、ミスのあった証明にも代わりの正しいものを用意できた。午後1時過ぎ原付で登校。夕方から降水確率40%らしい。

学食で食事して、半からセミナー開始。前回準備した分の残りを話そうとしたら内容をあまり覚えておらず、頻繁に資料を確認してしまった。また細部はいくらか飛ばそうと思っていたのに、どこを飛ばすべきか考えておらず、結局全部丁寧に話してしまった。今週準備していた部分は丸々残ってしまって次回話すことに。証明のテクニックはもう出尽くして、残りは面倒な計算パートが多いので、どう説明するか考えておかなければならない。

曇り空が怪しくなってきたので帰ろうとしたが、この後後輩と先生が話し合いをすると聞いて、興味本位で同席することにした。ただし話し合いといっても次回のセミナーの確認だけだったようだ。先生が去ったあとは後輩が読んでいる教科書についてしばらく二人で議論した。一段落して学食に行ったら今度は雑談に花が咲き、午後8時前になって解散した。

帰宅後、COSS2024への参加申し込みを行った。セミナーの合間に先生に相談したところ、問題なく許可が出た。何かが起こる気配も今のところないため、冬のLAシンポジウムみたいにキャンセルすることにはならないはず。

COSS2024 Home

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

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

Aは、Bobはできるだけ短い区間を選ぶべきなので、隣接項のMAXのMIN引く1が答え。Bは $i\oplus j=x\oplus y$ に加え $i\oplus(i+1)=j\oplus(j+1),(i+1)\oplus(i+2)=(j+1)\oplus(j+2),\dots$ が条件となるので、 $i$ 、 $j$ ともに下のほうのbitは一致し、特に全部0になっていてほしい。つまり $x\oplus y$ を割り切る最大の2べきが答え。

Cは整数性を忘れると $\sum 1/k\lt 1$ が条件。判定を考えると $A:=\mathrm{lcm}(1,\dots,20)$ を使って $\sum A/k\lt A$ か見る方法が思い浮かび、よくよく観察するとこれがそのまま答えにもなっている。つまり $x:=A/k$ 。Dは $p$ を全探索する。先頭から $p-1$ 文字と $p$ 文字目以降がそれぞれ $k$ -properになっていて、かつ操作後に繋がる部分にも少し条件があるが、チェックは簡単。Eは45度回転すると必ず2点が軸に並行な直線に乗る。

Fは有向完全DAGのハミルトンパスを作るのと同様に再帰を考えたら解けた。補グラフで説明すると見通しが良いので、そうする。次数の条件も反転していることに注意。 $d=1$ で聞いて、もし $u\ne 0$ が返ってきたなら、頂点 $v$ は次数1で辺 $(v,u)$ と接続している。つまり $v$ が削除された今、 $n-1$ 頂点 $n-3$ 辺となっている。そのハミルトンパスを再帰的に作ると、どちらかの端点には $v$ を繋ぐことができるため、元のグラフのハミルトンパスが得られる。

では $u=0$ が返ってきた場合はどうするか。この場合孤立点 $v$ を削除しており他の頂点の次数は一切変化していないから、次に $d=2$ で聞いたとき返ってくる頂点は次数が0または2となっている。それぞれ $u=0$ と $u\ne 0$ に対応するため、 $u\ne 0$ だった場合は $n-2$ 頂点 $n-4$ 辺のグラフが得られており、先ほどと同様再帰的にハミルトンパスが構成できる。以下 $u=0$ の間 $d=3,4,\dots$ と聞いていけばよい。

全完3位。Fで $d=1$ を聞いて $u=0$ が返ってきた後は、 $d$ を最大値にして次数最大の頂点を削除するという方法もあるらしい。この場合辺の数が $n-2$ 本「以下」の状態で再帰することになるが、確かに特に問題なく構築できる。

www.youtube.com

「冬季限定ボンボンショコラ事件」で描かれた中学生時代の小佐内さんは、挨拶で何度か「おわあ、こんばんは」と言っている。何の意味があるのかわからなかったのだが、萩原朔太郎の詩に由来することを知った。

ラノベを読んで午前8時半就寝。

06/07(金)

午後2時半起床。CHUNITHMのバージョンアップ情報が流れてきた。ここ最近のイベントが全部06/19に終了するところから何となく予想はついていたが、削除される楽曲については予想外。ボカロジャンルに属していても人間が歌っていればポプアニジャンルと同じ感じで消えていくのだろうか……。ただしこの理論では「FREELY TOMORROW」が消える理由がよくわからない。

info-chunithm.sega.jp

ラノベを2冊読んだ。1冊目、「異能学園の最強は平穏に潜む」3巻。今回は主人公が最初から大きく動いていて楽しかった。読んでいる最中はあいまいな描写に動揺したものの、振り返ってみると全編無双シーンと言える。2巻3巻で主人公の能力が加速度的に明らかになっているが、言っていることが本当なのか怪しいので底はまだ見えない。

2冊目、「孤高の華と呼ばれる英国美少女、義妹になったら不器用に甘えてきた」。主人公がスポーツ熱心な好青年で非常に印象が良い。ヒロインの隣にいても違和感がないというのは重要だと思う。野暮ったかった見た目を整え、努力して違和感を消す主人公もいるが、最初から評価が高いほうが振る舞いにも自信を感じられて好み。

午後7時くらいになって外出。歩きながらハーメルンの「天才TS美少女はわからされたい！」を読み切った。自分はチート主人公で才能に満ち溢れている、だからなんでもやってみればできる、という自信の持ち方が少し危なっかしいと思った。地に足がついていなくて怖い。

syosetu.org

立ち食いそばを食べ、本屋で本を買ってからゲーセンに向かった。今日は金曜日なので金曜奴の集まりを避け、GiGO仙台へ。閉店まで18クレプレイした。家を出る前にバージョンアップで消える楽曲の称号を調べてきており、もっぱらそれらを集める作業をしていた。

特に14+の「紅」と「]-[|/34<#!」はAJを出していなかったので、曲名称号を取得するため頑張って詰めた。「]-[|/34<#!」の最後のフリックが全然入らなくて気が狂いそうになった。腕はボロボロになったものの、最終的にはどちらも出せたので、楽曲追加当時からの成長を感じた。

削除される譜面の称号を回収したよ！ pic.twitter.com/6YKeuybS7t
— こたつがめ (@kotatsugame_t) 2024年6月7日

別のゲーセンのトイレを使ったら店員と目が合ったので、申し訳程度にもう2クレプレイ。立ち食いそばを食べた後ドンキに寄った。税抜100円の「つぶつぶチョコ」という商品を発見し、安さに惹かれて5袋買ったのだが、帰ってきて食べてみたらチョコの糖衣部分のケミカルな味が舌に合わなかった。まさかこの世に不味いチョコ菓子があるとは。5袋もあるのにどうすればいいんだ。

今日買ってきた本のうち1冊は、予約に失敗したSAOの28巻。

SAOの新刊が2年弱ぶりに出るが、すでに予約が品切れとなっていて残念。
週記（2024/05/20-2024/05/26） - kotatsugameの日記

ところで現在、hontoというサイトのMy本棚機能を使って本の購入記録をつけている。こうしておくとhontoの商品ページに表示が出て、買った本かが判別しやすいのだ。ところが今日登録しようとしたらできなくて焦った。どうやら紙の本に関してはサービス全般が終了し、電子書籍だけのサイトに変わったらしい。しょうがないので電子書籍として登録しておいた。紙の本の登録は最終的に703冊に上った。

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

06/08(土)

午後1時半起床。午後2時からUniversal Cupに参加した。先週トライアルコンテストを終え、いよいよシーズン3が本格始動する。今日は第1回目のSt. Petersburgセットだった。

https://qoj.ac/contest/1696

書く

動画準備を整えた後はラノベを読んで過ごし、午後9時からABC357に出た。

SuntoryProgrammingContest2024（AtCoder Beginner Contest 357） - AtCoder

書く

www.youtube.com

「極めて傲慢たる悪役貴族の所業」3巻を読了。語り手の切り替えがかなり頻繁にあって読みにくかった。語り手となるキャラも多いし、別々の場所の出来事が並列して描かれるのでなおさら。特にラストは視点を切り替えまくって風呂敷を広げるだけ広げ、回収はすべて次巻以降に丸投げという印象で、今のところ何が起こっているのかよくわからず混乱中。ただ中盤までは話もそれぞれ一区切りついて面白かったということを明言しておく。

午前5時就寝。

06/09(日)

午後1時起床。昨日今日とアーケードのあたりで「東北絆まつり」という祭りが開催されているらしい。東北6県の有名な祭りが一堂に会するということを数学科の友人から聞いて、ちょっと行ってみようかなという気になっていたのだが、調べたら昨日の人出がものすごかったらしくて萎えた。

布団でラノベを読んでいた。「血の繋がらない私たちが家族になるたった一つの方法」を読了。ヒロイン二人の導入から恋愛トラブル、偽カップル成立までがテンポ良く描かれて面白かった。恋愛トラブルの発端となった男子は、最初の描写だけだと根暗なオタクくんに見えて少し苦い気持ちになったが、実際は見た目良し・頭良し・運動神経良しのかなりの好青年でびっくり。主人公とヒロインの偽カップルに対し正々堂々と向き合っており、こじれるような気配がなくてよかった。

午後6時くらいに寝落ちした。次に起きたのは午後10時。シャワーを浴び、食事して午後11時半からCGR26に出た。

Dashboard - Codeforces Global Round 26 - Codeforces

書く

www.youtube.com

ラノベ「血の繋がらない私たちが家族になるたった一つの方法」2巻を読了。この巻も面白かった。ヒロイン二人の過去についての話がメイン。主人公にも何かあるようだが、まだほとんど何も明かされていない。ラストの体育祭のシーンはなかなか過激でよかった。そういえば、ヒロイン二人を侍らせる主人公に対する周囲の嫉妬というのはほぼ描かれていない気がする。体育祭での行動にはどんな反応が来るだろうか、3巻冒頭が楽しみ。

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