12/11(月)

午後2時起床。

今日は購買に行く。10日ほど行けていない間にちょうどラノベの新刊発売日が集中していて、今予約したラノベが21冊受け取り待ちになっているようだ。発症から1週間経ったし、症状も昨日の日記にはあれこれ書いたがまあ軽快したと言ってよいだろう。仙台市が外出を控えることを推奨する期間は過ぎたと認識している。

本当は購買だけのつもりだったのにうっかり学食に吸い込まれて昼食を摂った。これは配慮が足りなかったかもしれないが衝動に負けた。勘弁。辛めのカレーを食べても喉が痛くならなくて快復を実感した。その後無事ラノベを買って帰宅。

└( ＾ω＾ )┘♪ 買った♪└( ＾ω＾ )┘♪ 買った♪ pic.twitter.com/dWwc5icvYK
— こたつがめ (@kotatsugame_t) 2023年12月11日

午後3時半からインターン先定例会に出た。先週は何も進捗がないどころか1on1をすっぽかすという負の貢献を果たしてしまった。しかもひと月前の「あと1か月ほど頑張る」話の始末をそろそろ付けなければならない。もう1週間待ってほしいと伝えたが、果たして今週何か進捗を産めるだろうか。勉強会はKaggleのコンペ参加記だった。

とりあえずもう1か月ほど頑張ってみることになった。
週記（2023/11/13-2023/11/19） - kotatsugameの日記

解散後すぐ先週の週記を投稿した。体裁だけ整えた穴あきまみれの状態だが、実は明日セミナー発表があるため先にその準備をしなければならない。

そもそも眠気が酷かったので3時間ほど仮眠を取り、午後9時半から準備を開始した。完成したのは午前5時。シャワーを浴びてゴミを出し、午前7時に寝た。

12/12(火)

正午起床。

今週木曜日に迫ったチュウニズムの大型アップデートに関する新情報が出ていたが、その中でホールド・スライド始点の黄タップに関する仕様変更がTLで話題になっていた。自分の知る歴史的経緯をメモしておこう。

12/14(木) CHUNITHM LUMINOUSの新要素まとめ！｜CHUNITHM LUMINOUS (チュウニズムルミナス)｜セガ新作音ゲー

ホールド・スライド始点が黄タップになっている「ように見える」配置はこれまでも頻繁に使われてきたが、実は単に始点と黄タップが重なっているだけであり、ちゃんと始点の判定は残っていた。つまり迂闊に擦ると赤やアタックの判定が出てしまう。例えば「Sakura Fubuki」なんかはフリックの直後にそれが配置されており、しかもBPMが微妙に遅いせいで非常に赤が出やすかった。

NEW PLUSの最初に追加された「タイムカプセル」はその悪名高い黄タップ付き始点でタップスライドをやらせる譜面で、バージョンアップの直前生放送で譜面が公開されたときは違法配置だと騒がれた。しかしどうやら赤が出ないらしい。これが、ようやくホールド・スライド始点が真に黄タップになった瞬間だった。

ただこのタイミングですべての譜面の判定が更新されたわけではなく、新しい判定が適用されるのは新規に追加される譜面の一部のみだった。これは制作者名の先頭に「【Ex】」があるかどうかで見分けることができる。そんな初心者お断りみたいな運用がかれこれ1年半ほど続いていたわけだ。

そんな中、いつからかULT譜面は「【Ex】」の有無にかかわらずすべて新判定が適用されるようになっていた。これは公式から告知があったわけではなく、プレイヤーが気付いてSNSで広まった事実であったはず。それからさらに時間が経過して今日、新バージョンからすべての譜面に新判定が適用されることが告知されたのだった。

この仕様変更で簡単になる譜面がいくつもTLに流れてきて、眺めているうちにセミナーまで時間が無くなってしまった。午後0時半ごろ急いで家を出て、地下鉄で登校。昼食は購買で買ったパンを詰め込んだ。

午後1時からセミナー開始。まずは自分の発表。もともと3時間の予定だったが、喉がまだ本調子でないということで1時間半で一旦切らせてもらった。間に留学生の発表を1時間半。今日は特に複雑な話もなくスムーズに終わった。その後自分がさらに1時間半発表して今日は終わり。

