週記（2023/01/30-2023/02/05）

01/30(月)

午後2時に一瞬起きて修論発表会のZoomに接続した。もともと可能なら参加するようにと指導教員の先生に言われていて、特にこの時間帯は基礎論の発表だったから無理して起きてみた。しかしやはり無理だったようで、接続はそのまま放置して布団に戻り二度寝した。

次に午後4時半ちょっと前に起床しインターン先定例会に参加した。先週は集中講義を理由に何も稼働していないが、そもそも先週の進捗報告にも出席していないため、先々週少しばかりコードを修正した分の報告が残っていたのでそれを発表。

勉強会は二値分類の精度指標の話だった。F値という指標は二つの指標の調和平均で定められておりなんだか複雑そうな形をしているなと思ったら、式変形でそこそこ綺麗な分数になってびっくりした。

質疑応答が活発で終了時刻は午後7時半になった。おそらくこれで1月中の稼働は最後だろう。今月は年始や集中講義で2週間くらい何もしていなかったため、インターンを初めてから断トツで稼働時間の短い月となった。

夜中まで週記を書いていた。ABCの部分を書いているときに最短コードをチェックしていると、A問題が縮んでいるのに気付いた。改行を含めるとForが4文字、Againstが8文字だから、文字数の総和と6Nを比較することで判定できるらしい。考えもしなかった。

atcoder.jp

午後11時くらいになってようやく投稿。今週も当然のように校閲が終わっていない。

TUPC2022の情報が公開されていた。今年はAtCoderで開催されるし、大学の教室を借りてオンサイト会場も用意される。どちらも交渉ややり取りはサークルの面々が頑張ってくれた。自分は何もやっていない。

実は明日も修論発表会があって、その影響でセミナーが水曜日にずれているから準備も明日でよい。疲れ果てて布団に突っ伏し、日付が変わったくらいに寝落ちした。

01/31(火)

午前4時から午前11時くらいまで起きてなろうを読んでいた。また午後3時くらいに頭の痒みで起きて、急いでシャワーを浴びた記憶がある。

午後8時起床。1時間ちょっとハーメルンを読んで布団から脱出した。ABC283の賞品でアマギフ2万円分が届いていた。

セミナー準備になかなか気持ちが向かず、かなり長い間YouTube・ニコニコ動画・カクヨムに時間を使っていたらしい。明日は平面グラフに入る予定で、定義とその直後にある補題をいくつかやるつもり。それらの補題は定義したすぐ後に書いてあるくらいだし簡単なものだろうと舐めてかかっていたのだ。

午前2時から開始したが、思ったより証明が長大でびっくり。内容も平面幾何の話が結構あって、直観に頼った議論になっていないか慎重に確認する必要があり時間がかかる。何とか完成したのが午前5時半だった。

シャワーを浴びて午前6時過ぎ就寝。

02/01(水)

午前9時半起床。セミナーのため大学に向かった。購買でパンを買ったりしていて10分ちょっと遅刻した。購買の開店とセミナー開始が同時なのは不便なので、今度スケジュールを改める機会があったら主張したい。

午前中は明後日に博論発表会を控える博士課程の方の発表練習だった。まず聞いて、それから質問を飛ばす役割。

これまで1年くらい一緒にセミナーをやってきて発表も何度も聞いているので、何をやっているかはある程度理解できる。一方そのために大した質問ができない。なぜなら今聞いて抱くような疑問はこれまでのセミナーで解決済みだからである。「この研究は何が嬉しいのか」「あなたの仕事はどう新しいのか」とかTwitterでよく見るようなことを知った顔で言うなんてもっとできるわけもなく、捻り出した質問を一つ二つ聞くだけで精一杯だった。

昼食は学食で、先生と同級生との3人で摂った。行き帰りの間に先週集中講義で休んだTAの話を聞いたが、今週は期末テストで忙しい人が多いらしく休講になったそうだ。来週以降は単純に授業日ではないので先週が最終回だったことになる。そこだけピンポイントで休んでしまったというのは少し残念。

