週記（2021/10/25-2021/10/31）

10/25(月)

先週の週記を投稿してからの話。模擬国内予選の参加記を書き始め、コンテストの半分くらいまで書いたところで切り上げた。その後大学生協で本を注文した。今月は全然本を買っていなかったので、まだ手に入れていない新刊が山ほどあった。また、これまではリアル本屋に行くことを考えて本の予約をほとんどしてこなかったが、最近全然リアル本屋に行かなくなったことを鑑みて、11月発売の本も数冊予約してみた。

せっかく参加記を書くのを途中で切り上げたのに、結局昼前になってしまった。インターンの定例会に寝坊しないことを願って午前10時半、就寝。

CF div.1はそもそも定例会と被っているため不参加。午後3時半すぎに起床し、定例会直前に進捗報告のスライドを捻り出した。先週後半に帰省していた影響もあって、進捗はほぼなかった。

定例会後のKaggleチームミーティングで、参加しているコンテストがそろそろ終了しそうであることを知った。これまで1か月間、びっくりするほど何もしなかった。おそらくモチベーションの問題だろう。せっかくチームを組んでもらったのに申し訳ないという思いが強い。経験者のコンテスト中の動きを知れたのはよかった。かなり序盤に複雑な実験コードが完成しており、そのあたりのフットワークの軽さが印象的だった。

ゲームインさんしょう富山駅前店が今月末で閉店するというツイートが流れてきた。高校時代、学校から駅まで向かう道の途中にあるこのゲーセンにはかなり頻繁に通った。チュウニズムやSDVXの30日連続ログイン称号を手に入れたのもここだった。先週の帰省中に行ったのが最後になる。そうと知らなかったとは言え、閉店直前に行けたのはよかった。

今年の4月上旬に「転生したら皇帝でした」というなろうを読んだ。その読了ツイートに、TOブックスというラノベ出版元のアカウントからいいねが来た。さてはと思ってそのアカウントのツイートを見ると、案の定この作品の書籍化が決定していた。懐かしくなり、改めて即位式のあたりを読み返してみたが、やはり面白い。

https://ncode.syosetu.com/n6066gi/

信じられないくらい眠く、フラフラと布団に吸い寄せられ、そのまま寝てしまった。午後8時だった。

10/26(火)

午前2時起床。この時間から起きてしまうと、今日の夕方から予定されている1on1の前に眠気が限界を迎えてしまう可能性があるので、二度寝したい。そう思いつつ、なんとなくスマホを触ってしまい、結局そのまま朝まで起きていた。

なろうを1作読了。「この世界のヤベー奴らは大体みんな俺の弟子」。黒留ハガネさんの手になる中編で、師匠モノ。僕がこれまで読んできた黒留ハガネさんの作品はどれも非常に面白かったし、また師匠モノという設定も大好物だったので、読み始める前からかなり期待していた。実際面白く、途中で止められなくなったという訳。

https://ncode.syosetu.com/n2245gi/

10/18(月)の日記で、caburiさんのアカウントが乗っ取られたことについて言及していた。今日、本人がツイートされていて知ったが、もう@artclassifiiedという別のユーザーIDに変わって復活しているらしい。微力ながら報告しておいたが、さてどうなるだろうか……。

フォローしていた絵師のアカウントが乗っ取られたことを知った。そのアカウントは現在削除されていて、こちらからフォローを解除したりはできない。絵師のサブアカウントのツイートについていたリプライ曰く、乗っ取った直後は通報されるのを避けてアカウントを削除し、復活期限の30日ギリギリまで待つのではないだろうかとのこと。

週記（2021/10/18-2021/10/24） - kotatsugameの日記

2021/10/31追記：さらに別のユーザーIDに変わっていたので、追跡できるページを貼っておく。

idtwi.com

今日の5限の資料や課題がすでにClassroomに投稿されていたので、終わらせておくことにした。今日は、Pythonとしては関数（特に再帰関数）の紹介、アルゴリズム面ではバブルソートとクイックソートが紹介された。既知の話しか書いていないので斜め読みしたが、それでもかなり駆け足の資料という印象である。課題は100万要素の配列の中央値を求めよというもの。資料に載っていたクイックソートの関数を弄って選択アルゴリズムを書くと40秒近くかかったが、Python標準のソート関数を使えば爆速で求まる。どちらが想定されていたのだろう、来週の資料が楽しみである。