かなりねっとり喋ったので用意した分が終わらなかったが、自分の修論とあまり関係なさそうなので残りはスキップすることにした。次のセミナーでは別の内容を話す。つまりまた準備をしなければならないということ。

午後6時解散。学食には行かず家にも寄らず直接ゲーセンに向かった。上でチュウニズムの大型アップデートの話をしたが、そのタイミングで消える要素がいくつかあるため称号を集めたりマップを走り切ったりしておきたい。アップデートが発表されたのは12/01なのにそこから今日までゲーセンに行くタイミングがなかった。あと2日でどこまでやれるか。

とりあえず今日は閉店まで26クレプレイし、消える称号のうち一人プレイで取得できるものを軒並み取得することに成功した。軒並みと言ったのは赤のAJ称号を無視しているから。「一眼一足」は「モノノケ・イン・ザ・フィクション」の1速AJ称号で、そもそも普通のAJにすら苦労した覚えがあるしさすがに厳しいかと思ったが、案外すんなり出た。フィールドウォールを14にしてあとは全押し！

称号狩りのゾロ pic.twitter.com/z1r7zwziET
— こたつがめ (@kotatsugame_t) 2023年12月12日

先ほどは挙げなかったがデジタルアイテムキャンペーンも明日まで。こちらは余裕で終わった。ただマップについては到底走り切れない量が残っている。せめてNEWのマップは全部消化しておきたい。今日もしゃかりき走ったので残り1200マスほどとなり、明日も同じくらいクレを投入すれば終わる見込みだ。

今はデジタルアイテムキャンペーンも開催中で、12/13までにあと10クレ費やす必要がある。
週記（2023/11/27-2023/12/03） - kotatsugameの日記

ラーメンを食べて帰宅。眠気に負けてシャワーを浴びる間もなく寝落ちした。午前1時くらいだったと思う。

12/13(水)

午前6時くらいに目を覚ましてそこから4時間眠れなかった。ハーメルンで「【全９話】魔術情報瓶詰学・秋季課題レポート」を読了。興味深い形式の話だがオチが弱かった。

syosetu.org

よっぽどそのままゲーセンに行こうかとも思ったがこの睡眠時間では夜まで耐えられない。頑張って寝た。次は午後2時に目覚ましで起床。

シャワーを浴びて学食で食事し地下鉄に乗車。まずゲーセンではなく仙台駅に向かいみどりの窓口で帰省用の切符を買った。うっかり12/28にオンラインとはいえセミナー発表を入れてしまったため、帰るのは12/29の予定。帰省ラッシュのピークはギリギリ外していると思っていたのに、大宮駅→富山駅はもう席がほとんど残っていなかった。何とか確保したのは夕方の列車の、3人掛け真ん中の席。

そこからゲーセンに行った。着いてすぐの午後5時前の時間帯はチュウニズム8台全部が埋まっていて絶望したが、早々に学生が消えた後は延々連コできた。今日は閉店間際までで31クレ投入し、ちゃんと予定していたマップを走り切った。

駆け込みでマップ走った（イロドリミドリとオンゲキは知らん……） pic.twitter.com/1CI3At70BV
— こたつがめ (@kotatsugame_t) 2023年12月13日

ほかにも進捗がある。まず、1速称号を取るのが思ったより楽しいことに昨日気づいたのであらかたかき集めてきた。やはりフィールドウォールは最強。「月に叢雲華に風」だけ大昔にチャレンジしたことがあって、その時は散々な結果だったことを覚えているが、今日は通常スピードで譜面をおさらいした次のプレイでもうSSSが出てしまった。

1速称号集め pic.twitter.com/K1bBaxMWc6
— こたつがめ (@kotatsugame_t) 2023年12月13日

また、「千本桜」の理論値を出した。いわゆる言ノ葉カルマ配置は始点に黄タップが乗っていないので明日からの新判定でも別に簡単にならない。65-68小節はエアーの手を使って取り、他は必死にお祈り。61-62小節の小粒では一度も失敗しなかった。「六兆年と一夜物語」でもここ最近失敗した覚えがない。昔に比べエイム力が上がったことを実感する出来事である。

千本桜理論値、その他 pic.twitter.com/JzRHVJWFrZ
— こたつがめ (@kotatsugame_t) 2023年12月13日