同級生が3限と5限に講義を取っているらしいので、次のセミナーは4限の時間となった。これまでいた教室も別の講義で使われるようなので待ち時間は院生室でずっとなろうを読んでいた。暖房が入っていなかったためかなり寒かった。

4限になり発表。90分しか時間がないのを忘れ、終了時刻を決めない普段のような感覚で喋っていたら、用意した分が全然終わらなかった。平面グラフの定義のあたりを過剰にネットリ説明してしまったようだ。昨日頑張って準備した補題はその長大な証明を説明する時間などあるはずがなく、主張だけ確認して終了。

帰宅途中に川内キャンパスの生協に寄って予約していたラノベを受け取ったが、その10分程度の間に雨が降り出していた。空模様で遠からず降ることはわかっていたとは言え、こうも絶妙なタイミングだとちょっと悲しい。

午後5時過ぎに帰宅。ゲーセンに行きたいが疲れ果てて動けない。1月の読書記録を集計するなど今日のうちにやっておきたい作業を素早く終わらせて布団に倒れこんだ。

午後6時半から午後11時まで睡眠。起きてからCF #848 div.2に出た。

Dashboard - Codeforces Round #848 (Div. 2) - Codeforces

Aは操作をちょうど1回行うという条件を忘れて実装してしまい少し手間取った。しかも見切り発車で書き始めたら\pm 1の個数をそれぞれ数えるという面倒な実装方針を取ってしまった。

Bはちょっと難しかった。操作する必要がある場合、1\le i\lt mを選んでa_iとa_{i+1}の位置を近づけるか遠ざけるかすることになる。近づけるほうはちょうどa_{i+1}がa_iの直前に来るようにすればよく、必ず可能。一方遠ざけるほうは最大まで離してもどうにもならないことがあるのでチェックが必要。条件式に括弧を入れ忘れて1WAしたが、別のところを疑っていてバグの発見に時間がかかった。

Cはrを固定し、各lに対しa[l,r]=b[l,r]とするために必要なQを考えると、l=r\dots 1の順で単調に大きくなっていく高々11通りしかない。Qを全探索して(l,r)の組を数えておき、部分集合に渡る和を求めることで答えになる。ゼータ変換したが愚直でもよい制約。各rに対し最大のQに対するlを計算し忘れていて1WAした。

Dは文字が異なる位置の数を状態とした期待値dp。ループがあるが、dp_{i+1}をdp_iの1次式で表すことでdp_nから順に計算できて、その後dp_0=0から順に具体的な値を確定させられる。

Eは部分木全体から作った基底を管理して全方位木dp。根を移動するとき元々の根にあった値を書き換えるのと、根から戻ってきたときに元の値を復元することに気を付ける。根自体の値がどうなるかよくわからなかったので、そういうケースはすべてのaを使った基底を求めて先に計算しておいた。

基底の実装はいわゆるnoshi基底を使った。これは基底の順番にも意味があるのだが、値の最大化を貪欲で行うために降順ソートする必要があると思って基底を求めるタイミングですでに降順ソートしてしまい壊れていた。実はもともとの順番で貪欲に取っても最大化できるようだ。

Fは木dp。部分木に対してそこにある値をすべてgの倍数にするために必要な最小の操作回数を持つ。gとしてはa_1の約数しか見なくてよいことを使うと十分高速。最初それに気づかず実装していて、pretestで1934msだったので出し直した。最初のコードはシステスで落ちるようなので助かった。

全完16位。序盤手間取ったりWAを出したりしていてちょっと残念。

TUPCのテスター作業を延々続け、午後1時前に就寝。

02/02(木)

午後7時起床。TwitterのAPIが02/09から有料化されるということが話題になっていた。自分もTwitter botのatgolferを管理しているので無関心ではいられない。1年で1万ちょっとくらいなら払ってもいいかな～と思っていたら後から月100ドルという話を聞いてひっくり返った。