試しに資料のクイックソートをそのまま使ってソートしてみたら、なんと45分もかかってしまった。選択アルゴリズムで落ちるlogも、100万要素ともなるとこんなに違いが出るということか。あるいはデータが偏っていてよくないピボットばかり選んでいた可能性がある。実装が悪く、特に全部同じ値の配列をソートするとO(N^2)になってしまうようで、配列の要素はかなり狭い範囲に分布していたから、途中からそういう状態になっていたとも考えられる。

ちなみに、同じアルゴリズムをC++で実装したところ、クイックソート6秒、選択アルゴリズム2秒だった。

Google Colabでクイックソートを回している間、YouTubeで動画を見ていた。「絶対に笑わない男」という動画シリーズに出会い、2本ほど見た。人が笑いを我慢している様子を見るのは最高に面白い。

絶対に笑わない男 - YouTube

昨日の続きから模擬国内予選の参加記を書き上げ、投稿した。D問題の線形時間の解法がわからず、とりあえず存在だけ言及しておいたが、いつの間にか公式解説がアップロードされていて、それを見て理解した。

kotatsugame.hatenablog.com

FIFから何かの景品が届いた。おそらく2021/10/10に行われたHACK TO THE FUTURE for Youth+のものだろう。

夕方、1on1。眠気は十分耐えられる程度だった。今週も機械学習の実験を繰り返すことになりそう。学習の途中経過を見て実験を打ち切る場合、Ctrl-Cを送信する方法しか知らなかったが、これだと終了後のログ出力なども行われないという欠点がある。プログラム側の機能として、何らかの操作に対応して学習を打ち切る必要があった。これに関して、特定の名前のファイルが存在するかをチェックして停止するか続行するかを分岐するという方法を、メンターさんから教えていただいた。大変興味深い。flockと似たような発想だろうか？

「C言語関数辞典」というページを昔よく参照していて、ブックマークにもいくつか残っていた。今日ふと開いてみると、ドメインの有効期限が切れてしまったのか、謎の広告ページに飛ばされてしまってかなりびっくりした。

急激に眠くなって布団に倒れこんだが、TLを見て模擬国内予選の問題がAOJに追加されたことを知り、最後の力を振り絞って起き、パソコンの前に戻ってきた。手元に残してあったコードを提出してみると、どれもちゃんと通った。DやFは計算量的にちょっと心配していたが、ICPCのマルチテストケースは制約ギリギリを攻めてこないため、結構余裕があった。さらに僕が解いていないAとCも通しておいた。Cは枝刈りdfsが楽という話を知っていたものの、一応bitDPで書いてみた。遷移を書くのは場合分けなどではどうにもならず、結局遷移を生成するための再帰関数を書くことになった。

また布団に倒れこみ、午後9時就寝。

10/27(水)

午前4時半起床。せっかくなのでインターンの実験コードを少し手直しし、また走らせておく。

今日は昼から院試ゼミのメンバーで遊ぶ予定があって、今から二度寝するにしても微妙な時間。ついついスマホに手が伸びて、ハーメルンを読み始めてしまった。面白かったので最新話まで追いつこうと思って頑張って読んでいた結果、昼からの予定の直前になってようやく読了。そこからシャワーを浴びたりの準備をして青葉山に向かう必要があるので、大遅刻である。

読んだのは「天地神明の真祖龍」。モンハン二次創作で、主人公は祖龍ミラルーツに転生する。といっても僕のモンハン経験は3rdのみなので、この作品に登場する古龍たちの中ではアルバトリオンやアマツマガツチ、ジエン・モーランしかビジュアルが想像できない。適宜画像を検索してイメージを補いつつ読んでいた。内容は非常に面白かった。主人公最強なのも良いし、正体を隠して街に潜入する展開も良い。

syosetu.org

そこからシャワーを浴び、学食で昼食を摂ってから青葉山に向かったので、到着したのは午後1時半。昼からの予定は午後0時10分集合だったので、実に80分遅れであった。それから午後6時まで4人でボードゲームをして、山の学食で夕食を摂って帰宅。

今日はディクシット、ドミニオン、スカルという3種類のボードゲームをこの順にプレイした。それぞれちょっとした感想を書いておく。

ディクシットについて。謎の絵が描かれたカードを手札にして、順番にお題を発表し、それに沿う（こじつけられる）ような絵のカードを場に出す。お題の発表者が出したカードを当てればよいが、このとき、当てた人数が正整数の範囲で小さければ小さいほど高く評価される、というゲーム。僕が出したお題はかなりいい感じに票がばらけ、そのうえ1人のみが正解してくれたので、だいぶ上手くいっていた。しかし自分の印象としては、お題として曖昧な語彙を選んだ結果、みんなそれっぽいカードを出せて、たまたま1人だけ僕のカードを指していたというように感じられたので、運が良かっただけに思える。