帰りにホスフィンと合流してラーメンを食べた。日付が変わってから帰宅。

ホスフィンにお薦めされたVRChat実況者の動画を2本ほど見た。初対面の人に話しかけに行く積極性を持ち合わせていないため、そういう人が跋扈しているVRChatは異世界のように見えた。パーフェクトコミュニケーションを連発する実況者が見ていて爽快だった。ネタがきわどいのには冷や冷や。うっかり話し相手の逆鱗に触れてしまったりしないのだろうか。

www.youtube.com

シャワーを浴びて日記を書き、午前6時くらいに布団に入った。それからハーメルンを読んでいるうちに寝てしまったらしい。午前8時過ぎか。

12/14(木)

午後6時半に目を覚ましたが、学食に行こう行こうと思いつつも布団から出られなかった。1時間ほどYouTubeを見続けて学食が閉店したくらいにまた寝た。

午後11時半起床。明日のセミナー発表の準備をする。今週火曜日のセミナーは単に追加されただけであり、毎週金曜日の定期セミナーも変わらず開催される。これは午前6時半までかかった。量が月曜日に用意したものより少ないためかかった時間も少し短いが、開始時刻が遅かったので完了時刻も遅くなってしまった。

シャワーを浴びて布団に入った後うっかりなろうを読んでしまった。午前8時就寝。

12/15(金)

午前11時起床。スマホを触っていたら二度寝するタイミングを失ってしまった。

少し早めの正午に家を出て地下鉄で登校。図書室に寄って借りている教科書の貸出期間延長をしようと思ったが、昼休みの時間帯でできなかった。学食に行ったら半を回っているのにまだ長い行列ができていて、諦めて購買でパンを買って食べた。

午後1時からセミナー。まず1時間半はこちらに進学予定の学生による発表だった。もともと先週金曜日に予定されていたものだったが自分の体調不良でここにずれてきた。いつも発表原稿の字が上手くて良いなあと思っている。また、自分はよくわからない書体の文字があると全部mathcalで書いてしまうので、それらを教科書に揃えている点でも感嘆。

次は自分の発表で、2時間半。用意した分が終わるまで喋り散らかした。かなり最近出版された論文の前半の内容が教科書の今日読んだ箇所にほぼそのまま書いてあって仰天。手法自体には新規性はなかったらしい。その論文は連作の一部らしいので、自分が文脈を知らないだけかもしれない。

最後に留学生の発表だが、これも2時間半ほど続いた。よく知らない概念に関するよくわからない定義のものを数え上げていて意味不明。実例を用意し文言の解釈についてあれこれ議論しながら計算していたのでこんなに時間がかかった。結局セミナー後に聴衆の一人から論文の記述が間違っていたと報告された。徒労。

終わるとちょうど学食が閉店した時間だった。コンビニでパンをしこたま買い込んで帰宅。

Yandex Cupの賞金受け取りの案内が来ていたので作業した。この案内自体から始まり埋めるべきフォームに書くべき書類まで全部ロシア語で勘弁してくれという気持ちに。機械翻訳片手に立ち向かったがロシア人向けの記入項目が多く、よくわからなかったので運営にTelegramでいろいろ質問した。リアルタイムで返信があって助かる。銀行口座よりPayPalに送金してもらったほうがお互い簡単かと思ったものの、そういう選択肢はないらしい。

来週末にホスフィンと家飲みをする予定なので、お酒やボドゲをAmazonで注文しておいた。翌日もセミナーがあるので控えめに。ボドゲも1種類だけ買った。

うっかりTrialsシリーズの淫夢実況を見て時間を溶かしてしまった。このゲームの実況が好きというよりは語録洪水系の淫夢実況が好き。

www.nicovideo.jp

シャワーを浴びようと思ったのに布団に倒れこんでしまい、無事寝落ちした。午前1時過ぎだったはず。

12/16(土)

朝方1時間ほど起きてYouTubeを見ていた。本格的な起床は午後1時55分、目覚ましによるもの。慌ててPCの前に座り午後2時からUniversal Cupに参加した。今日は14回目、Southeastern Europeセット。

書く

解散して動画の撮影準備を整えた後10分でシャワーを浴びた。午後9時からABC333。

Toyota Programming Contest 2023#8（AtCoder Beginner Contest 333） - AtCoder