念のため元ツイートを確認。一瞬月100ドル「以下」のように読んでしまうが、そういえばチルダは英語だと「およそ」とか「約」を表現するのだった。やはり月100ドルらしい。

ゲーセンに行くため外出した。チュウニズムデュエルがまだ結構残っており、具体的には02/08までに35クレ程度プレイする必要がある。1日で終わらせるには厳しいので早めに行動する必要がある。ミスタードーナツで少し腹ごしらえして、午後8時過ぎから閉店までプレイした。

今日の成果はそこそこ。前回ゲーセンに来た時埋め切れなかった14+でSSSを出した後、最近触っていなかった14+をいくつか詰めてSSS+を四つ増やした。その後少し理論値狙い。

なんと13+のきゅうくらりんの理論値を出せた。結構好きな曲なので嬉しい。今日は中盤の微ズレが上手かった。3個並んだノーツのうち右端がズレているなら左手1個右手2個に分け、真ん中がズレているなら左手2個右手1個に分け、手を傾けてスライダーにタッチするタイミングをずらすように意識したら安定した。

ラーメンを食べて帰宅。シャワーを浴び、しばらくTUPCのテスター作業をしてから、午前3時から3時間ほどインターンの進捗を産んでいた。ツールのドキュメントやブログとにらめっこして自動化したいことを実装。幸い今の目的とかなり近い記事を見つけたので思いがけず捗り、ツールの下調べどころかもう実際に使える状態になったのではないかと認識している。

しばらく布団でなろうを読んで午前7時半就寝。

02/03(金)

午前10時ちょっと前に起床し、博論発表会のZoomに接続した。一昨日発表練習に参加した方の発表が朝一番からあった。練習のときスライド中のグラフに関して行った提案が反映されていて嬉しい。

内容自体は特に変わっていないようなので、ゴミ出しの準備をしながら聞いていた。無事終了したのでZoomから退室。布団に戻ってまた寝た。

今度は午後2時ちょっと前に起床し、1on1に参加した。昨日産んだ進捗を報告。自分としてはもう十分自動化できていたつもりだったが、もうちょっと広い範囲をもっと簡単に自動化できるはずらしい。しかし痒いところに手が届かないAPIしか存在しない。いろいろ調べた結果あまり効率的でない方法なら実現可能ということが分かって、それの実装は来週までの自分のタスクとなった。午後4時終了。

午後10時まで先週の集中講義「応用数理総論」の期末レポートを作成していた。5日間あった講義で毎日2題ずつ問題が出され、そのうち片方ずつに解答するのが課題。先週のうちに昨年の資料を参照したり、先生に質問したり、友達と話したりネットで調べたりして最終日以外のものは解けていた。しかしそれらを文章に起こすのは結構時間がかかった。

最終日は順序数に関するもの2題で、まだ考えていなかった。昨年はなかった内容だから今年の資料だけで頑張るしかない。最後だから自力で解こうと思って格闘した。実は後からネットで調べてみたところ必要な定義がメジャーなものと微妙に異なっているらしく、安易に検索に逃げてもあまり意味はなかったようだ。

かなりそれっぽい式変形を行えたがその後のステップがわからない。もう元気がないので適当にまとめてレポートを完成させてしまった。無事提出。これにて今期の講義はすべて終了したことになる。卒業要件に含められない講義二つもなんだかんだ真面目に最後まで取り組めたのでかなり満足している。

Twitterアカウントの凍結が盛んなので、自分も何か対策をと考え、6年近く前に作ったマストドンのアカウントに久しぶりにログインした。有名だったインスタンス5個くらいにkotatsugameというIDでアカウントを持っているが、今は管理が面倒なだけで無駄だったなと思っている。そのインスタンスの一つであったfriends.nicoが結構前に消えていてびっくり。