ドミニオンについて。カードの効果でカードを集め、その場でデッキを作るカードゲーム。最終的には勝利点というジャンルのカードをどれだけ持っているかで勝敗がつくが、勝利点のカードはカードを集めたりデッキを整えたりするのには使えないため、プレイ中は邪魔者になる。僕はデッキを作るのに夢中になっていた結果勝利点をほとんど確保できず、最下位となってしまった。

スカルについて。各プレイヤーは3枚の花カードと1枚のドクロカードを持ち、順番にターンが回っていく。自分のターンでは、自分の前にカードを1枚選んで伏せるか、「チャレンジ」を行うことができる。チャレンジでは適当な正整数を宣言し、自分の前のカードすべてと他プレイヤーのカードのいくつかを、合計枚数が宣言した正整数に一致するように（新しいものから）めくる。めくった中にドクロカードがなければ勝ち、というゲーム。ただしチャレンジ宣言は、別のプレイヤーからより大きな正整数によって上書きされることがある。非常に面白かった。1ゲームがすぐ終わるし、それっぽい駆け引きも行える。僕も駆け引きっぽいことをしていたつもりだったが、実際には指運とクソ度胸、またビギナーズラックによって、1戦目は無傷での勝利に成功した。代わりに2戦目は微妙だった。場にある全てのカードをめくるような宣言をして成功した瞬間や、ブラフで相手に自分のドクロカードをめくらせた瞬間は非常に気持ちよかった。

帰宅してからしばらくYouTubeを見ていたつもりが、いつの間にか布団に移動して、あっという間に寝ていたらしい。おそらく午後8時だった。

10/28(木)

午前5時半起床。

僕が寝ている間にTOKIやCodeChefでコンテストが行われていたらしい。今週平日はこんな感じで、朝に寄った生活リズムで過ごすことになりそう。平日のコンテストには出られない代わり、週末のAGCはいい感じに眠気なく臨めるのではないだろうか。

今日もハーメルンを読んでいたら朝だったのが昼前になってしまった。午前10時、購買が開店したのを見計らって大学に行き、昼食を摂りつつ注文していた本を受け取った。今週月曜日の部分で書いていたものだ。

4年後期の時間割をツイートした。ずいぶん前に確定していたのにツイートするのをすっかり忘れていた。このリプライツリーとも長い付き合いになったものだ。

昼過ぎから1on1。火曜日の時点で生活リズムが朝に寄っていることが分かっていたので、普段通り夕方に行おうとすると寝ている可能性が否めず、この時間に入れてもらった。今日は火曜日から断続的に回していた実験の結果を報告した。Lossの値だけ見ても下がっていることはわかっていたが、改めてビジュアライズしてみると思った以上に学習できているようでびっくり。いくつか改善点を議論して、また実験を回していくことになった。

1on1が終わってから外出し、ゲーセンに向かった。今日は新曲埋めと、11/04に迫った大型アップデート前に消えてしまうもろもろの整理。8月の時点で99枚あった「もう1曲遊べるチケット」だが、無心でプレイを続けた結果ついに使い切れた。つまり、少なくとも99回チュウニズムをプレイしたということで……まあ、ほぼ3か月と考えれば多くもないか。実際は7曲プレイチケットも使ったりしているので、もっと多い。

「もう1曲遊べるチケット」は、なんとなくもったいない気がして上限ギリギリまで貯めているので、非常にまずい。

週記（2021/08/02-2021/08/08） - kotatsugameの日記

今日の進捗としては、これまたアップデートで消えてしまう「Memories of 〇〇」系マップの称号を全部集めたのと、「《運命》 〜 Ray of Hope」で99AJを出したこと。アップデートで削除される曲に関連する称号も、1人で手に入るものをだいたい集めておいた。残りは2つで、どちらもMASTER譜面をSPEED SONICでAJすることが求められる。

SPEED SONICとは、チュウニズムで譜面が流れてくる速度を限界まで速めた状態の名称だ。以下にYouTubeに上がっているプレイ動画を添付するが、譜面がまともに見えないので、運指の暗記が求められる。

www.youtube.com