Aはよい。Bは一目見てABC305-Bを思い出し嫌な気分になったが、今回はマジックナンバーの埋め込みを求められているわけではなかった。文字コードの差 $d$ を求め $\min(d,5-d)$ で判定。

Cはちょっと難しかった。レピュニット数三つの和と先頭から数桁に1、次の数桁に2、残りに3が並んだ数は一対一対応するので、後者の形で全探索した。その後サンプル3を試すときに答えがそれほど大きくならないことを知った。レピュニット数を列挙して直接全探索できるなら確かにC問題。

Dはやるだけ。なぜDに置いてあるのか理解できない。Eは敵に出会う度直近のポーションを拾ったことにする貪欲が正当。 $K$ を求めたり復元したりと微妙に手数が要求されて面倒だった。

Fはちょっと詰まった。 $\mathrm{dp}_n$ を「 $n$ 人並んでいるとき最後尾の人が最後に残る確率」と定め、これを $n$ の昇順に求めた後答えを計算した。どちらのステップも $O(N^2)$ 。 $\mathrm{dp}_n$ の計算は両辺に $\mathrm{dp}_n$ が出現する等式を解く問題になるので、ちゃんと移項して求める必要がある。最初これに気付いておらず、サンプルが合わなくて少し固まっていた。

GはStern-Brocot treeやるだけ。同じタイプの問題、つまり分母分子に上限がついたときの探索をYandex Cup予選Fで解いていたので、それを思い出しながら書いた。分数を比較する必要があるが、雑に見積もると $|r-p/q|$ の分母分子が10²⁸オーダー、それ二つの比較が最後に来るため10⁵⁶オーダーの整数を扱わなければならない。256bit整数を使う方法がわからなかったのでRubyの有理数クラスに逃げた。実行時間的にはかなり余裕があるので安心。

36分半でノーペナ全完し6位。GはPythonのFractionsモジュールにlimit_denominatorというそれそのもののメソッドが用意されているらしい。またC++で解く場合10⁵⁶オーダーの整数という話をしたが、 $r$ の分母が2回現れるのでキャンセルすることで10³⁸になりギリギリ収まるとか、 $r_1\lt r\lt r_2$ のとき $r_1+r_2$ と $2r$ の大小を比較することでどちらが近いか分かるとか、いろいろ方法はあるようだ。

コードゴルフはAのみ。 $N$ を $N$ 回繰り返すといういろんな言語にありそうな処理だが、こういうのはやはりNibblesが最強で、自明な^$@が最短……と思っていたら&@に負けていた。どうやらjustifyを使うと&@$$と書けて、こちらではImplicit Argsで2個も省略できるらしい。

www.youtube.com

午後11時半からCF div.2。ABCをとっとと全完したので動画の投稿作業が間に合った。

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

Aは $\max(n,m)$ 。ほぼサンプルからエスパーしたようなものだが証明もすぐできた。Bは難しい。葉の個数に注目すると解けた。葉が4個以上だと1手で最大2個ずつ消せるはずなので、2個のとき1手、3個のとき2手というところから必要な操作回数が求まる。

Cは最初に操作した文字たちがその後ずっと操作され続ける。正確には後ろから1文字ずつ先頭に行って消えていくので、最終的にはreverseされる。これでまずソートできるかの判定が行えて、reverseにかかる手数は辞書順最大の文字が何文字あるかで決まる。

Dは難しい。逆順列で考えるとコストは $\sum_{i=0}^{n-1}(n-\max\{p_0^{-1},p_1^{-1},\dots,p_i^{-1}\})$ となる。左に1回rotateする操作は $p^{-1}$ をデクリメントする操作とほぼ同じで、このとき先頭から末尾に来た要素を $v$ とすると、 $n-\max\{p_0^{-1},p_1^{-1},\dots,p_i^{-1}\}$ は $i\lt v$ ならインクリメントされ、 $i\ge v$ なら1になる。

よって全体インクリメント・区間代入・総和取得のクエリが処理できればよい。 $n\le 10^6$ で2secなので遅延セグ木は微妙に怖く、同じ値となる区間を管理する方針で通した。区間代入の右端は必ず全体の右端に一致するので、stackなどを使って線形で解ける。最初に $p_0^{-1}=n-1$ となるようにrotateしておくと初期状態が作りやすい。