しばらくフォロバ作業に勤しんでいたが、動作がかなりモッタリしていて嫌になった。Twitterのような快適さを求めるわけにもいかないので、本当に自分のアカウントが凍結されてしまうまでマストドンに移行することはできないのだろうなと考えた。

食事して午後11時半からCF #849 div.4。

Dashboard - Codeforces Round #849 (Div. 4) - Codeforces

ABはよい。Cは両端を見て文字が異なる限り縮めていき、残った長さが答え。Dは全通り計算できる。文字の出現をbitで管理したが、一か所__builtin_popcountを忘れて答えがとんでもない値になっていた。気づくのに少し時間がかかった。

Eは隣接という条件を忘れて2個ずつ符号を反転できる。負の数が偶数個あれば全部反転するべきで、奇数個なら負の数を1個残すか、正の数を巻き込んで1個負の数にする。書いてから、これは結局絶対値が最も小さい値を負にしているのだということに気づいた。

Fは1回操作する場合999999999\rightarrow 81、2回操作する場合79\rightarrow 16が操作後の値が最大になるケースなので、高々3回操作すればもう値が変化しなくなる。よって、まだ変化する余地のある値のインデックスをsetで管理しておくと、そこに入っているインデックスに対しては愚直に操作しても間に合う。

G1はスタートとテレポート先が常に座標0なので、そこからテレポーターまで移動して座標0に戻ってくるサイクルに分解して考えることができる。各テレポーターについて1サイクルにかかるコストを計算し、安いほうから貪欲に取ればよい。

G2はテレポート先が2か所に増えている。基本的にはどちらか近いほうからテレポーターまで移動してどちらかに飛ぶというサイクルに分解してコストの安いほうから取れるが、最初の1回だけは座標0から移動する必要がある。貪欲に取ったときにそのような移動が含まれるなら答えはそれで確定する。そうでない場合の処理に苦労した。

最初に座標0からどのテレポーターに移動するかを全探索し、この時余分に増えたコストも含めてc以下に抑えるため貪欲に取った解をどこまで削除するか考える。貪欲解に含まれないテレポーターならどうとでもなる。含まれる場合は二分探索するが、このとき座標0から移動する予定のテレポーターを除いて考える必要がある。実装に手間取ってG1まで解くのにかかったのと同じ時間をG2にかけてしまった。

40分弱で全完、最終順位は12位。動画を撮っていたので編集・エンコード・非公開状態でのアップロードまで済ませ、コンテスト終了を待って公開した。

www.youtube.com

朝まで日記を書きながら社築さんのサーモンラン配信を見ていた。普段見ている「総理大臣によるサーモンラン」シリーズとはかなり立ち回りが違うように思えて目新しく、面白い。総理大臣はコンテナからあまり離れないイメージがあるが、社築さんはステージをかなり広範囲に渡って動き回る。うっかりカンスト達成まで見届けて午前7時就寝。

www.youtube.com

02/04(土)

午後1時半起床。食事して午後2時からUniversal Cupの2回目に参加した。今日のセットは中国のICPC由来でHong Kong Regional。

2022-2023 ICPC Asia East - Hong Kong Regional Contest - Dashboard - Contest - QOJ.ac

チームでKAHBELDFCを解いて9完、41位だった。自分はABDCを解いた。

コンテスト開始早々に通されたのがABHKLで、Kをぷらさんが、Hをかっつさんが通した。Hは難読だった。全員で問題文を読んだが結局細部はよくわからなかったので、サンプルからエスパーしてそれっぽい解法が提出された。

Bは考察すると黒マスに囲まれた白マスの連結成分数を求めればよいことになって、実はこれは右と下のマスが黒で塗られた白マスを数えるのと等しい。なぜならマスの塗り方から、そのように塗られている場合それより右あるいは下に同じ連結成分のマスが存在できないから。何とか思いつけてよかった。