この状態でAJすることが称号獲得の条件になっているのは「シュガーソングとビターステップ」「Sparkling Daydream」で、前者は普通にプレイしてもAJが安定しないため、とりあえず後者を詰めてみることにした（のが昨日くらいのことだった）。譜面を家で覚えてきたつもりが全然できない。とりあえず通常速度でプレイして、速度を速めてプレイして……を繰り返し、譜面を覚えるのに専念した。15速くらいでプレイしていたら普段の10速で精度が取れなくなったので、10速＋フィールドウォールで譜面の見えなさを再現しようともした。結局先駆者のアドバイスを受けて、17速でプレイを繰り返すことにした。17速だと、流れてくる譜面の判定と認識がだいたい同時になって、見えないことには変わりないが、間違えた場合本来どういう譜面だったかはわかるという寸法らしい。17速でSSSを出し、SPEED SONICで3k弱を出して、今日は終了。

帰り際、今日のマップ進行でかなり増えたゲーム内通貨でショウニスタチュウを購入したところ、所持数が3桁に突入した。チケット系が99枚で制限される中、これは3桁まで行けるらしい。びっくりした。

帰宅してから残りの「Memories of 〇〇」系マップをどう進めるか考えていた。TiamaT:F minorのゲージ10本を達成できる目途が立たない。今日試しにプレイしてみたら、赤以下が150を超えてしまったので、勇気のしるしで完走できるかどうか不安がある。

寝ている間に回す実験コードをセットして、午前2時半就寝。

10/29(金)

午前9時半起床。ずっと布団でウネウネしていたが、正午あたりに身を起こしてゴミを出した。これまでの生活の経験から、ゴミ回収は結構遅めの時間に行われることが分かっており、今から出しても間に合う。

以下のブログ記事を読んだ。内容もそうだが、合間合間に挟まれる画像も含めてオモコロっぽさがある。内容も負けず劣らず良かった。中盤は理解を放棄しそうになったけど、オチがツボに入ってしばらく笑っていた。

umector.hatenablog.jp

大学に行って昼食と散髪を済ませ、サークルの時間になるまで談話室でラノベを読んでいた。

チュウニズムのアップデート情報が連日追加され続けている。今日公開された情報で、判定タイミング音が追加されることがわかった。これを使うと、ATTACK以下の判定時に音を鳴らせるようになる。アップデートで、ATTACK以下の判定時にスキル音が鳴るという理由からAJ狙いの時に愛用していたスキル「パニッシュメント」が消えると知って絶望していたが、この機能で（強制終了は別として）同様のことが行えるため、安心。

談話室がある棟の2階に、仙台に旅行に来ていたなぎの（@makonagix）さんがいるらしかったので、連絡を取ってエンカした。パチスロの設定に関する興味深い話や、計算機数学に絡めた話題があって、非常に良い体験だった。

サークルの時間に少し遅れて教室にたどり着き、バチャに参加。今日のAOJ-ICPC500点枠は「街を駆ける道」という問題で、一度解いたことがあったので問題文は斜め読みしたのだが、見事に誤読してしまった。結ぶべき街はABそれぞれ1組ずつであるということに気づかず、すべての街を連結にしようとしていた。この状態で昔解いたときの考察を復元しようとした結果、「AとBのどちらかは直線で結ばれる」が「AとBのどちらかは最小全域木で結ばれる」になってしまい、当然答えが合わずに苦しんでいた。

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2334

学食でホスフィンと合流し、夕食を摂ってゲーセンへ。金曜夜ということでチュウニズムが8台全部埋まっていたりしたが、少し待って空きができ、マッチングができるようになった。1時間くらいプレイしてフルチェインを2つ出した後は自分のことに集中。昨日から引き続き「Memories of 〇〇」系マップを進めようとしたが、インド人を無の境地AJしても10マス届かなかったり、TiamaT:F minorを勇気のしるし完走したのにギリギリ10マス届かなかったりで、今日はちっとも進められなかった。

残り時間は今日もSPEED SONICでSparkling Daydreamを詰めていた。昨日家で動画を見て運指を組んだり覚えたりしてきたのでなかなか調子がよく、もはや噛み合い待ちであった。が、最後150ノーツくらいまでAJ通過し、緊張で運指が飛んだ回などあって、閉店まで粘ったものの結局この日はAJを出せなかった。せっかく譜面を覚えたので、忘れないうちに、明日は朝からゲーセンに行きたい。運指は↓これ。手の位置を動かさなくてよいのが楽だった。