Eは簡単。問題文で定義されている再帰関数と全く同じ形式で答えを計算する再帰関数 $\mathrm{ans}(v,l,r)$ が書けるが、よく見ると返す値を $v$ の一次式にすることで引数から $v$ が削除でき、さらに区間の長さにしか興味がないため $(l,r)$ ではなく $r-l+1$ を引数に再帰できる。あとはメモ化すればよい。 $n$ に対し $\lfloor n/2^k\rfloor$ と $\lceil n/2^k\rceil$ での答えしか必要ないという典型。

Fは面倒。まず $p=1,\dots,n$ のケースは $n-2$ が答えである。それ以外なら $i\lt j$ かつ $p_i\gt p_j$ なるペアが存在して、それをswapする操作ではgoodなインデックスが破壊されない。よって最初の状態で $f(p)$ を求めた後、どれだけ増加させられるか求まればよい。

インデックス $x$ がgoodになるようなswapを考える。goodなら $p_x=x$ であるという事実が重要。まず自分の左右に一つずつ条件を満たさない要素があるとき、それらをswapする操作でのみgoodになる。このとき自動的に $p_x=x$ は満たされている。そうでないとき、 $p_x\ne x$ なら、 $p_x^{-1}$ とswapすることでgoodになる可能性がある。

実はそれだけしかない。つまり高々 $n$ 種類のswapが $f(p)$ を増加させる。どのswapで増加するかまで求まるので、それを列挙して、最頻値の出現回数を答えればよい。左右からの累積MIN・MAXの上位2件を求めておく必要があるという点で面倒だった。

全完5位。

www.youtube.com

MHCの賞金受け取りの案内が来ていたので作業した。気づいていなかったがFinal Roundに出場すると賞金が確定するらしい。自分は17位で200ドルだった。賞金受け取りのシステムはYandex Cupより遥かに洗練されていて、今年からHackerOneというバグバウンティプラットフォームを使用するとのこと。アカウントを作ってW-8BENを書いたら終わりだった。PayPal経由で受け取る設定にしておいた。

食事して日記を書き、午前9時就寝。

12/17(日)

午後6時起床。まだ微妙に眠かったがAGCの3時間前に起きるのは理想的なムーブだと思い耐えた。ただ1時間くらいは布団に転がっていたらしい。

外を見ると雪が降っていた。今シーズン初めて見る降雪・積雪。仙台の初雪かと思って調べたら、11/25に降っていたらしい。その日はICPCで横浜にいた。

午後8時までに食事を済ませ、残りの1時間はずっとそわそわしながら過ごしていた。あまり記憶がないがYouTubeを見ていたようだ。午後9時からAGC065に参加。

AtCoder Grand Contest 065 - AtCoder

Aは $A_N-A_1+K\times\#\{A_i\gt A_{i+1}\}$ まではすぐだったのにそこから先になかなか進めなかった。 $A$ に同じ値があるときが面倒。説明のため $c:=\#\{A_i\gt A_{i+1}\}$ とする。

最頻値の出現回数を $l$ 、最頻値を $M_1\lt M_2\lt\dots\lt M_m$ としたとき、 $c=N-l$ とすることが可能で、このとき $(A_1,A_N)=(M_m,M_1)$ になる。ここから改善する場合 $c=N-l-1$ にするしかなく、このとき $(A_1,A_N)=(\min A,M_1),(M_m,\max A)$ とできる。

まあこのくらいかな……と思いつつ順位表を確認したらとんでもないペナ率だったので、ランダムケースを試すことにした。まだACが少ないのでじっくり回して探そうと思っていたが小さめの $N$ と $K$ で一瞬で落ちた。書き換えては落ちるケースが見つかり……を数度試し、ようやく $c=N-l-1$ で $(A_1,A_N)=(M_i,M_{i+1})$ が可能であることに気づいた。

これで出したらちゃんと一発で通ったが30分弱かかっており、いつの間にかAC数も増えに増えて現在60位ちょっと。まあ後からここのペナ差で捲れればOKと思いつつBに進んだ。結論から言えば捲るどころの話ではなかった。