Lはそう簡単に解ける問題に見えない。EFが通されてきたのでそれにも目を向けた。Eは区間\pm 1加算しながら区間の0の個数が分かれば解けることになって、そこで詰まっていたらぷらさんがセグ木に最小値とその個数を持つ方法を出してくれたのでそのまま実装してもらった。言われてみれば見覚えがある。

かっつさんがFと格闘しているのを横目にいよいよLを詰める。それっぽい貪欲がいろいろ思い浮かんで、その中から大きな値から削除することが正当であると示せた。残りの考察や実装はぷらさんにお願いした。1WAしたのでコードを読んだり証明を見直ししたりするも間違いが見当たらない。問題文に立ち返ったところでbがaの部分列であることが必要だと気付いた。自明な条件過ぎていつの間にか忘れ去ってしまっていた。

かっつさんのFの考察を見に行った。隣り合う2数の桁数の差は1以下であると書かれていて、すぐにはわからなかったが精密に不等式を評価すると確かにそう。直感的にはどの位置にある2数も桁数の差が1以下になりそうだが示せない。しかし実は隣り合う2数に関する条件だけで調べるべき状態数が十分少なくなっているのではないかと思った。残りの詰めや実装はそのままかっつさんに押し付けた。

CとDが解かれていて、どちらかというとDのほうがとっつきやすそうなので考え始めた。DAGの辺u\rightarrow vについて0\lt v-u\le 1000という制約が明らかに怪しい。ということでまず頂点をサイズ1000のブロックに分けてみたものの、先に進めなかったので別の方針を考えた。

各頂点に対し、そこにたどり着くために使った黒の辺の数と白の辺の数をペアにして持ちたい。このペアは大量に存在しうるが、それらを平面上の格子点だと思うと答えに関わるのは左下凸包に乗る点のみ。そして座標の範囲[0,m]\times[0,m]の中で凸包に乗る点の数はO(m^{2/3})なので、実は持っておくペアはそれなりに少ないことが分かった。あとは実装すればよい。かっつさんのFの実装に割り込む形で書き始めた。

凸包を取るのに失敗して1TLE、また答えを求める二分探索が失敗していたようで2WA。持っているペアを全部試して答えを求めても十分間に合うため、最終的にはそれで通した。TLEは手元で最大ケースを試せば分かったはずだから三つとも不必要なペナ。下手くそだった。

その後Fが無事通った。かっつさんに押し付けてからノータッチだったので何もわからないが、自分では実装したくないような面倒さだったから本当にありがたい。

その間にCの考察を進めていた。nmが奇数なら当然不可能。また行・列のパターン数が足りない場合も不可能。それ以外の場合を考える。mが偶数として、マス目をn\times m/2に分割し片方をもう片方の反転で埋めれば白と黒の数に関する条件を満たせるので良いのではないかと考えた。ただしこれは行のパターンを2^mから2^{m/2}にしているため、mが小さくてnが大きいケースでは使えない。

ちゃんと評価すると、そのようなケースはm\le 18にしかないと分かった。このケースは行のパターン2^m通りを配列で持てるため重複チェックが楽になる。またm\lt nもわかるので、最初にm\times(m+1)マスに白黒同じ数ずつ埋めて列の重複が起きないようにした後、残りの行をxと\lnot xをペアにして埋めていくことにした。偶奇が壊れる部分などは適切に頑張る。まずこれを書き上げて、チェッカーも書いて正しいことを確かめた。

残りは結構簡単。最初に2^k\ge m/2を満たす最小のkを取り、上k行を使って列の重複をなくしておく。縦に2進数として見て1\dots 2^kとなるように埋めればよい。残りの行は横に2進数として見る。まず0を置くことで全体を反転しても列の重複が起きないようにする。ここで先ほどの埋め方だと上k行には0がないのも重要。その後0からどんどん値をインクリメントしつつ、上k行とのみ重複チェックして置けるものをどんどん置いていった。