f:id:kotatsugame:20211102012047p:plain
51-52小節

yukicoderで1問テスターを行った。詳細は当然書けないが、面白い問題だと思った、くらいは言っていいだろう。

「ワールド・ティーチャー」15巻を読了。いよいよクライマックス、なのに前巻の内容を覚えておらず、人名などもあやふやなまま読んでいた。この巻は主人公の活躍がそれほどでもなかったが、次巻すごいことをやってくれるんじゃないかという引きで終わっている。何事もなければ、その次巻が最終巻になるらしい。

布団に入った後もしばらくYouTubeで動画を見ていた。「絶対に笑わない男」という動画シリーズを火曜日に見つけて、それからもしばしば見ている。

ここから20秒くらいが本当に好き。左下のワイプに写っている「鈴木さん」が笑いをこらえきれないシーン。映っている画面自体は右下の人のものであるため、このとき鈴木さんが見て笑ってしまった画面がどのようなものだったかは定かでないが、なんとなく想像はつく。一度持ち直したはずなのに、石を掲げて近づいてくるキャラクターを見てだろうか、とんでもない顔面になるのがたまらない。またこの30秒ほど後でキャラクターがじりじり立ち上がっている様子は、画面にも映るのでより直接的な面白さがある。

午前5時就寝。

10/30(土)

午前10時半起床。食事してすぐゲーセンに向かう。今日は初めからSPEED SONICのAJ詰めを頑張る。

ラストのトリルに癖がついた状態でそこまでAJ通過してしまい、案の定そこでATTACKを出して開いた口が塞がらなかった。

と、そんなことをやっていたら、次のクレで出た。称号「邪王真眼の使い手」獲得である。久しぶりにチュウニズムを頑張り、成果も得られてうれしい。

MASTERのSPEED SONIC AJには、曲を問わない称号「邪気眼」もあって、それも同時に獲得できている。同様のものが1速AJにもあるので、簡単な譜面で出してみたが、以前すでに出して獲得していたことをすっかり忘れていた。

その他は、TiamaT:F minorでコンボエクステンド・フォーチュンを使い10マス達成したり、トライしている最中にスコア6900が出たり、久しぶりにプレイヤーレベルが100に到達したりした。今日は夕方に生協の弁当が届くので、それに間に合うようにゲーセンを離脱。本を買い、ドーナツを食べて帰宅した。

弁当は午後3時半すぎに届いた。11月発売のラノベがいくつも予約できるようになっていたので、生協で予約した後、かなり眠くなってきたので午後5時からお昼寝。

午後8時半起床。ABC225に出る。

UNICORN Programming Contest 2021(AtCoder Beginner Contest 225) - AtCoder

6完79位。Gが五億人に通されていて非常につらい。

AはRakuですべての順列を生成しようとしたが、リストのリストを持った状態で重複を省こうとしたら一致判定がされず、しばらく試行錯誤して文字列に直す方法に至るまでしばらく時間がかかった。重複を省く際は2つのリストを===演算子を使って比較することになるが、このときobjectとしての一致を見るため中身の比較はされないらしい。BはPerlで書いた。CからはC++。Cの問題設定は、S8PCで2回出題されたCalendarという問題に一致している。Dはかなり難しく感じられたが、双方向連結リストっぽく持てば良い。Eは偏角が区間になるので、区間スケジューリングを行う。

A - Calendar

Fはdpで、最近模擬国内予選のFの解説でわざわざ「後ろからdpする」と指定してあったことを思い出し（この問題は実際は前からdpしても通るが）、その方針で考えてみた。各文字列を1度しか使えないので、dpを更新する文字列を使う順番を考える必要がある。これについてはS+T\lt T+Sを比較関数にして降順ソートすればよい。この比較関数が比較関数としてvalidであることは典型。また比較関数の形から、ある解を構成する文字列たちのうち、先頭からこの順番に並んでいないものがあれば、隣接文字列のswapを繰り返すことで辞書順で小さい文字列に置きなおせる。よって、今得られた順番でdpを更新していけば正しい解が得られる。シンプルな問題でありつつも2つの典型が組み合わさっていて面白かった。

Gは解けなかった。盤面を45度回転すると、斜めの条件が縦横の条件に言い換えられる。上下のどちらかと左右のどちらかが塗られているなら、そのマスはコストを支払わずに塗れるので、結局最後に塗られた形は長方形の集合になる。この観察をもとに、すべての長方形領域に対して分割を試し、最適な塗り方を求めるdpを書いた。計算量はO(H^2W^2(H+W))だが定数倍がそこそこ小さいと思ったので、一番内側のループでアクセスするdp配列がメモリ上で連続している領域になるよう添え字を入れ変えてみたり、いくつかpragmaを指定した上で投げたが、全然通らなかった。