Bはこういうのは後ろから見るんですね～と思いながら考察。 $i=N$ で操作する直前に $N$ がどこにあったかでその前後に分離できることに気づき、勝ったな！と思ったが、そこから一歩も進めないまま1時間ほど苦しんでいた。後ろを無視するためその自由度を先に計算しようとして、できなかった。

まとめて動かすのが無理そうということは分かったので1要素ずつ動かしていく気持ちになって考え直したところ、何とか解けた。値が $i$ 以下の要素を動かしたタイミングを考える。 $1\dots i$ の相対位置は $P$ におけるものと等しい。このとき $i+1$ がどの要素とどの要素の間にあるかという情報も持つと $O(N^2)$ 状態のdpが書ける。ちなみにコンテスト中は微妙に違う定義をしていたが、勘違いによりこの定義での遷移を書いていたらしい。

最初 $Q=(1,\dots,N)$ であったため、次に動かす要素の位置は単調に増加していく必要があるが、それが二つ目の状態によって考慮できている。各状態に対し $O(N)$ 通りの遷移先があって、累積和で高速化すれば全体でも $O(N^2)$ になる。答えは $N+1$ が末尾にある場合の数。通して順位表を確認したら154位でひっくり返ってしまった。

C。 $B=A/2+x/2$ 、 $C=A/2-x/2$ と置いて考えた。このとき $\sum\pm x=0$ となるような符号の選び方が存在しないようにできるか、という問題。条件は $0\le x\le A$ かつ $x$ と $A$ の偶奇が等しいこと。

全部偶数の場合は一つ残して全部 $x=0$ とすればよい。よって問題は奇数の扱い。 $x=1$ とすると作れる数が区間になってしまうが、 $A_N$ を最大値として $A_1\dots A_{N-1}$ の奇数の個数より $A_N$ のほうが大きければ、それでも0を作れないようにできる。最初はこれを提出した。12ケースWA。

このあたりで $x=1$ または $x=A$ とするしかないという気持ちになっていた。大間違いであるがずっと気づかず、例えば奇数の最大値を偶数個取り除いて良いとか、大きな奇数の $\gcd$ を求めてそれが残る奇数の個数を上回っていればよいとか提出していた。どちらも7ケースWA。どうしようもなくなって2回くらい部分和問題を解こうとしてしまった。WAは減らないうえTLEが出た。

残り1分となったところで、最初の提出に「奇数を昇順に並べたとき $1,1,3,3,5,5,\dots$ を超える要素がある」という条件を追加したものを提出した。この条件は残り40分くらいの時点で思いついていた、最初の $\max A$ を使った条件を適当に一般化したもの。反例を作れた気になっていたので提出しなかったのだが、もうどうしようもないからとりあえず投げておこうの精神。

ところがなんと通ってしまった。179分21秒でAC、しかも5ペナということで、3完中2番目に遅い150位。Aをノーペナで通した意味が全くなくなってしまった。パフォーマンス2495、レートは2945→2907(-38)。その後Cまでの解説をじっくり読んだりTLを眺めて解法を振り返った。

Aは $(A_1,A_N)=(\min A,M_1),(M_m,\max A)$ が解になることはないらしい。 $K\times(N-l-1)$ をベースとしてどれだけ答えを大きくできるか考えたとき、 $c=N-l$ では $K+M_1-M_m$ となる。この値は先ほど挙げたペアによる $M_1-\min A$ や $\max A-M_m$ より大きい。それほど自明ではないと思うのだが、解説では特に触れられていなかった。

Bは後ろから見ると簡単というツイートがいくつも流れてきた。そんな馬鹿な……と思いつつ改めて考えてみると前後に分離したうち前パートの長さをキーとすることで解けたが、結局上の解法を逆からやっているに過ぎないようだ。この向きだと解説のdpとも一致する。

Cは $x=A$ だと思い込んでいたのが敗因。例えば $A=(1,1,3,5,5,5,5,5)$ に対して $x=(1,1,1,5,5,5,5,5)$ とすると良い、という理由で奇数の最大値を偶数個取り除く話をしていたのだが、全く同じことが $A=(1,1,3,5,5,5,7,7)$ でもできる。これに気付かなかったのはヤバすぎという気持ち。愚直を書いて条件をエスパーした人もいたらしいし、それくらいは自分もやればよかった。