チェッカーを動かして確かめる。すべてのケースは試せないが、小さいケースと大きいケースでOKだったので自信はかなりあった。出したら一発で通った。

残り1時間はGを解こうとしていた。最初は単なる扇形二つの和だと思ったがサンプルが全然合わない。必死に図を描いて考え、サンプルを何とか合わせたと思ったのにWA。結局解けなかった。後から確認したらサンプルすら合っていなかったようだ。小数点以下が違うのを見落としていた。

コンテスト後は先週と同様感想戦をしていた。今日は結構いろいろな問題の考察に顔を出していたので、上に書いた以上のことはほぼない。Kだけ何も知らなかった。いくつか解の候補がある問題らしく、いくつかペナを出しているチームが多い中、素早く列挙してちゃんと一発で通しているのはかなり偉いと思った。

雑談に移行してこの先のコンテスト予定を確認しているとき、次の水曜日にCodeChef Cook-Offがあるのを見つけた。この日はホスフィンと家飲みをする予定が入っている。ちゃんとCLISTも確認していたはずだが、こんな直前になって生えてくるとは。連絡して家飲みをその次の日にずらしてもらった。スケジュールを頑張ってすり合わせて決めた予定だったので、かなり申し訳ない。

午後8時解散。シャワーを浴びて食事した後ABCの録画のセッティングをしていた。せっかくWebカメラがあるので手元を映してみたい。これまでは一枚画面をShadowPlayで撮ることしかしていなかったが、実は配信のためにインストールしたOBSでも録画はできて、これだとカメラ映像も取り込めて画面に自在に配置できる。セッティングとはそのための設定と、Webカメラを手元が映るように置くことだった。

午後9時からABC288。

Toyota Programming Contest 2023 Spring Qual A（AtCoder Beginner Contest 288） - AtCoder

Aは見た瞬間AWK。それ以外はC++で書いた。Bはソートしてから上位K人を答えると思ったら上位K人をソートして答える問題だった。CはUFに辺を追加していって、連結成分が減らなかった本数を出力する。

Dは難しかった。K=2なら交代和が0になることが必要十分条件なのでKが一般の場合も同様に解けると思ったが、それほどうまくいかない。手で実験して、列の長さが2K以上のとき左からK項を0にしようとしたらその次のK項にどんな変化が生じるかを求めた。具体的にはK=4のとき(a,b,c,d,e,f,g,h)\rightarrow(0,0,0,0,e-d+a,f-d+b,g-d+c,h-d+d)となる。正確にはhは操作されないが、巻き込んで考えると規則的。

これをどんどん適用することで、どんな長さの列も長さ2K未満の列に帰着することができる。あとは貪欲に操作すればよい。添え字\bmod Kごとの累積和が必要になって頭を壊してしまったが、何とかサンプルを合わせて提出し、通した。

Eはdp。商品番号iを昇順に見て、これまでいくつの商品を購入すると決めたかjを状態に持ってdpする。商品iを購入するタイミングを適当にずらすことで、定価から値上げされる金額としてC_{j+1}\dots C_iのみ、またその範囲のどれでも選ぶことができる。したがってCの区間MINによって価格が決められる。

Fはちょっと難しかった。1文字ずつ見て、その直前の文字との間に区切りを入れるか入れないかでdpを行いたい。和だったら楽、というか何度か見たことのある問題だが積なので複雑。直近で区切りを入れた位置より左に対する値Pと現時点の答えSをペアに持ち、数字vを追加するとき、区切りを入れるなら(P,S)\leftarrow(S,Sv)、入れないなら(P,S)\leftarrow(P,10S+Pv)となって、線形性が成り立つからP、Sそれぞれありうる状態すべてについての和だけを管理できる。

この状態の持ち方は適当に思いついたもので、試して実際に答えが出たときはびっくりした。線形性なども後から確認したこと。素早く解けてよかった。