コードゴルフ。A問題は1、3、6を埋め込んだコードが最短だった。よくよく観察すると、2進数に直せば1、11、110である。つまり110を3-(文字の種類数)だけ右シフトすれば正しい答えが得られるようだ。このことをRakuで実装したコードが最短になっている。BはRaku。CはOctaveで書いておいた。

2021/11/01追記：A問題は1から(文字の種類数)までの総和でも答えが求まるらしい。これを使ったコードは+1Bになっていた。

途中で切り上げて、午後11時半からCF #752 div.1。

Dashboard - Codeforces Round #752 (Div. 1) - Codeforces

Aは、まず先頭の要素は偶数でない必要があって、2番目の要素は3または2で割り切れない必要があって……と考えていくと、i番目の要素が{\rm LCM}(2,3,\dots,i+1)で割り切れなければよいとわかる。念のためこの値を前計算しておいた。あまりに大きくなっても困るので、109を超えたタイミングで残りの要素はすべてそれで埋めておいた。

Bは場合分け。y=pn+r=p(qx+r)+rとおいてみると、y\lt xのときはr=yを考えてn=x+yとするのが条件を満たす。それ以外は、例えばp=q=1を考えるとr=\frac{y-x}2、n=\frac{x+y}2が条件を満たしそう。しかし、サンプルで正しく構築できたのを見て勢い込んで提出したところ、WA。冷静になるとx\le rになってしまう場合があった。これを修正するため、q\gt 1も許すことにして0\le r=\frac{y-qx}2\lt xとなるようにしてみた。n=qx+r=\frac{qx+y}2であり、0\lt px\le yからn\le y\lt 2nとなり、y\bmod{n}=y-n=\frac{y-qx}2=rが満たされる。

Cは後ろから全探索。商の種類数が少ないので、同じ商に対して場合の数をまとめて持つことによって高速に計算できる。商をまとめるところで毎回vectorをソートしてしまったが、1secを切る十分な速さで通った。実はソートされた商たちで特定の値を割るとこれまた降順ソートされた値になるので、並べ替える必要はなかったらしい。Dは2^k\gt nなら答えはn。残りの場所について、普通にdpを書くと時間がかかってしょうがないが、同じ値の箇所がたくさんあったので、その階差を埋め込めるんじゃないかと思ってやってみた。結果1e6Bくらいのコードが完成したのだが、CFは65536B制限で絶望的。dpの遷移を勘で絞ると計算時間を削減できたため、2回ほど提出したが、どちらもWAだった。

45位で2998→2990(-8)。厳しすぎる。D問題が全然通されなかった結果崖ができており、BのWAがなければもうちょっと順位は上だったが、それでも+2には届かなかったのだろう。Legendはいまだ遠い。

ABCのコードゴルフの続き。D問題はRubyで縮めていたが、AWKにすると40B近く縮んだ。EはCFの間にRubyの分数を使ったコードが提出されており、短すぎてどうしようもない。座標を(+1,+1)することでゼロ除算を回避できるのでは、と思ったが、偏角がずれるらしくそもそも答えが合わなかった。FもRubyで負けてしまったので、Vimで書いて無理やり縮めた。

布団にもぐってYouTubeをしばらく視聴し、午前7時就寝。

10/31(日)

午後0時半起床。

KUPCに出る。コンテストの難易度が高いことが予想されるため、チームを組もうと思っていた。以前からTLを眺めて数人目星を付けており、そのうち直前になってもチームを組まれていないようだったりーふ（@leaf_1415）さんに突撃して無事チームを組んでもらった。

京都大学プログラミングコンテスト 2021 - AtCoder

結果はABCDEFGIKMの3100点で7位。最後にMが通ったのが159分のことで、その前後しばらくは1位だったのに、そこから何も通せず人生が終了した。

Aはりーふさん。僕はBから読んで、焦ってよく確認せず実装した挙句テスト出力を見てミスに気付くことを2回繰り返した後、公式解説の再帰的に構築する方法っぽいものを思いついて通した。りーふさんがCを読み始めていたため、Dに移動。Dは実験コードを書くとすぐgrundy数の規則性が見えて、手でもやってみた感じ正しそうだったので、証明はほとんどせずに通し、すぐE問題に移った。

E問題は、青色の辺(u,v)に割り当てられた重みが、赤色の辺からなる木のu-vパス上のどの辺よりも重ければよい。つまり、重みの小さい辺の番号から大きい辺の番号に辺を張ったDAGのトポロジカルソートを求め、特に順列のinverseが辞書順最小になるように構成できればよさそう。順列のinverseが辞書順最小という条件は、辺番号が小さいものをできるだけ早く使いたい、つまり逆に辺番号が大きいものをできるだけ遅く使えばよいということで、（DAGの辺を逆向きにして）後ろから貪欲すれば求まる。さて、このままではDAGの辺がO(NM)本程度になってしまうが、ここで赤色の辺は必ず入次数がゼロで、逆に青色の辺は出次数がゼロになることに注意すると、後ろから貪欲するとき青色の辺は常に自由に使える状態になっていることがわかる。それらのうち番号が大きなものから使われていくのだから、赤色の辺の番号から出る辺のうち最も小さい番号に向かうものだけ辺を張っておけばよいことになる。赤色の辺からなる木をdfsして、関係する青色の辺の番号たちをsetで管理し、マージテクを使うことで求めることができる。この問題はFAだった。

りーふさんがFに進んでいたため、Gを読んだ。2回開く箱を少なくしたい感じがする。ここで、当たり前のことだが、箱に入っているボールの行き先をもとにグラフを作るとfunctional graphになることに気づいた。これをもとにループごとに分解して考えてみると、自分の箱に入るべきボールが最初入っていた箱、つまりループにおいて自分の1つ隣の箱の開くタイミングと自分が開くタイミングの兼ね合いでコストが決定できることに気づいた。つまり、直前の箱がいつ開かれたかを持ってループ1周ぶんdpすればよい。ループの最初の箱がいつ開かれたかはdpの別の次元で保存しておけば、ループを閉じる部分は最後に処理できる。

Hに進んで30分ほど格闘していたが、全然光明が見えないためIに進んだ。IはHLDすることを考えると、セグメント木で区間加算し、負になった要素があるか確認できれば良い。負の要素を数えて云々、ということを考えていたが、普通にセグメント木全体のminが負であるかを見るだけでよかった。りーふさんのFとほとんど同じ時間に通った。

ここから、順位表を頼りに進むのが難しくなってくる。とりあえず全部目を通して、Kを考えてみることにした。別の要素の決定を阻害しないような遷移をまとめるようなdfsを思いつき、これでヤバいケースが想像できなかったため、りーふさんに確認を取って投げてみると爆速で通ってびっくりした。

次にMに進んだ。Mはsolvedがそこそこいて、後ろから解く異常者たちが通しているのだとばかり思っていたが、よく見るとそうでもなかったのだ。考えてみると、「これまで作れた式の数、式の値の総和、掛け算のみでつながった項の総和、まだ演算子で区切られていない数の総和」を持つとdpが可能であるようだ。遷移は、数字を1文字追加するか、演算子と数字を組みにして2文字追加するか。遷移を行列で表して行列累乗するとすぐサンプルが合って、そのまま通ってくれた。

残り時間、僕はL問題を、りーふさんはJ問題を考えていたが、双方通せず終了した。りーふさんが担当してくれた問題たちは順位表を見ても結構通せていないチームがあって、実際僕はまだC問題すら解けていないため、そこを通してもらえて非常に助かった。解法の共有や相談は行わなかったが、こうやって問題を分担できただけでもチーム戦を組んだ甲斐があったと感じられた。

その後、KUPCのコードゴルフをいくつか行った。A問題はRakuが強い。B問題はOctaveで書いた。文字列の添え字として行列を使うと、結果も2次元の文字列になってくれるのが便利。Cを飛ばして、DはAWKが短くなった。残りは手付かず。

ふぁぼん氏が言及していたのを見て、カクヨムで「おいしいピザトーストの作り方」という日常の謎短編を読んだ。氏も触れているが、キッチンで不自然な状態を目にし、どのようにしてその状態が作り出されたかを推理するというのは、米澤穂信さんの小市民シリーズに収録された「おいしいココアの作り方」という短編とまったく同じである。僕はその短編が結構好きで、カクヨムのほうも楽しく読めた。

おいしいピザトーストの作り方（十一） - カクヨム

午後9時からAGC055に出た。

AtCoder Grand Contest 055 - AtCoder