Gは解けなかった。3進表記で0と2しか現れないような位置に対しては、それぞれ包除原理することで答えが求まった。しかし1が現れる位置は何一つわからない。正確にはこれも包除原理すればできるはずだが計算量が大きすぎる。

6完88位。ちょっとひどい順位だがとりあえずオンサイトには出られるようだ。Dは差分を取る典型が効くらしいがK=2のときの交代和に引きずられてしまった。

Gを3桁人が解いていてひっくり返った。競プロフレンズさんがB\rightarrow Aを考えると解けたと仰っていて確かにという気持ちになった。しかしその時点で解説を読んでいたので、本当にそのアイディアだけでコンテスト中に解けたかはわからない。

コードゴルフ。AはAWKでよい。BはVimだった。書こうとすらしていない。CはPerlで、UFを使って森の辺の数を数える問題はいくつもあるのでそこからコードを引っ張ってきたが、この問題用に書き直す部分で負け。FはPerlがかなり短くなった。他は手付かず。

ABCの録画を編集して投稿した。せっかく手元を撮ったのだから出したいという欲求が、Gを解けなくて恥ずかしいという気持ちを上回った。

www.youtube.com

しばらくPCの前でなろうを読んでいて、寒くなってきたので布団に潜り込んだらすぐ寝落ちしてしまった。午前4時くらいだった。

02/05(日)

午前9時半から午後3時まで起きていて、ずっとなろうを読んでいた。「異世界転移で女神様から祝福を！　～いえ、手持ちの異能があるので結構です～」を読了。

https://ncode.syosetu.com/n2031cu/

面白かった。多人数で異世界転移したのに主人公（ともう一人）がすぐ排除されてしまう、というところまではテンプレだと思う。あまり読むジャンルではないのでその先の展開がどれだけ特徴的かはわからないが、排除された主人公たちが実はめちゃくちゃチート持ちで爽快だった。

最初は単に異能をいろいろ持っていて強いという感じだったが、後から元の世界でも非常に特異的な人間だったと明らかになる。最初からそういう設定があるとさすがに盛りすぎと思ってしまったところ、途中から徐々に明かされていくので無理なく受け入れることができた。主人公の豪運っぷりが見ていて楽しい。

また寝て、次に午後7時起床。1時間ほどなろうを読んで布団から脱出した。

食事してCFに向けた準備をした。今日も手元を含めて録画するつもり。昨日はメモ用紙が体の影になって見えにくかったので、前からデスクライトで照らしておくことにした。顔をモニターに向けるとちょっと眩しいが耐えられないことはない。あとはカメラの位置も調整して、メモ用紙がより大きく映るようにした。OBSでカメラ映像の画面全体に対する比率も大きくした。

午後9時からCF #850 div.1。久しぶりのcombinedでないRatedだ。

Dashboard - Codeforces Round #850 (Div. 1, based on VK Cup 2022 - Final Round) - Codeforces

Aはなぜか一つ目の呪文も全モンスターに1ダメージ与えると思い込んでしまい少し手間取った。適当に1から連続する値を作ると二つ目の呪文で全モンスターを倒せるので、そういう連番を作るために与えるダメージを最小化する。ソートして貪欲でよい。サンプル2に怪しげな数字が並んでいて面白かった。

Bはw、i、nに対応する頂点を作り、各sを見ていらない文字から必要な文字に向かう有向辺を張って考えた。文字のswap1回によってある辺とその逆辺を消せる。また2回swapすれば長さ3のサイクルを消せる。直感的には前者を貪欲に行った後後者で調整すればよい。

実際、前者を行えるだけ行った後の辺は、長さ3のサイクルにちゃんと分解できる。有向辺としてsに必要な文字が存在するという意味の自己ループも考えると、三つの頂点はどれも入次数、出次数共にmとなるから、逆辺を持たない辺しかなければそれぞれ対応する長さ3のサイクルが存在する。