A問題はもはや恒例の天才パズル。天才のフリをし損ねた瞬間ゲームオーバーだ。最初に、ABCそれぞれの文字を先頭から順に組にしていき、6通りの順番で場合分けして別の文字列に組み分けることを考えた。3!=6という意味の制約なんだなあと興奮。あまりの興奮に、よく確かめずサンプル2が合っていないことに気づかず提出してしまった。WAが出て心臓が止まりそうになった。しかし3!=6という意味は間違っていないはずだ。そのあと20分くらい考えて、N文字ずつに分割するとうまくいきそうだということを以下のような計算をもとに確かめ、提出してACを得た。証明は途中だったが、おそらくもうちょっと計算してAとBを同時に使いきれることを確認した後、ホールの結婚定理を使えば言えるのだろう。

B問題は、まず文字列の隣接項の差分を取っていろいろ考えてみた。a,1,1,bという列をa+1,1,1,b-1に置き換えられるらしい。これを使って先頭からマッチさせていくことを考えると、1が2つ連続している場所を探して、それを動かして特定の位置の値を弄ることはできる。では、所望の値をセットし終わった後は？動かしてきた1,1という部分列は再利用できるのか？……このことは隣接項の差分を取った状態では何とも言えなかったため、元の文字列に戻って考えてみた。1,1を動かすことは、ABCやBCAやCABを動かすことと同じである。XABCから適当に置きなおすことで(ABC or BCA or CAB)X、その後ABCXに変化させることができるので、この操作を考えていたのだろう。こうやって文字列で見てみれば、3文字が一塊になって文字列中を自由に動いているとも考えられる。それで特定の位置にたどり着き、さらに何度か置き換えて所望の文字をセットした後、残った2文字はまた自由に動けるだろうか、ということが知りたい。これは明らかに不可能である。例えばAABCがあって、Aは所望の文字ではないから代わりにBCAAと置きなおしたとすれば、一塊になっていた3文字には異なる文字との入れ替えが発生し、残りCAAのように必ず2文字が重複してしまって動かせない。つまり、このような3文字は1か所の文字を交換するのにしか使えず、使った後はその場に特定の順序でとどまることが分かった。ここまでわかれば、あとは操作をdequeでシミュレートできて、AC。

C問題は非常に難しかった。数列の値は1種類か2種類の場合しか考えなくてよく、このうち1種類の場合は別に計算できる。つまり、ある3\le k\le Mであって数列がk-1とkのみで構成される場合を考えればよい。k-1という要素が必ずLISに含まれる一方、kという要素は基本LISに含まれないが、2つ連続していれば含めることもできる。k-1の個数をa、2つ連続しているkの個数をbと置くと、a\le k\le a+bなるkを当てはめることができそう。とりあえずO(N^3)のdpを書き、\max(0,\min(a+b,M)-\max(a,3)+1)を掛けて足し合わせたら答えが合った。さらに、M\gt 2かつa\le Mの場合だけ計算することにすれば、0とmaxを取る必要もなくなった。2\lt M\le N-1よりa+b\ge 2となるらしい。これで寄与が分解できたので、a+bをキーに持つdpとaをキーに持つdpをそれぞれ書けばO(N^2)で求まりそうだったものの、実装してみたところ答えが合わなかった。どうやらa+bをキーに持つほうでa\gt Mの場合を含めてしまっているのが問題らしい。ここで、a\gt Mの場合\min(a+b,M)=Mであることに気づいた。よって、最後に各a\gt Mについてa+bの値を任意とした場合の数をcombinationで表し、Mを掛けて答えから引いてみたところ、見事にサンプルが合った。祈るように提出し、AC。1時間以上粘って通せたので非常に気分がよかった。

残り時間はふわふわした気持ちでDを読んでいたが、そもそも判定問題すらまともに解けなかった。結果は37位、パフォーマンス3080でレートは2821→2850(+29)。当然最高値である。

コードゴルフ。Aは適当にRubyで書いてある。Bは解説の方針が天才すぎた。差分を取るのは典型操作だが、このようにインデックスを引いてみるのも見覚えがあって、今回はそちらが正解だったらしい。その方針で、これまたRubyで書いてある。

夜中はずっと日記を書いていた。普段寝る前に日記を書いているが、今週は倒れこむように眠ることが多く、なんと一週間まるまる溜めてしまったようだ。もう全然書き終わらないので、途中であきらめて寝た。午前9時半だった。金土日の分は11/01(月)に書いている。