復元が面倒そうだったが、頂点の組に対しその間にある辺に対応する人の番号を持つと結構簡単に書けた。一発AC。

CはAの強化版。値を追加しながらAを解く必要がある。真面目に追加していくとしても遅延セグ木があれば解けないこともなさそうだが、細かいところで実現不可能な操作が要求されるように見える。考え方を変えて値を削除しながら解こうとしたらかなり簡単に解けた。

まずAの解法を整理する。aを適当に並べ、先頭からできるだけ遠くまでi\le a_iが成り立つようにする。m\le a_mまで成り立つとすれば、このaたちに対する答えは\sum_{i=1}^m(a_i-i)となる。1\dots mというのが上で述べていた連番である。

a_1\dots a_mに使った値から1個削除すると、代わりに削除した値以上の使っていない値を埋めて連番の長さを保つか、諦めて連番を一つ縮めることになる。前者は使っていない値をmultisetに入れておくと取得できる。後者については単に削除した要素より後ろを一つずつ前にずらせば条件を満たせる。mと\sum_{i=1}^m a_iを管理しておけば答えが求まる。

Dは面白かった。人uに注目しているとき、残りの2^n-1人を2^0,2^1,\dots,2^{n-1}人に分けることができる。これはuからトーナメントを表す完全二分木で上に登っていくとき、uを含まないほうの部分木に含まれる葉の数、つまり人数を意味している。作ったn個のグループそれぞれで番号の最小値を求めると、それがuを先頭にした順番で単調減少であることと、uがそのトーナメントでWooden Spoonとなることが同値。

グループ内の並び替えや二分木の子の左右は単なる係数だから後から掛けることができる。よって番号の最小値に関する条件を満たすような分割を求めればよい。挿入dpを考えた。大きなグループから順番に挿入していく。挿入したグループの中で番号が最小の人が先頭から数えてどの位置にいるかを状態として持てば条件のチェックができる。一つのグループに対して状態数は高々2^nであり、遷移も累積和を取ればまとめてO(2^n)となる。これをグループの数だけ繰り返せば、最後に挿入した一人がuに対応する。その番号はdpの状態としてわかっている。

Eに2時間近くかけたが解けなかった。現在行われているsetにおけるAliceとBobの勝ち数はちょうど4状態しかなく、それぞれからスタートしてsを一周し、戻ってきたときの勝ち数の状態とAlice・Bobの勝ち数の差が求まれば、ゲームの進行をシミュレートできる。いずれループに突入してそこを無限回周回するから、答えはそのループ一周におけるAliceとBobの勝ち数の大小と一致する。

つまりsを一文字ずつ見ながらスタート4状態に対する現在の状態とAlice・Bobの勝ち数の差を求めていけば解けはする。この時点での状態数は高々(4|s|)^4、実際は実現不可能なものがそこそこあって大幅に減っているがACには遠いようだ。ここからどうやっても削減できなかったので、遷移をビット演算を駆使して高速化してみたところ、最大ケースで7.5sec程度にはなった。当然通ることはなくそのままコンテスト終了。

4完47位で2905→2914(+9)。撮った動画をE問題に苦しんでいる2時間も含めほぼそのまま投稿した。AviUtlで前後を少し切り落としたらエンコードに1時間半かかって大変だった。どうせ大した編集はしないのだから、一度投稿してからYouTubeの機能でカットすればよいのかもしれない。

www.youtube.com

Amazonでいろいろ注文した。まず来週木曜日の家飲み用の缶詰とボドゲ。お酒はホスフィンによって提供される予定だ。次に、本棚と転倒防止の突っ張り棒を買った。部屋の机の上にはラノベが山と積まれており、何かあったら崩れそう。どうせホスフィンを家に上げるときどこかに動かさなければならないのだし、今買うのがちょうどよい機会だった。

昼間まで日記を書いたりなろうを読んだりしていた。午後0時半就寝。