1月

1日
11文字の檻
2日
あたしは星間国家の英雄騎士！1
4日
現代社会で乙女ゲームの悪役令嬢をするのはちょっと大変4
6日
紅蓮戦記2
ブラックな騎士団の奴隷がホワイトな冒険者ギルドに引き抜かれてSランクになりました8
13日
クラスで2番目に可愛い女の子と友だちになった3
14日
黄金の経験値
15日
ガリ勉くんと裏アカさん1
迷子になっていた幼女を助けたら、お隣に住む美少女留学生が家に遊びに来るようになった件について2
18日
迷子になっていた幼女を助けたら、お隣に住む美少女留学生が家に遊びに来るようになった件について3
20日
完璧な俺の青春ラブコメ

2023-02-06

週記（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で開催されるし、大学の教室を借りてオンサイト会場も用意される。どちらも交渉ややり取りはサークルの面々が頑張ってくれた。自分は何もやっていない。

東北大学競プロサークル puzzleknot によるコンテスト TUPC2022 を 3/4 (土) に AtCoder 上で開催します！
今年はオンサイト会場も設けます！コンテストの詳細，オンサイト参加の申込みについては以下のリンクを参照ください．https://t.co/qWJPc2j3HB
皆様のご参加をお待ちしております！#tupc2022
— TUPC2022 (@tupc_tohoku) 2023年1月30日

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

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月の読書記録を集計するなど今日のうちにやっておきたい作業を素早く終わらせて布団に倒れこんだ。

1月の集計
買った：21冊
読んだ：11冊
積読：+10冊
積読（累積）：+10冊
— こたつがめ (@kotatsugame_t) 2023年2月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ドルらしい。

Yeah, free API is being abused badly right now by bot scammers & opinion manipulators. There’s no verification process or cost, so easy to spin up 100k bots to do bad things.

Just ~$100/month for API access with ID verification will clean things up greatly.
— Elon Musk (@elonmusk) 2023年2月2日

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

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

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

きゅうくらりん　理論値！！！ pic.twitter.com/KjlRYRium1
— こたつがめ (@kotatsugame_t) 2023年2月2日

ラーメンを食べて帰宅。シャワーを浴び、しばらく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

サモラン野良カンスト達成しました😭😭😭😭😭😭😭 pic.twitter.com/yvZi2gApR6
— 社築🖥 (@846kizuQ) 2023年2月3日

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$ を考えると解けたと仰っていて確かにという気持ちになった。しかしその時点で解説を読んでいたので、本当にそのアイディアだけでコンテスト中に解けたかはわからない。

アライグマ「G問題は高速ゼータ変換みたいなやつなのだ！　アライさんもしばらく悩んだけど、テストケースを生成するためにBからAを作ろうとしたら解けたのだ！」
— 競技プログラミングをするフレンズ (@kyopro_friends) 2023年2月4日

コードゴルフ。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時半就寝。

2023-01-30

週記（2023/01/23-2023/01/29）

01/23(月)

午後3時少し前に起床。すぐ集中講義のZoomに接続した。

今週1週間参加する講義の名前は「応用数理総論」で、これだけだと何のことかわからないが内容は数理論理学である。実は同じ講義が学部生向けとしても開講されていて、自分は去年それの単位を取得した。だから知っている内容だろうし単位も楽に取れそうという見込み、純粋に理解を深めたいという気持ち、さらに今期の専門科目で他に興味のある科目がなかったため、以上3要素により受講を決めた。

初回の今日は基礎の確認で、命題論理、1階論理、再帰的関数、不完全性定理などが予定されていた。実際は3時間に収まらず、不完全性定理は次回に回された。内容的にはほぼ同じことを去年もやったはず。去年は資料が配られるだけだったが今年はZoomで実際に説明されるので、そこで何か得られるものがあるかと思ったら、特に何もないまま終わってしまった。まあ聞いているだけでわかるなら苦労はしないということで。

午後6時終了。今日オンラインだったのは予定していた講義室が取れなかったからで、明日からは対面になるらしい。

直後にインターン先定例会の会議に接続した。勉強会発表が終わった後の質疑応答の時間で、発表を聞いていないため特に何も言えることはなく、スライドを眺めて30分ほどで終了。

それから日記を書いて午後9時半頃投稿した。書いている途中でちょっとTLを見たとき興味深い話題を見つけ、それに関して少し調べていたので日記に書いておく。

.#マシュマロを投げ合おう https://t.co/pj7FH7xEFF pic.twitter.com/GEQAes9Nlx
— 競技プログラミングをするフレンズ (@kyopro_friends) 2023年1月23日

日曜日のARC-Dの話。std::stable_sortを使うと比較回数が足りるという話だったが、サンプルを試すと同じペアが2回聞かれてしまうらしい。本当にマージソートしているならこんなことは起こらないはずだし、余計な比較をしているのになぜ回数が足りているのかもよくわからなくなる。上のツイートでは解決しておらず、自分も気になったので調べてみた。

2727行目を見るとマージソートする前に7要素ごとに挿入ソートが行われるようだ。実はGCCの挿入ソートは同じ比較を2回行うことがある。逆にそれ以外の部分は普通のマージソートだから、これが理由だとわかった。

https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_algo.h#L2727

挿入ソートは、要素一つずつに注目して、前の要素より小さければ交換してさらに前を見るということを繰り返す実装になっている。ところがこれをそのまま書こうとすると、見ている要素のさらに前に本当に要素があるか毎回判定する必要が出てきてしまう。それを避けるため、最初に先頭要素と比較する処理が1819行目に入っていて、この比較が挿入ソート本体の比較とダブる可能性がある。

https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_algo.h#L1819

以上のことは日記を書いているときに確認した。月曜日の時点では見る部分を勘違いしていて、数列の長さが短いと挿入ソートになるせいだと言っていたが、それはマージ用のメモリが確保できない場合のみ実行される関数だった。通常時は上のような理由で比較がダブるはず。

std::sortは高速化のためにいろいろ複雑なことをしているから、比較回数は多くなりがちらしい。まずクイックソートのパーティション用pivotを決めるために何回か比較している。次に、クイックソートの再帰が深くなるとヒープソートに切り替わる。最後に粗くソートした配列を挿入ソートして終わり。比較のダブりも至る所で起こりそう。

今日が期限の期末レポートがあるので書いた。確率モデル論という講義。講義中に出された問題から3問選んで解けという課題で、実は昨年末に出された時点で2問解いてあったので今日は追加で1問解くだけ。1時間で完成した。

教員のやる気がなさそうで講義スライドも講義動画も使い回しらしいが単位取得には問題ない。問題3問というのも実は全15問中3問で、しかも2回目・3回目の講義で3問ずつ出題されるという偏りっぷりだから、講義の序盤の内容だけ把握すれば期末レポートが書けてしまう。いわゆる楽単というやつだった。

しばらくなろうを読んだりニコニコ動画を見たりした後、かなり久しぶりにTUPCのテスター作業をした。そろそろ気合いを入れないとまずい。

一段落して午前7時頃布団に入り、しばらくなろうを読んで午前9時就寝。

01/24(火)

午後2時半起床。天気予報によれば夕方から雪が降るらしく原付で登校できない。仕方なく地下鉄で向かったら案の定遅刻、と思いきや先生が機材の設定に手間取っていたためギリギリ間に合った。

今日は去年やっていない2階論理の話。本当はもっと内容があったが、2階論理以外は理解が及ばなかった。そもそも理解しようとしていなかった気もする。眠気が強くウトウトしているうちに時間が過ぎていった。

学食で食事して帰宅。雪は降りそうだがまだ降っていなかった。疲れて布団に倒れこみ、なろうを読んでいるうちに寝落ちした。午後8時半。

午後10時に目を覚ました。改めて寝直すか迷っていたがECRがあることに気づき起きていることにした。なろうを読んで時間を過ごし、午後11時半からECR142。

Dashboard - Educational Codeforces Round 142 (Rated for Div. 2) - Codeforces

Aは $h=1$ なるモンスターが2匹いれば一つ目の呪文で倒すべきで、それ以外は1匹ずつ倒していく。Bは最初にtype 1をすべて話し、次にtype 2とtype 3を交互に話すのが最適で残りは貪欲に取れる。場合分けを頑張る。

Cは、 $k$ 回操作するとき、 $2k$ 要素を一気に削除してから先頭と末尾に $k$ 要素ずつ振り分けると思ってよい。これで $p$ がソートできるのと $p$ の部分列として $k+1\dots N-k$ が現れることが同値。この判定を使って $k$ を二分探索する。

Dは $a_i\cdot a_j$ の先頭 $b$ 項が一致することと $1\le k\le b$ に対して $(a_i)_k=(a_j)_k^{-1}$ となることが同値。辞書順において $a_i$ より小さい $(a_j)^{-1}$ のうち最大のもの、あるいはその逆を試せば十分である。あらかじめ $(a_j)^{-1}$ をソートしておいて、 $a_i$ の位置を二分探索で求めるとよい。

Eは大変だった。 $m_1$ 、 $m_2$ を素因数分解した結果を使うと約数の全列挙ができる。これが $d$ になるので、 $d_1,d_2\le n$ によって $d=d_1\cdot d_2$ と表す方法のうち $d_1$ が最小のものを求めたい。 $d_1\le n$ は最後にチェックすればよいので、結局 $d$ の約数であって $n$ 以下で最大のものを求めることになる。

約数の全列挙の過程でさらにその約数も全探索することにしたら、最悪ケースである $m_1\cdot m_2$ が高度合成数の場合に1ケース0.5secくらいになった。微妙に間に合わないようだ。その後高速化しようといろいろ書き換えたもののむしろ遅くなる一方だった。

しばらく考えてまともな解法を思いついた。もし $d\le n$ なら $d=1\cdot d$ とするべき。そうでない場合 $d$ の素因数 $p$ を全探索し、 $d/p$ の結果を流用する。最適な表し方 $d=d_1\cdot d_2$ について、もし $d\gt n$ なら必ず $d_1\gt 1$ だから、 $p\mid d_1$ なる $p\mid d$ が存在して $d/p=(d_1/p)\cdot d_2$ もまた最適な表し方となる。

Fは4頂点あって初めて破綻するらしい。赤の辺でも青の辺でもパスグラフになるような塗分けがある。どうせこれが存在しないことが十分条件でもあるだろうと思ったが、そこから先にはまったく進めなかった。

5完33位。F1は赤の辺と青の辺が必ず存在するという条件を外した状態、つまり2を足したものをOEISに投げると見つかるらしい。FORMULAを辿っていくと $O(n^2)$ の式が見つかって、F1はすぐ解ける。F2も書いてあることを使って頑張ると解けるらしい。

A006351 - OEIS

しばらくTUPCのテスター作業をしていたが遅々として進まない。布団に逃げ込んで午前4時頃ふて寝。

01/25(水)

午前7時半くらいに目を覚まし、うっかり2時間ほどなろうを読んでしまった。

昼過ぎに目覚ましで意識を取り戻す。Classroomの投稿で今日の集中講義がオンラインになったことを知った。「悪天候により」と書いてあって、さてはと思って窓の外を見たら一面の銀世界だった。それはともかくとしてもう一度寝直した。

午後3時前に起床しすぐさま集中講義へ。講義資料が共有されていないのを休憩時間まで言い出せず、前半は内容を見落とさないよう必死に集中していた。資料を手に入れて満足した後半はあまり聞いていなかった。今日は様相論理やクリプキモデルの話で、去年の時点でそれなりに分かったと思っているから余裕をぶっこいていた。実際にはまだ意味不明な話も多いが単位を取るには不足しないだろうと信じている。

集中講義を終えてすぐ布団に倒れこんだが、今日は夜中のCFに備えてしっかり目覚ましをかけておいた。ひと眠りして起きたら午後11時過ぎ。半からCF #846 div.2に出た。

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

Aは奇数三つか奇数一つと偶数二つを使えばよい。判定だけだと思ったら出力も求められて非常に面倒。 $n\le 300$ なので3乗が通るように見えるが、マルチテストケースで $\sum n$ の上限が大きいためそれだとTLEしてしまう。しょうもない罠。

Bは $k=2$ と固定してよいので分割位置を全探索する。

Cは解法が壊れていた。一応問題概要から説明。 $n$ 人の人がいて、それぞれが好む料理の種類が $a_1,\dots,a_n$ で与えられる。テーブルが $m$ 脚あって、それぞれに座れる人数が $c_1,\dots,c_m$ で与えられる。ここで $\sum c\ge n$ である。今から $n$ 人の人を全員テーブルに座らせ、テーブルごとに配膳する料理の種類を一つだけ決める。座っているテーブルに配膳された料理が好きな種類のものだった人数を最大化せよ。 $n,m\le 2\times 10^3$ 。

自分は好む人数が多い種類の料理を座れる人数が多いテーブルに配膳していく貪欲を行った。計算量 $O(m\log n)$ に比べて制約が小さいのがよくわからないが、ともかくこれでpretestは通ったから、想定解も貪欲をしていただろうことがわかる。

しかしこれは大嘘である。コンテスト後に考えてみると、そもそも部分和問題を何回も解くようなケースを含んでいるからまともには解けなさそうだと分かった。結局このコンテストはunratedになり、C問題は後々削除された。

Dは下のbitからどんどん引いていくと操作後の値がわかる。直前のpopcountから1だけ減っていれば、もともとそのbitが立っていて今は立っていないということがわかる。そうでなければ逆。最後に引いた数を足して答える。

Eは辺の重みとして $g$ が現れることと $[l,r]$ に $g$ の倍数が二つ以上存在することが同値。後者の条件は $\lceil l/g\rceil\lt\lfloor r/g\rfloor$ と書ける。ここでうっかりfloor_sumを考えてしまった。sumを取るときに動かす変数 $g$ が分母に来ているので解けない。正解は $\lceil l/g\rceil$ を $O(\sqrt l)$ で列挙すること。ここで $l\le 10^9$ という制約が使える。

Fは選ぶ三つの数のうち最小でも最大でもない値はどうでもよいためソートすると「 $\min=a_l$ かつ $\max=a_r$ の三つ組が $r-l-1$ 個ある」と書けて寄与が分解できる。これで $\min$ と $\max$ がともに何かの倍数であるような場合の数が求められて、あとは約数で包除原理をすればよい。

GはまずSuffix ArrayとLCP Arrayを構築する。最初は同じ長さ $0$ の文字列がSuffix Arrayの $[0,n)$ に出現している状態だと捉え、そこから文字列の長さを増やしつつLCP配列を見て区間を区切っていくことで、長さに対して部分文字列が何種類、それぞれ何回現れるかカウントできる。

回数を頻度配列で保存することにしても更新は可能。この配列のうちインデックスが長さの倍数であるような位置について和を取ることで、特定の長さに対してdeliciousな文字列が数えられる。長さを全探索すると配列を見る回数は $O(n\log n)$ になり、十分高速。

全完したがC問題をうっかり通してしまったのはバカ発見器という感じで残念。コンテスト終了直後は4位と表示されていて、その後C問題が削除された結果10位になっていた。

システスについて、A問題をTLEで落とした人が上位にも少しいた。上で言及した罠がpretestに入っていなかったらしい。信じられないくらい性格が悪い。

今日のCFはまた音声入りで画面を録画していた。コンテストは破綻していたがせっかく撮ったので投稿したい。C問題に関してちょっと文章で説明を入れたりしてから投稿した。

www.youtube.com

Universal Cupというコンテストシリーズがもうすぐ始まる。中国で行われたclosedな5hのセットが出題されるらしい。1チーム3人なので参加するためにはチームを組む必要があるが、夏ごろのMulti-Universities Campとは違いOpenCupのSlackで何か募集が行われたり組まれたりはしないらしい。一人で出るには辛そうなので自分から探しに行く必要があった。

「チームどうしようかなあ」のようなツイートを行い、言及を待って突撃するという姑息な方法でチームを組むことに成功した。ぷらさんとかっつさんである。どうぞよろしくお願いします。

1st Universal Cup Annoucement - Codeforces

朝までTUPCのテスターをしていた。午前9時に布団に入り、小一時間なろうを読んで就寝。明日の集中講義もオンラインである。

01/26(木)

午後3時前に起床。今日はTAを休んで集中講義に参加する。オンラインだしTAの教室に行くだけなら行けるな……とも考えたが、雪が積もっていて外に出る気にならなかった。

すぐさま集中講義へ、と思ったらZoomリンクが見当たらない。月曜・水曜に使ったものはそれぞれその日時のミーティング専用らしく今日は使えなかった。しばらく待っても音沙汰がなく他の人がどうなっているのかわからない。恥を忍んでClassroomにZoomリンクがないとコメントしたら、先生からは「自分は繋がっているのですが」という投稿があった。

言葉の感じからするに、これは先生しか繋がっていないという意味で、他の誰もミーティングに参加できていないのだろう。案の定Zoomリンクを送ってくれとのコメントがぽつぽつ付いた。しかしそれから実際にリンクが送られてくるまでにはさらに時間がかかり、結局講義が始まったのは予定時刻の30分後だった。

その待ち時間の間に新春TCB2023の賞品を選択した。ちょうど今日の昼前にメールが来ていた。自分に回ってきた時点で何の賞品が残っていたか公開するのはあまりよくない気がするが、自分が何を選んだかはここで言ってよいだろう。トラックボールマウスを選んだ。

2021年の新春TCBでもほぼ同じ機種を貰っておりこれで二つ目。HHKBも2台、PCも2台あるのでバランスがよい。そして、このキーボードとマウスはすべて競プロで得た賞品となる。

新春TechFULの商品であるトラックボールマウスが届いた。
週記（2021/03/01-2021/03/07） - kotatsugameの日記

集中講義の話に戻る。今日は様相論理の続きで、これも去年結構頑張って理解したはずの部分である。微妙に書き方が違う気もするが、まあ方言みたいなものだろう。ということで今日は最初から話を聞く気などなく、Zoomに接続だけしておいてこの講義の課題を解いていた。5日間毎日2題ずつ課題が出されていて、そのうち1題ずつに答えるのが期末レポートになる。

話は聞かないとしてもスライドには目を通している。参考文献として井上真偽「恋と禁忌の述語論理」が挙げられていたのが印象的だった。名前はよく聞くが別作品しか持っていないしそれも積んでいる。

午後6時に終了した後準備して外出。徒歩でゲーセンに向かった。TAのために外出するのは気が進まないがゲーセンに行くなら話は別である。

立ち食いそばを食べ、午後7時半から閉店まで4時間ほどプレイした。2週間ぶりなので新曲が結構あり、今日はほぼそれを埋めるだけとなった。

ただし大きな成果も一つ。「TiamaT:F minor」で5アタフルコンを出した。SSS+に少し届かなかったのが残念。実はこれは今日1回目なので、譜面が体に染みついておらず変なところでアタックを出してしまった。

ティアマトフルコン！SSS+寸…… pic.twitter.com/dKeA6j5P1f
— こたつがめ (@kotatsugame_t) 2023年1月26日

油そばを食べて日付が変わってから帰宅。TUPCのテスター作業をしたり、集中講義の先生に質問したいことをまとめたりしたら朝になった。ちなみに明日の集中講義は最後だからと対面の予定になっている。

午前6時に布団に入り、そこから2時間ちょっとなろうを読んで就寝。

01/27(金)

午後2時起床。生協でラノベを受け取りつつ地下鉄で山に登った。午後3時に微妙に遅刻したが、月曜日と同様今日もまだ講義は始まっていなかった。

今日の内容は逆数学と順序数。これは去年の講義では影も形もなかったものである。何も知らないし何もわからない。そのまま講義が終わってしまったので、昨日まとめてきた質問を聞いてから講義室を出た。

ホスフィンに誘われて夕食を一緒に摂り、次の飲み会の日程をすり合わせるなど結構話し込んで帰宅。家に着いたのは午後8時前だった。

今日は生命情報システム科学のレポートの提出期限。最終回である。Classroomの課題ページに期限が設定されておらず、講義スライドを見ないと失敗するのはいつものこと。

今回の課題は、講義で扱ったアルゴリズム・手法・データベースをどれか選んでレポートを書けというものだった。ゲノムアセンブリをグラフを用いて行うとき、頂点を並べる問題にするとハミルトン路を探すことになって難しいが、適当に変形して辺を並べる問題にするとオイラー路を探すだけになって簡単ということが説明されていたので、それについて書くことにした。

具体的には後者が簡単であることを示すつもり。グラフがオイラー路を持つ必要十分条件を示せば量としては十分だろう。十分条件は構成的証明によって示そうと思っている。これだとクラスPに属するというだけでなく実際に単純なアルゴリズムで解けることがわかる点で嬉しそう。

知っている話なので特に何か調べる必要もないはず。楽に書けそうに見えたため余裕ができたと勘違いし、うっかりなろうを読んで2時間弱をドブに捨ててしまった。それから慌てて書き始めた。グラフ理論の話を細かくするのは趣旨から外れるが、日本語だけで説明しようとするとかなり注意深くやらないと不正確になってしまう。説明を考えるのには思ったより苦労した。

さらに今日はCFがあるので、日付が変わるまでの時間をフルに使えるわけではない。午後11時半を目前にしてギリギリ完成し、急いで提出してCF #847 div.3へ。

Dashboard - Codeforces Round #847 (Div. 3) - Codeforces

Aはサンプルに30桁の情報があるのでコピペする。Bは最大値が $s-r$ だと決まる。残りは適当に構築すればよい。入力に対して必ず解が存在するという制約が嬉しい。

Cは先頭要素の多数決を取ることで $p_1$ がわかる。そして先頭に $p_1$ が来ていない列が $p_2,p_3,\dots,p_n$ になるため、 $p_1$ をくっつけて出力すればよい。

Dは貪欲に取ってよい。マトリョーシカをサイズの昇順に見ながら、今作っている最中であるようなsetの個数を管理した。

Eは結構時間がかかった。サンプルを2進数に直してみると、どうやら $x$ で立っているbitの一つ下のbitが必ず0なら構築できそう。逆にそうでない場合構築できないことも何となくわかって、出したら通った。

Fは謎。黒く塗られた頂点が増えたら答えも小さくなるだろうと思って、500頂点まではLCAを使って距離を求め、それ以降はdfsで探索するコードを書いたらTLE。そこでクエリ平方分割し、基本はLCAで距離を求めつつ適当な回数ごとにまとめてBFSすることで答えを更新するようにした。これも最初の提出はTLEだったが、BFSで答えを更新しなくなった瞬間打ち切るのと、答えがすでに1のときLCAで距離を求めないのを実装したら、TL 4secのところ2.6secで通った。

Gはちょっと面倒。頂点1から距離1以下の頂点にトークンがあればよい。そうでない場合、トークンの移動先は常にボーナスが置かれた頂点でなければならない。まず、頂点1からボーナスが置かれた頂点だけを通ってたどり着けるトークンを距離とともに列挙した。ただしトークンが置かれた頂点自体にはボーナスが置かれていなくともよいことに注意。

列挙したトークンのうちどれかを頂点1まで持っていくには、その距離から1引いた回数だけ別のトークンでボーナス頂点を踏まなければならない。ここで、辺で隣接するボーナス頂点に1手でたどり着けるトークンがあれば、それでボーナス頂点を往復することで何回でも踏むことができる。そうでない場合も、ボーナス頂点に1手でたどり着けるなら1回だけ寄与できる。これも別に数えておく。

どのトークンを頂点1に持っていくか全探索し、そのたびに先ほど数えた値を差分更新して、必要な回数だけボーナス頂点を踏めるか判定した。グラフが木だと思い込んでいて探索で1MLEしたが何とか通った。

全完31位。Fでかなりしてやられてしまった。Eは $a+b=(a\oplus b)+2(a\,{\rm AND}\,b)$ を使うと $x=a\oplus b=2(a\,{\rm AND}\,b)$ となって、自分がサンプルを観察して得た考察がストレートに手に入る。

Gは頂点1に持っていくトークンは候補が複数あるなら距離が最も近いものとしてよいらしい。距離2なら別の候補によってボーナス頂点を1回踏めばよい。距離3以上なら、別の候補によってボーナス頂点を往復することができてこれまた達成可能。

「黄金の経験値」の続刊が決定したらしくかなり嬉しい。2巻はおそらくちょっと苦しい展開が最初のほうにあるはずで、少し怖がってもいる。

皆様の応援（経済力）のおかげで、二巻の発売が決定いたしました！
ありがとうございます！

男装の吸血鬼っぽい新キャラ……
いったい何ランなんだ（ https://t.co/nEuWTnX77Y
— 原純【黄金の経験値】１月１０日発売！ (@harajun1001) 2023年1月25日

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

01/28(土)

正午少し前に起きてAHC017に参加し、提出を行った。自分がこの時間に提出を行ったことは順位表からわかる情報である。

AtCoder Heuristic Contest 017 - AtCoder

そのあと食事して日記を書き、午後2時からUniversal Cupの1回目に参加した。Discordで通話しつつHackMDで考察メモを共有する今期のOpenCupと同じスタイルで、ルールも同様コピペ・検索あり、コーディングは同時に一人まで。

今日のセットは中国のICPC由来でShenyang Regional。コンテスト後にQOJにも上がった。

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

チームでDCAEFLIHの8完。自分はCAEIHを解いた。最終順位はShenyang Regional参加チームも含めて24位。

コンテストが始まってすぐ問題を3等分して読み始めた。先頭から読んでいたところもうDにACが出始めたらしいので、かっつさんに読んでもらったところ、一瞬で通った。その後Cが通されているのを見て、すでに読んだものを改めて考えてみると自明。これもすぐ通った。

しばらくしてAFLが通され始めた。チームメイト二人がFLを考察しているらしい。一応問題概要は読んだが、Lは解けていそう、Fは天才構築に見えて何もわからなかったので、Aを考え始めた。絶対値記号を含む式を二重積分すればよさそうで、端点を集めて区間を区切りそれごとに計算すれば解ける。PCが空いていたので書き始めた。

書き始めてすぐ、積分範囲の点が有限個しかない場合の処理が思ったより面倒なことに気づいたが、PCを空けても使う予定がないとのことだったのでそのまま考え考えコードを書いていた。1時間以上経過してようやく完成。サンプルのほかにいくつかWolfram|Alphaで計算したものも試してから提出。見事一発で通った。

次にEを考え始め、結構すぐに残す橋の本数で包除原理をすることを思いついた。これは偶奇にしか興味がないので、状態数を別のことに使える。まだPCが空いていたので書き始め、頭が混乱したときに2乗の木dpになっていると指摘を受けたりしつつ何とかサンプルを合わせて出したら通った。

その後Fがぷらさんによって通された。相変わらず何もわかっていないので感動。さらにかっつさんによってLが通された。小数の出力なのに判定が絶対誤差 $10^{-9}$ 以下になっていて不安という話をしていたので、真の値が1以下だから相対誤差のほうが値が大きくなり、つまり普通の誤差ジャッジと変わらないということを指摘した。

実装の間にIの考察が完了していた。 $a-b$ の値の昇順に並べると0以下の範囲とそうでないところで購入戦略が変わり、前者はインデックスの $\bmod 4$ を、後者は $\bmod 2$ を見ればわかる。1点更新をどうしようか迷ったがクエリを先読みしておけばセグ木に乗る。ノードに、そこに入っている値の数と、入っている一番左の要素を0番目としたときのインデックス $\bmod 4$ に応じた和を持てばよい。実装したら一発でサンプルが合って、半信半疑で提出したらそのまま通った。

その後は皆でHを考えていた。 $|P|\le|Q|$ とすると $Q$ の一部に $P$ が含まれるので、 $Q$ だけ考えればよい。ユニークな回文は高々 $\sum|S|$ 個しかなく、重複の削除はロリハで行える。そうやって $Q$ を全探索したうえで、まず $|P|=|Q|$ つまり $P=Q$ のケースが一つあり、残りは $Q$ から $P$ を取り除いた部分も回文になっている必要があるので、 $Q$ を回文二つに分割する方法の数え上げとなる。

回文は $\gcd$ っぽいことができたはずだと口走ったらぷらさんからARCの過去問が送られてきた。解説を見るとその通りのことが書かれていてバッチリ。だから $Q$ の回文による周期が高速に求められれば良いことになる。 $|Q|$ の約数 $d$ を全探索しても時間的には問題なさそうで、 $d$ が周期であるかを見たい。

C - 足の多い高橋君

ここで閃いた。 $Q$ の先頭 $|Q|-d$ 文字と末尾 $|Q|-d$ 文字が完全一致すれば、 $|Q|$ は周期 $d$ を持ち、特にこの周期が回文になる。この判定はロリハで行える。誰もロリハのライブラリも回文列挙のライブラリも持っていないようだったので自分が書くことにした。コンテストは1時間くらい残っているが結構ギリギリそう。ペアプログラミングっぽいことをするつもりで画面共有をしてから書き始めた。

まず回文列挙をPalindromic treeを窃盗して行う。それっぽく書き換えたら望み通りのふるまいをしてくれた。ロリハは空で書く。小文字を整数に直すとき、うっかり $0\dots 25$ にマップしていたのを壊れると指摘され慌てて $1\dots 26$ に書き直した。これでとりあえず回文の列挙はできて、周期の判定も行える。

math314.hateblo.jp

あとは $|Q|$ の約数を全探索するだけ。全体で調和級数になり間に合うと思ったがそれには $1\dots 10^6$ に対して約数を前計算しておく必要がある。vectorにpush_backしていたらそれだけで1sec以上かかるらしく、大きめの周期を持つように作ったランダムケースでTLの3 secをギリギリ超えてしまった。

ロリハの法を2種類から1種類にして提出したところ、TLEはしなかったもののWA。実装ミスではなくハッシュの衝突だと信じ2種類に戻して、代わりに約数列挙を $1\dots 99$ まではその場で試すように書き換えたらなんと通った。コンテスト終了17分前だった。ロリハを構造体や関数を用意してきちんと実装したのが後から便利だった。

もう解ける問題はなさそうと終了モードに。全員時間に余裕があるとのことなので、1問ずつ振り返る感想戦をお願いした。自分の分については上に書いたので割愛。

Dはかなり素早く通ったなという感想だったが、問題文を確認すると結構長くてびっくり。どうやらほとんどの部分はLoLの世界大会とプロチームの話をしているらしい。その知識があると読み飛ばせて楽とのことで、分担が思いがけず良かったということになる。

Lは実装担当がかっつさんだったが、考察の初手はぷらさんらしい。1回の攻撃ごとに必ず1体死ぬというもので、結構非自明だと思う。一瞬で出てきたらしくすごい。それにしても早い段階で解けていそうと思ったのにその後なかなか実装されなかったのが気になる。自分がそう思っていると伝えるコミュニケーションが足りていなかったのかもしれない。

午後8時前に解散。食事して午後9時からABC287に出た。

UNIQUE VISION Programming Contest 2023 New Year (AtCoder Beginner Contest 287) - AtCoder

AはとりあえずC++で書いてから、Perlからgrepを呼び出して数えるコードを提出しておいた。Bは愚直に探索。最初に $S$ と $T$ を全部読み込んでから判定しなければならないのが面倒。 $T$ 、 $S$ の順に与えられていれば $S$ は読みながら処理ができるのに。

Cは次数1の頂点が二つで残りが次数2の頂点であることをまず判定。サンプルも合って提出しようとするときにサンプル3の説明画像でループを目にして、グラフが非連結の場合に間違えることに気づいて慌てて書き直した。

Dは $S$ の左右からどこまでマッチさせられるかそれぞれ探索し、その情報を組み合わせればよい。

Eは文字列を辞書順ソートして隣接する文字列のペアだけLCPを計算すれば十分である。LCPの計算も愚直に行ってよい。比較に $\min(|S_i|,|S_j|)\lt|S_i|+|S_j|$ だけかかると評価すれば $O\left(\sum|S|\right)$ だとわかる。Suffix ArrayからLCP Arrayを構築するのにアルゴリズム的工夫を要求されるのは $\sum|S|=N(N+1)/2$ だから。

Fは2乗の木dp。先ほどUniversal Cupでも見たので何を使うかだけはすぐわかり、意気揚々と書き始めたが、実装を終えてサンプルが合わないのに気づいてから部分木の根を使ったか使っていないかも状態に持つ必要があることに気づいた。思ったより面倒。

Gは解法は一瞬だが実装に苦労。得点を先読み座圧してセグ木に乗せ、どの得点のカードが何枚使えるかと総得点を持つ。そういえば座圧セグ木もUniversal Cupで見たばかりか。この上で二分探索することでどの得点のカードまで使うかが判定できる。それより大きな得点のカードは全部使い、足りない分を調整すればよい。得点や枚数の書き換えにちょっと苦労してしまった。

Exは微妙なサイズの制約が気になる。番号が小さい頂点から順番に見つつ、今見ている番号以下の頂点だけを使って行き来できる頂点のペアを管理する。具体的には $N\times N$ のテーブルを更新していく。これはbitsetを使うとワードサイズを $w$ として $O(N^3/w)$ で行える。代わりに、具体的にどのタイミングで行き来できるようになったかがわからないが、これは並行二分探索を行うことで対処できる。これで $O((N^3/w+Q)\log N)$ になった。

1WAを出した。頂点 $u$ を見ているとき、 $s_1\rightarrow s_2\rightarrow u\rightarrow t_1\rightarrow t_2$ というパスを考えなければならない。 $s_1\rightarrow s_2$ と $t_1\rightarrow t_2$ は前に計算しておいたテーブルで、 $s_2\rightarrow u\rightarrow t_1$ は入力されたグラフになる。ところが $s_2$ を抜かして考えていた。サンプルが弱すぎる……。

1WA全完で19位。賞金には遠いかと思ったら上位にそれほど学生がいないようで、ペナがなければ滑り込めていたらしい。

Exは新しい頂点を見るたびにクエリの処理を行う $O(N^3/w+QN)$ でよかった。 $QN$ の最大値を $2\times 10^7$ ではなく $2\times 10^8$ と計算間違いしていた。たとえそうだったとしても通りそうな気はする。さらに、行き来できる頂点のペアのテーブルに更新がある度bitsetの_Find_firstと_Find_nextを使って列挙することで、 $O(N^3/w)$ で全点対間の答えを求められるようだ。

コードゴルフ。AはVimに負けていた。多数決を取るときにソートしてから50%でカーソル移動して真ん中の行の文字列を見る方法があるのは既出だが、そこから答えの出力を分けるのは自分では書けなかっただろう。

BはRubyで、 $T$ をまとめて正規表現のORとして表現しマッチする方針を書いた。しかしその後、判定したい文字列の4文字目以降と同じものが入力された文字列に存在するか見る方針で縮められた。これだと $T$ の判定が必ず失敗するので、わざわざ避けておかなくてよい。

EはRubyで縮めてみたがPerlに負け。文字列のXORを取ってヌル文字を探すことで、先頭からどこまで一致するのか一発で判定できるのがめちゃくちゃ強い。他は手付かず。

今日も音声入りで画面を録画していた。少し編集して投稿。

www.youtube.com

ずっと日記を書いていた。午前11時半就寝。

01/29(日)

午後7時起床。

昨日のUniversal Cup-Hの話で、回文の長さの約数列挙が $S=\sum|S|$ として $O(S\log S)$ に本当になるのかと指摘された。例えば $S/2$ くらいの高度合成数を長さに持つユニークな回文が $S/2$ 種類あるケースはないのか。考えた結果、2種類の回文が交差していたらその部分の文字列があらかた固定されて3種類目が交差できなさそうに見えたので、そういう説明をした。正確な証明はつけられなかった。間に合っているのでヨシ！

布団から出て食事し、午後9時からARC155に出た。

AtCoder Regular Contest 155 - AtCoder

Aから難しかった。昨日のUniversal Cup-Hに引きずられて考察がまとまらない。とりあえず $K\lt 2N$ のケースは真面目に判定できる。 $K\ge 2N$ のケースは $S'$ が周期 $2N$ を持つので、 $K\lt 2N$ のケースと同様に両端の文字列を求め、それが整合するか調べればよさそう。もうちょっと簡単になりそうに見えたがどうにもならないので書き、一発AC。25分くらいかかっていて辛い。

Bも難しい。 $||x-a|-b|$ のグラフがどういう形をしているか調べ、高々4つの区間にある傾き $\pm 1$ の線分として表現できると分かった。この区間と出力クエリの区間の端点を全部混ぜてソートすると、区間の中では右端または左端しか見なくてよい。これは遅延セグ木に乗る。ノードに対して対応する区間の端点を持ち、切片を情報として更新すればよいのだ。

ほんまかと思いながら実装。1WAしたがこれは出力クエリで $a=b$ となるケースだった。対応するノードが1個もないので $\infty$ が返ってしまう。無理やりノードをねじ込んで対処した。結局端点の情報はノードが持っているから、それさえ正しい値なら良いのだ。

Cはスムーズに考察できた。操作が可逆なので、 $A$ と $B$ 両方を何らかの正規形に直して一致するか判定する方針を考えてみる。まず、奇数が1個もなかったり、あっても離れている・偶数が存在しないといった理由で奇数を含むような操作ができない場合は、間の偶数を適当にソートしたもので比較する。ただし偶数が2個以下だった場合は操作できないのでそのまま。

奇数を含むような操作ができる場合、操作を繰り返して奇数要素を先頭に集めることができる。そして今偶数が1個以上あるのだから奇数の隣接swapが可能、つまりソートできる。偶数は2個以下ならそのまま、3個以上あればソートできるので、これらを結合したものが正規形になる。出したら一発で通った。

Dは $G$ を状態として小さいほうからdpすれば答えは出ると思ったが、 $\gcd$ 操作による遷移先を列挙するのが難しい。約数を列挙したり包除原理したりして何とか実装できたと思ったものの、間に合わなかったしそもそもWAだった。

3完75位。Bはやはり想定解ではなかった。コードゴルフは何一つ行っていない。

コンテスト後30分ほどDと格闘した結果03_rand3_*.txtというケースだけ全部落ちるようになり、何もわからないままCF combinedに出た。

Dashboard - TypeDB Forces 2023 (Div. 1 + Div. 2, Rated, Prizes!) - Codeforces

Aは $x^y\cdot y+y^x\cdot x=xy(x^{y-1}+y^{x-1})$ と変形。べき乗が嫌なので $x=1$ としてみると $2y=n$ となるから、 $n$ が偶数なら $y=n/2$ でよい。またこの式の値は必ず偶数になるようなので $n$ が奇数の場合解なしだともわかる。

Bは常に $p=1$ としても損しない。 $\sum a\cdot p$ の最大化のためには異なる素数はできるだけ積の形にして $a$ とするのがよい。同じ素因数を二つ以上含まないような数を貪欲に $n$ から取ればその和が答えとなる。

Cは各 $x$ が取りうる値の範囲がわかるが、もし最適解がこの範囲の端点にない $x$ を使っていれば、どちらかの端点に寄せても損しないとわかる。よって $x$ の取りうる値が範囲の左端・右端の二通りとなり、dpできる。

Dは、まずそのままの状態でループするなら、経路の途中からループしない点もしくは範囲外に飛ばす必要がある。ループしない点をあらかじめ数えておいて経路上の点を一つずつ見て足し合わせればよい。そのままの状態でループしないなら逆に飛ばしてはいけない点を考える。これはループする点もしくはループしないとしても今いる頂点にたどり着いてしまう点で、後者は逆向きの辺を張って探索し求めた。

Eは $\bigoplus_{i=1}^n i$ が $k$ の偶奇によって $0$ か $x$ か決まる。これが満たされていると、まず $k-1$ 個の部分列に分け、最後に余ったものをひとまとめにするという方法で構築できる。部分列に分ける際は $[i,x\oplus i]$ という2要素のものしか考えなくてよい。そうでなければ、適切に1要素選んでそれ以外をひとまとめにし、別の部分列の要素と交換することで2要素に直せるから。

Fは大変だった。本当は $a^{2^k}$ を考えなければならないのに $a^{k+1}$ を考えたまま実装まで終えてしまい結構時間を取られた。もともとの $a$ に長さ $l$ のループがあると、 $2^k$ ステップ後には $g=\gcd(2^k,l)$ として $g$ 個の長さ $l/g$ のループに分解されている。

逆に $a'=a^{2^k}$ に長さ $l$ のループが $x$ 個あれば、これを束ねて長さ $xl$ のループを作れそう。最小化すべき値は実はループの個数を数えているので、できるだけたくさん束ねるべきである。 $x$ の条件は $\gcd(2^k,xl)=x$ 、つまり $x\mid 2^k$ かつ $\gcd(2^k/x,l)=1$ 。 $a^{k+1}$ と誤読していたときは約数を見ながらdpしないと最適な $x$ が求まらなくて大変だった。それでも約数が少ないので一応解けはするはず。

今は単純な場合分けで分かってしまう。 $l$ が奇数なら $x$ は $2^0\dots 2^k$ を自由に選べる一方、 $l$ が偶数なら $x=2^k$ と確定する。復元は実際に $2^k$ 個置きに並べてループを作ればよい。実装が結構しんどかったが出したら一発で通った。

ここまではそこそこよかったが以降GもHも解けず。Hは $k$ の降順にソートすると $O(n^2)$ のdpが書けて、そこから先に進めなかった。

システスは全部通り6完50位、2887→2905(+18)。4か月振りに2900台に帰ってきた。結構長かった。

このコンテストも音声入りで画面を録画していたので、ノーカットで投稿した。3時間以上あってAviUtlの初期設定だと読み込み切れなかった。喋りながらRatedに出るのは初めてだったが、式を書きながら読み上げるだけでは何もわからない。やっぱり何とかして考察メモを画面に映す必要がある。

www.youtube.com

日記を書いて布団に入り、少しなろうを読んでいたら寝落ちした。午前9時過ぎだった。

2023-01-23

週記（2023/01/16-2023/01/22）

01/16(月)

午後4時起床。30分近くかけて布団から這い出てインターン先の定例会・勉強会に参加した。

先週の進捗は、金曜日の1on1でこの1週間何をするか決まったということのみ。まだ手を付けていない。簡単な修正なので、今週金曜日にある次の1on1までに終わらせることを期待されている。それくらいはさすがに達成したいものだ。

勉強会はKaggleの参加記だった。最近終了したコンペでめちゃくちゃ良い順位を達成されたらしい。機械学習は使わなかったとのこと。そして、機械学習を使わない解法が強いコンペだということが、順位表の上にいるチームの顔ぶれから分かりやすかったということが語られていた。競プロで順位表から得られる情報といえば問題の難易度がメインで、誰それが解いているから解法は○○だという推論は当てにならないと感じている。このあたりKaggleと結構違うのかも、と面白く思っていた。

とても好きな音MADが流れてきた。「テイキョウ・ヘイセィ・ダイガク」と言えば超有名な音MADだが、それとは別の人が勝手に裏バージョンを名乗って投稿している。正直ただの二番煎じだろうと思いながら見たらかなり完成度が高くてびっくりした。テンプレをなぞるだけではなく独自性もしっかりあって、しかも滑っておらずちゃんと面白い。このくらいネタが盛りだくさんのほうが好みだから、正直本家より好きかもしれない。

www.nicovideo.jp

先週の週記を書いていた。午後9時過ぎに投稿。いつものように校閲できていない。火曜日のセミナー準備のため月曜日に時間が取れないのがかなり厳しい。火曜日夜以降だと気持ちが離れてしまっている。

Amazonでパスタやパックご飯を購入した。少し前にお酒を買った時もそうだったが今日もAmazonポイントが使えず、なぜだろうと調べたところ、どうやらAmazonギフト券との併用ができないらしい。ほぼ確実に、自分のギフト券残高がなくなるより今のAmazonポイントが無くなるほうが早いだろう。今はほんの数百円程度なので諦めも付く。

セミナー準備を始めた。先週以下のようなことを言っていたが、今日に至るまで結局何もわかっていない。深夜までもう一度粘ってみるもどうにもならなかった。

昨日完成させるのを諦めた証明二つについては、片方は議論しているうちに思いつくことができたが、もう片方は何もわからず。自分で考えるのも苦しいためネットで誰かに尋ねたいところだ。
週記（2023/01/09-2023/01/15） - kotatsugameの日記

とりあえず助けを求めるツイートをして、明日のセミナーはここを飛ばして先の話を始めてしまおうかなと考えていたら、maspyさんからリプライを頂けた。そこにあった資料や方針を確認し、確かに行けそう！という気持ちに。ということでこれを発表することにしたのはいいのだが、その時間から読解して発表できる形に持っていくのに苦労し、午前5時までかけて何とか完成させた。

方針として、サイクル C、点 p に対して

f(p) = p から右方向に無限に進んだときに C を交わる回数

とて、f(p) の偶奇で内外を特徴づけることを目指します（競プロでもあるやつ）。

微小な回転により線分と辺が重なるなどが起きないとしてよくて、ぴったり頂点を通るところは適切に定義します。
— maspy (@maspy_stars) 2023年1月16日

ゴミを出して午前6時前就寝。布団に入ってから完成したと思ったセミナー準備の穴に思い至り、修正を考えながら寝入った。

01/17(火)

午前9時半起床。大学に向かい、購買でパンを買ってから教室に行った。購買が開店するのはセミナー開始と同じ午前10時なので、今日も微妙に遅刻ということ。

午前中は同級生の発表。今日はη-変換に関する定理を二つ示していた。証明はラムダ式の構成を見て丁寧に行う必要があり、大変そうだった。

午後0時半に終了し、購買で昼食を買って、食べている間に博士課程の方のセミナーが始まった。先週資料による定義の食い違いを発見したが、これは博士課程の方が本を誤読していただけのようだ。しかしそれ以外の部分も複雑で解釈に疑問が残る。定義がどう使われるかは別の論文を読む必要があるらしく、今日は解決されなかった。次回以降で解決されるのかもわからない。

本に書いてあるものと論文に書いてあるもので定義に食い違いがあっておかしいということを発見し、指摘した。来週に持ち越し。
週記（2023/01/09-2023/01/15） - kotatsugameの日記

午後2時過ぎに終了。少し休憩して半から自分のセミナーとなった。昨日寝る直前に発見したミス以外の部分は問題なく発表できたはず。ミスは結局修正できていないので、今日は諦める気満々だったが、なんだかんだ先生と同級生は1時間くらい考えていた。自分は早々に諦めてmaspyさんにリプライを送っていた。結局解決せず、午後5時過ぎ終了。

すいません、「左から順にPi……」のくだりで詰まりました。3つのregionのどれかが非有界であることを示したりしたいのですがどうにもなりません。何か手はないでしょうか
— こたつがめ (@kotatsugame_t) 2023年1月17日

学食で食事して帰宅。自分が入店したすぐ後5限終了の時刻になり、レジ待ちの列が学食の外まで伸びていた。

疲れ果てて帰宅し、かなり長い間YouTubeを見たりTLを見たりしてボーっと過ごしていた。この後は何をしようかなと考えて、ふと思い立ってICPCの参加記を完成させにかかった。ほとんどの部分は年明け最初の週に完成していて、あとはまとめっぽい部分を書くのと文章の手直しをするだけ。相変わらず時たまYouTubeを見ながらの作業だったため結構時間がかかり、投稿は午前2時になった。

kotatsugame.hatenablog.com

今回は5年間の振り返り記事も同時投稿。といっても大会の成績と参加記をまとめただけで特に何か文章を書いたわけではない。本当は書こうとしたのだが、そういうのは横浜の参加記のほうにまとめて、振り返り記事は単なるまとめページの意味合いでできる限りシンプルにしておいた。

食事してからまたYouTubeに戻り、しばらくして布団へ。なろうを読んでいたら寝落ちした。午前4時くらいだった。

01/18(水)

午後1時から2時までは起きていた形跡がある。なろうを読んでいた。

午後6時起床。布団でしばらくスマホを触ってから起き上がった。

今日は生命情報システム科学のレポート提出期限。相変わらずClassroomの課題には期限が設定されていないが、講義スライドにそう書いてあった。まったく非道なことをする教員である。

今回の課題は与えられた二つのデータを観察し比較して考えを述べよというもの。扱うデータはFASTQ形式で与えられており、この形式は単純なのでライブラリに頼らずとも自分で簡単にデータ読み込みの実装ができる。比較にプログラムを使ったならそれも提出せよと言われていたので、せっかくならとColaboratoryでレポートを書いた。

特に何事もなく午後10時くらいに完成。Classroomの課題提出画面でGoogleドライブからColaboratoryのファイルを直接提出すると、そのファイルのオーナーが自分から教員に切り替わるようだ。つまり提出したものを後からこっそり修正することができなくなるわけで、連携が実にうまくできている。

ラノベを読み始めた。日付が変わるくらいに「迷子になっていた幼女を助けたら、お隣に住む美少女留学生が家に遊びに来るようになった件について」3巻を読了。前半の運動会のシーンは主人公がこれでもかというくらい活躍していて、目立っていて、最高だった。その後のデートシーン二つもいい感じ。ストーリーとしてはいよいよ主人公の過去が明かされてかなり辛いが、好みのシーンが多かったため全体としてみれば良かったという感想になる。

来週は集中講義のためセミナーができない。そのしわ寄せが今週に来て、なんと明日もセミナーが行われる。朝方までそれの準備をしていた。昼からスタートで5限前に終わるため、時間が普段より短くなる。よって量も控えめでよいとのことで、昨日maspyさんに送ったリプライに頂いた返信をまとめた後、もう一つ補題を扱うだけで終えた。とはいえ今日も午前5時くらいまでかかっている。

まだ睡眠時間に余裕がある。ハーメルンやラノベを読んでいた。

今日のハーメルンは新作でも更新分でもなく、読み返し。主人公の設定もキャラも非常に好みで、この先の展開が楽しみで楽しみで仕方ない。U7のライブはおそらく行われるだろうが、どのように描写されるのだろうか。自分で妄想してニヤニヤしたりもしている。それくらい好きな作品だ。

syosetu.org

午前7時半就寝。

01/19(木)

正午過ぎ起床。大学に向かい学食で昼食を摂り、午後1時からセミナー。

前半は同級生の発表。今日は公理系をいくつか用意して何かする話。内容的にはそれなりに長くかかりそうだったが、ちょっと詰まったところで先生が切って90分ちょっとになった。

後半は自分の発表、の前に、同級生に火曜日の議論の穴を埋めるアイディアがあるらしいのでそれを聞いた。なんと見事に解決していた。一昨日maspyさんから教えて頂いた方法と異なったので、一応そちらも発表した。昨日準備した補題について少し触れて、こちらも90分くらいで終了。

購買でラノベを購入してから5限のTAへ。今日の発表は多次元空間における「球」の表面積や体積を求める話だった。この話題に関しては実は高校生の頃に調べていたことがあるので、自分にとってかなり懐かしいもの。当時は適当な座標軸に沿って切ることで一つ下の次元における球の表面積・体積に帰着して求めていたはず。今日はそうではなく、謎の等式から無理やり表面積の式を出し、それを積分して求めていた。

謎の等式について少し解説。 $n$ 次元の点 $x=(x_1,\dots,x_n)$ について $|x|=\sqrt{x_1^2+\dots+x_n^2}$ とし、値 $\exp(-|x|^2)$ を考えて空間全体で積分する。遠くに行くほど値が急激に小さくなるので、この積分値は有限。というか具体的には $\left(\int_{-\infty}^{\infty}\exp(-x^2)dx\right)^n=\Gamma(1/2)^n$ となる。

一方、 $|x|$ が同じ $x$ をまとめて計算すると、 $r=|x|$ で積分するとして $\int_0^{\infty}\exp(-r^2)S_nr^{n-1}dr$ となる。ここで $S_n$ とは単位半径の $n$ 次元球の表面積で、 $r^{n-1}$ 倍することで半径 $r$ の時の式になる。 $S_n$ は定数なので外に出せて、残りはこれまたガンマ関数で表すことができ、先ほどの式と比較することで $S_n$ が出るようだ。

なかなか難しかったが発表はかなりしっかりしていたように思う。板書の字もきれいで良かった。

学食で食事して帰宅。今日も疲れ果てておりTLやYouTubeで時間を無為に過ごした。2時間ほど経ってから2月のラノベ新刊チェックと注文の作業を行った。今回は26冊。嬉しい新刊情報を二つばかり記録しておく。

一つ目は「Vのガワの裏ガワ」2巻。1巻が出たのが11月だったから、たった3か月で新刊が出たということ。無事続刊してくれたことも嬉しいし、それがこんなに早く読めるというのはもっと嬉しい。

mfbunkoj.jp

二つ目は「世界で一番『可愛い』雨宮さん、二番目は俺。」。結構前にアイドルとかモデル、芸能人というキーワードでなろうを漁っていた時に読んだ作品で、結構好みだったという記憶がある。最後の更新から1年以上経過してほぼ忘れ去っていたところ、いきなり書籍化を知ってびっくりした。

gcnovels.jp

その後日付が変わるまでゼミの後始末みたいなことをしていた。今日聞いた同級生のアイディアをちゃんと証明にまとめるという作業。紙に書き、スキャンして先生に送った。

ABC285-Exを解いた。形式的べき級数で表されている部分が重複組み合わせを使った和の形になって、一向に閉じた状態にできなかったため、解説を開いて結構読んでしまった。

Submission #38159986 - AtCoder Beginner Contest 285

朝方までインターンの作業をしていた。久しぶりに触ったら依存ライブラリのアップデートか何かがあって、ちゃんと動く状態にするまで結構時間がかかってしまった。それさえできれば今日実装するものは簡単……と思っていたら、ライブラリの仕様にない内部の変数を触っていた部分でうまく動かないケースがあって困ってしまった。そのライブラリのコードを読んで何とか修正したが、結局仕様にない使い方をしているままのため、これもいずれ動かなくなるのだろう。

外から触られることを想定されていなさそうな_cellという変数を直接見ることになった。
週記（2023/01/09-2023/01/15） - kotatsugameの日記

1時間程度日記を書き、午前7時就寝。

01/20(金)

午後2時ちょっと前に起床。すぐ1on1が始まった。

自分からの進捗報告は昨日書いたコードの説明。特に問題なさそうでこれはすんなり終わった。ツールの下調べというタスクも振られていたので、残り時間はそれについて話していた。実はこのツールが要求するライブラリのバージョンと他のライブラリのバージョンが合わず、昨日もかなり苦労していた。結局どうやっても合わなさそうだと分かったが、合わないままでも動いたのでまあいいだろうということに。

終わってから大学に向かった。購買でラノベを買うだけのつもりだったが床屋が空いているのを見て思わず入店。散髪し、学食で夕食を摂って帰宅した。サークルはサボってしまった。

古典部シリーズの愛蔵版第1弾をAmazonで注文した。すっかり忘れているうちにリアル書店での予約は締め切られてしまったらしい。何はともあれ買えてよかった。Amazonギフト券を使えるのも嬉しい。

地元で買えるとそのまま実家に安置できるので嬉しいが、タイミングが合わなければ仙台の本屋で予約することになるだろう。限定生産とあるのでちゃんと予約を忘れないようにしたい。
週記（2022/12/12-2022/12/18） - kotatsugameの日記

しばらくラノベを読んで、午後9時からSRM844に出た。出場した赤以上23名のうち12名までもがRoom1に割り振られていた。

https://community.topcoder.com/stat?c=round_overview&er=5&rd=19550

Easyはdp。状態と遷移を掛けると10⁸になってちょっと怖い。注意点としてcakesは昇順に使う必要がある。これをしないとサンプルで落ちるのは非常に優しかった。

Medは難しかった。 $A\times B\times C$ の直方体の表面積は $2(AB+BC+CA)$ なので、あらかじめ $N=\lfloor{\rm paperArea}/2\rfloor$ としておく。 $AB+BC+CA\le N$ が条件なので、 $A$ を最大化する場合整数という条件を無視すれば $A=B=C=\sqrt{N/3}$ となる。よって $1\le A\le\sqrt{N/3}$ がわかる。これくらいなら全探索可能。

ここからなかなか先に進めなかった。 $AB+BC+CA=(B+A)(C+A)-A^2\le N$ となるので $B+A=\left\lfloor\sqrt{N+A^2}\right\rfloor$ とするのがよいかとも考えたが、サンプルが合わない。しかし $B$ の範囲は $A\le B\le\sqrt{N+A^2}-A$ と分かった。この時 $C$ は単に最大値を取ればよいので、 $C=\left\lfloor\frac{N+A^2}{A+B}\right\rfloor-A=\left\lfloor\frac{N-AB}{A+B}\right\rfloor$ 。

このような $B$ と $C$ に対して $ABC$ を最大化するのが目標である。 $C$ が整数という条件を忘れ、 $B\times\frac{N-AB}{A+B}$ が $B$ に対してどういうグラフになるか微分して計算してみると、 $B\lt\sqrt{N+A^2}-A$ なら微分係数が負になることが分かった。つまり先に求めた $B$ の範囲に対しては $B$ が大きくなるごとに単調増加する。

よって $B$ を降順に探索し現在の解を更新しなくなれば打ち切るという枝刈りが思いつく。解の初期値を $\left\lfloor\sqrt{N/3}\right\rfloor^3$ にしておけば十分高速そう。注意点として、 $ABC=AB\times\left\lfloor\frac{N-AB}{A+B}\right\rfloor$ ではなくあくまで $AB\times\frac{N-AB}{A+B}$ と解を比較しなければならないことに注意。オーバーフローが怖いのでfloorやceilを取って緩めに判定した。

計算量はわからないが乱数で試したところ十分高速だったため提出。この時点で20位ちょっととかなり低い順位だった。Hardには10分しか残せずそのまま終了。

チャレンジは自分は何もしなかったが、Medがボコスカ落ちていてびっくりした。さらにシステスでも大量に落ち、無事2完した自分の順位は8位まで上がった。レートは2894→2897(+3)でギリギリ耐え。赤が大量にいたRoom1はチャレンジで全部落とされ切ったようで、システス落ちが一人もいなかったのですごいなあという気持ちになった。

夜中はラノベを読んでいた。「完璧な俺の青春ラブコメ」を読了。非常に面白かった。主人公は顔も良く、勉強も運動もできて、おまけにコミュニケーション能力も高い。まさに完璧と言う他ない設定でかなり好みである。ストーリーについても、初めの方はいかにも不穏そうな空気を醸し出していたのに、恐怖していたドロドロした展開は最後までなく、純粋に楽しい気持ちで読むことができた。総じて最高。

朝まで日記を書いて午前9時前に布団に入った。ちょっとなろうを読もうとして、すぐ寝落ちしたらしい。

01/21(土)

午後3時頃に生協の弁当を受け取って、またすぐ寝た。午後6時半起床。布団でずっとなろうを読んでいて、午後8時を過ぎてようやく布団から脱出した。

昨日読んだラノベは本当に好きだったので読了ツイートに感想を書いていたが、それがアキバBlogで引用されたらしい。FFの方がツイートしていて見つけた。結構嬉しい。

「完璧な俺の青春ラブコメ」読んだ！非常に良かった、主人公が完璧すぎて最高！話も重そうな始まりだったのにドロドロしていなくて、最後までずっといい気分で読めた！
— こたつがめ (@kotatsugame_t) 2023年1月20日

blog.livedoor.jp

食事して少し日記を書き、午後9時からABC286に出た。

UL Systems Programming Contest 2023(AtCoder Beginner Contest 286) - AtCoder

Aから面倒。変なことはせず素直にC++で実装したのに、区間の始点や長さを間違えまくって合わせるのに少し手間取った。Bはsedで一発。Cは文字の置換より先にrotate操作を全部行うとしてよく、その回数を全探索。

Dは個数制限ナップザック問題なので、何も考えず $B$ を2べきに分解して解いた。あとから単に $B$ 回遷移しても間に合うことに気づいた。

Eは問題文にある通りの値のペアを距離と見てワーシャルフロイド。辺の重みとしてそれが向かう先の都市で売られているお土産の価値も含めた。経路の始点については出力時に加える。

Fはfunctional graphにおいて各頂点から $N$ ステップ移動した後の頂点の情報から $N$ を復元する問題。グラフとしてはループの集まりしか考えなくてよく、このとき $N$ をループの長さで割った余りがいくらかという情報が得られる。ループの長さを互いに素にして、中国剰余定理で復元すれば良い。

難しいポイントは $N\le 10^9$ かつグラフの頂点数が110以下というところ。単に素数を並べるだけでは29まで使う必要があり、足りない。2²などべき乗を使えば良いのでは、と思いついて適当に全探索すると $2^2\times 3^2\times 5\times 7\times 11\times 13\times 17\times 19\times 23$ が見つかった。調べた範囲ではこれが唯一の解だった。

Gはちょっと面白い。歩道をマルチグラフと見ると、使った辺が全て連結で、次数が奇数の頂点が0個または2個しかない。そのように辺を選べればよい。ここで、 $S$ に含まれない辺をすべて2回通ることを考える。すると $G$ が連結という条件から自動的に使った辺も全て連結になる。あとは次数に関する条件を満たせればよい。

$S$ に含まれない辺たちからグラフを作ると、その連結成分の中ではある程度好き勝手できる。具体的には2頂点ずつ次数の偶奇を入れ替えられる。次数が奇数の点が奇数個あるとどうしても1個残ってしまうようだ。このチェックをすべての連結成分に対して行い、残った点の数が合計で2以下になっていればOK。そうでなければ不可能。

Exは結構簡単だった。線分 $ST$ が $C$ と交差しない場合は直線で向かえば良い。そうでない場合、 $S$ から $C$ 上の点に移動し、 $C$ 上で別の点に移動してそこから $T$ に行くということになる。真ん中の部分は多始点多終点の最短経路問題になる。グラフがループなので簡単に解けるが何も考えずdijkstraを使った。

問題は、 $S$ または $T$ から $C$ の内部を通らずに直線で辿り着ける $C$ 上の点をどう判定するかについて。1点の判定に $O(N)$ かかると思ってしばらく判定回数を減らす方向で考えていたが、そもそもの判定が $O(1)$ で行えた。 $p_i=(x_i,y_i)$ とすると、 $S$ から $p_i$ を見たとき右手に $p_{i-1}$ 、左手に $p_{i+1}$ がある場合 $S$ から $p_i$ に辿り着けないらしい。外積で判定できる。

出したら通った。1時間ちょっとでノーペナ全完、順位は9位。Fでループの長さの組を見つけるのに手こずっているが、それがなくても賞金には遠かった。Exは $S$ と $T$ を含めて凸包を取れば $C$ を経由するときの距離が簡単に出せるらしい。頭が良すぎる。

コードゴルフ。AはAWKで縮めていたがVimにボロ負け。行の範囲を指定すると、それを一気に別の行の下に挿入するmoveという命令があるらしい。これを知らないし、知っていたとしてもその周りの部分を縮めきれたとは思えない。

Bはやはりsedで速度差で勝ち。DはRuby。コンテスト中に自分で80Bのコードを書いたが、コンテスト直後に見ると同じ長さのコードがもう一つ提出されていて、そちらが3B縮み最短になっている。他は手付かず。

午後11時半からCF #845 div.2。

Dashboard - Codeforces Round #845 (Div. 2) and ByteRace 2023 - Codeforces

Aは操作で挿入される要素のparityが元の要素と変わらないため、単純に1要素削除だと思ってよい。

Bは $p$ の内部の転倒数、 ${\rm rev}(p)$ の内部の転倒数、 $p$ と ${\rm rev}(p)$ にまたがるペアによる転倒数の三つに分けて考える。前二つについては、 $p$ で転倒数に寄与するペアは ${\rm rev}(p)$ では寄与せず、逆も然り、ということで合わせて $n(n-1)/2$ になる。三つ目は明らかに $n(n-1)/2$ 。よって答えは $n(n-1)n!$ である。

Cはちょっと難しかった。smartnessを見ながら尺取り法のようなことを行う。各topicを誰が担当しているか管理し、逆に人ごとに担当するtopicの数も数えておいて、それが0になった人をチームから抜いていくという方法で行える。問題はチームに人を追加するときの処理について。

担当するtopicすべて、つまりsmartnessの約数をすべて見る必要がある。事前に $a$ の重複を取り除いておけば見る個数は十分少なくなるが、そもそも約数を列挙する部分で $O(\sqrt a)$ かかってしまう。どうしようもないので祈りながら提出したら爆速で通った。

Dはちょっと面白い。時刻 $t$ におけるある頂点の値は、そこから $t$ 段下った子に最初に割り振られた値のbitwise XORになる。そのような子が存在しなければ当然値は0。存在するとき、子から一つ選ぶと、それ以外の頂点にどんな値が割り振られていても選んだ子の値次第で0か1かが決定するから、1になる割り振り方は必ず $2^{n-1}$ 通りだとわかる。よって各頂点について値が1になり得る最大の $t$ を求めるだけになり、単なるdfsで解ける。

Eはちょっと苦労した。辺の向きを入れ替える代わりに逆辺を追加すると考えてもよい。その状態である頂点から他のすべての頂点に辿り着けるなら、通る有向パスたちは木になるように取れて、それに沿って改めて辺の向きを決定できる。

追加した逆辺込みで強連結成分分解したとき、入次数が0の成分が一つだけであるかをチェックしたい。最初に分解してあとはマージしていけば良いかと思ったら、マージで内側に飲み込まれてしまう辺を入次数にカウントし続けてしまうようで2WAした。コストで二分探索すると判定の度に真面目に分解できるためOK。

Fは分割統治。区間の最大値が固定できると、考える値は最大値と累積XOR二つのXORになって、そこから片方の端を固定するとbinary trieで最大値が求まりそう。しかしこのbinary trieには考えている区間の値だけを乗せておきたくて、少し難しい。

区間の最大値で分割すると区間の幅が抑えられないので、binary trieを構築する段階でTLEしてしまう。そこで区間の真ん中で分割することにした。ABC282-Exの解説を見ながら実装。1.8secで通った。

Editorial - HHKB Programming Contest 2022 Winter(AtCoder Beginner Contest 282)

1時間17分で全完、25位。

ベッドのシーツや掛け布団がずっと春・秋用だったのを冬用に変えた。流石にもう耐えられなかった。ちなみにTwitterや日記でずっと布団という言葉を使っているが、これは自分にとって寝床一般くらいの意味合いで、実際はベッドで寝ている。

ABCの画面録画＋音声をYouTubeに投稿した。編集は一切行っていない。実況と銘打っている通りコンテスト中はあれこれ口に出しながら解いていたつもり。普段はわざわざ音声を入れないのだが、今日はたまたまその気になっていた。そういうタイミングで全完できたのも運が良かった。

www.youtube.com

朝までなろうを読んでいたが途中で放棄した。興味が薄れたのと、やらなければならないタスクが溜まっていたから。一応記録しておく。

https://ncode.syosetu.com/n7707gs/

日記を書き、さっきとは別のなろうを少し読んで午前11時就寝。タスクが溜まっているとは何だったのか。

01/22(日)

午後6時起床。そのまま布団でなろうを読んでいたら、午後7時半頃に今日の昼行われたJOIG本選の過去問が上がっているのを見つけ、飛び起きた。

JOIG 2022/2023 本選過去問 - AtCoder

Aはよい。Bはまともな性質がなさそうだが単に $O(N^2)$ でシミュレートすればよい。Cは音の強さが固定なので、家から最も近い座標を左右で求め、比較すればよい。

Dは葵が操作する行を全探索し、各列の表のコインと裏のコインの枚数を差分更新する。凛はそれを見て貪欲に操作すればよい。 $O(HW)$ 。

Eは $k$ を全探索すると左右が分割できるので、それぞれ解ければよい。実際、 $HW$ 頂点のUFを持って見ている範囲の頂点だけマージしていけば可能。

Fは解けていない。

コードゴルフ。Aは追加してから条件をチェックして削除すると書きやすい。sedで実装して満足していたらVimで縮められた。Bは真面目に数列の要素を一つずつ減らしていかなくても必要な値は計算できる。これで結構縮んだが、まだ隙があったようで取られた。CはOctave。以降は手付かず。

午後9時からARC154に出た。

AtCoder Regular Contest 154 - AtCoder

Aは $A$ をできるだけ小さくするのが最適とエスパー。桁ごとに数字を見て、 $A$ のほうが小さくなるようにswapしていけばよい。

Bは操作を分解し、最初に削除を全部行ってそれから挿入すると思ってよい。 $S$ と $T$ を構成する文字の種類・数が異なれば一致させることができない。そうでない場合、削除しなくてよいのは $S$ のsuffixであって $T$ の部分列になっているもののみだから、その長さの最大値を求める。

Cは $i=N$ で操作できるのでちょっと難しい。もしこの操作ができなければ、要素をコピーして区間を広げていくと思えるので、 $B$ から隣接する重複要素を取り除いたものが $A$ の部分列になっていることが必要十分条件になりそう。正確には要素が後ろにコピーできないので少し違う。

$i=N$ で操作するのは $A$ をrotateするのとほぼ同じに見えた。そこで、逆に $B$ をrotateしてから先程の判定を行うことにした。rotate状態が $N$ 種類あって毎回 $O(N)$ で判定可能なので、間に合う。しかしWA。

冷静に考えると、 $B$ のどの隣接する2項も等しくなければrotateはできない。この場合はそもそも操作後の状態としてはありえないので、最初に $A=B$ であるか判定するだけでよい。逆にそういう2項がある場合はそこを使って $B$ をいくらでもrotateできるので、最初にちょっと触れた「要素を後ろにコピーできない」制限も回避できる。これで出したら通った。

Dは難しかった。質問の回答がYesだとあんまり情報がないため、なんとかしてNoを見つける必要がある。 $i=j$ とすると見つけやすいのではないかと考えた。 $k$ を固定し、 $i=j\ne k$ に対してすべて聞くことで、 $2P_i\le P_k$ なる $i$ を集めることができる。これを何回か行うと $P_k=1$ なる $k$ を見つけることができる。

今度は再帰の帰りがけに各要素の値を決定していくのかと思っていたが、実はこの時点で $P$ をソートすることができる。 $P_l\ne P_r$ という条件のもと、 $P_l\gt P_r\Leftrightarrow P_l+1\gt P_r$ となるからだ。

最初に $k$ を見つけるとき、固定する $k$ をランダムに決めることで候補が4分の1になることが期待できる。後からソートする分も合わせるとクエリが微妙に足りない気もするが、とりあえずジャッジを書いて手元で試してみることにした。

std::sortを使うと全然足りなかったが、std::stable_sort、つまりマージソートを使うことでかなりいい感じになった。数回試して通りそうだったので提出。最初の提出では1ケース落ちてしまい、実際手元のランダム順列でも落ちるケースを発見したものの、乱択だから何回か出せば通るだろうと思って全く同じコードをもう一度出したら通った。

残り1時間はEとFを半々くらいで考えていた。Eは何もわからず。Fは下の記事と同様にして $k$ 種類持っている状態から新たに1種類ゲットするまでにかかる回数の確率変数を $X_k$ とおくと、 $f_k(x)=\sum_n E[X_k^n]x^n/n!$ という指数型母関数を $k=0\dots N-1$ で掛け合わせられれば解けることまではわかった。

コンプガチャに必要な回数の期待値の計算 | 高校数学の美しい物語

4完32位。コードゴルフはAをRubyで縮めたのみ。

今日も画面録画＋音声を撮っていたので、YouTubeに投稿した。E以降はバッサリカットした。最近新しい動画が見たいですというコメントを頂いたので、昨日今日とマイクに向かって喋りながらコンテストに出てみた。しかし編集する余力はない。ゆっくり実況など夢のまた夢である。

またUnratedのコンテストしか動画にしていないのもちょっと気にしている。本当はAGCの実況を作ってみたい。しかし今の形式だと紙の上での試行錯誤が動画に反映されず、面白くなさそう。板タブで書くのは面倒だし、紙に書くと動画で見えない。やはり手元を映してみたい。

www.youtube.com

実は、コンテスト参加時の画面の録画自体はここ2年ずっと行っている。今その動画ファイルが300GB以上あってPCのSSDを圧迫しているが、しかしこれはShadowPlayでキャプチャした動画ファイルをそのまま保存しているからで、適当にエンコードしておけば6分の1くらいになることに気づき、今日はそれからずっとエンコーダーを動かして圧縮に勤しんでいた。

エンコードしているPCはCPU使用率が100%に張り付いて使いづらいので、別のPCで日記を書いていた。また結構な頻度でなろうに気を取られていた。

午前8時過ぎに布団に入る。なろうを読んでいたら午前9時頃寝落ちした。来週一週間、午後3時から6時まで集中講義である。ただ明日はオンラインになったのでこの時間までのんびり起きていた。

2023-01-18

Aobayama_dropoutのまとめ

Aobayama_dropoutの5年間を振り返ります。

2018年

メンバー

AokabiC
Yukly
kotatsugame

記録

大会名	順位（完数）	参加記
模擬国内予選	31位（4完）
国内予選	40位（4完）	ICPC2018国内予選参加記 \| puzzleknot 公式サイト
JAG夏合宿		JAG夏合宿・ACPC2018 参加記 - kotatsugameの日記
		JAG夏合宿2018 参加記 \| puzzleknot 公式サイト
アジア地区横浜大会	21位（4完）	ICPCアジア地区横浜大会 2018 参加記 - kotatsugameの日記

2019年

メンバー

AokabiC
Yukly
kotatsugame

記録

大会名	順位（完数）	参加記
模擬国内予選	17位（4完）	ICPC模擬国内予選 2019 参加記 - kotatsugameの日記
国内予選	7位（5完）	ICPC国内予選 2019 参加記 - kotatsugameの日記
JAG夏合宿		JAG夏合宿2019 参加記 - kotatsugameの日記
		JAG夏合宿2019に参加しました - aokabic
アジア地区バンコク大会	19位（6完）	ICPC Asia Bangkok Regional 2019 参加記 - kotatsugameの日記
		ICPC Asia Bangkok Regional 2019に出場しました - aokabic
アジア地区横浜大会	16位（5完）	ICPCアジア地区横浜大会 2018 参加記 - kotatsugameの日記
		ICPCアジア地区横浜大会2019に出場しました - aokabic

2020年

メンバー

AokabiC
Yukly
kotatsugame

記録

大会名	順位（完数）	参加記
模擬国内予選	10位（6完）	ICPC模擬国内予選 2020 参加記 - kotatsugameの日記
国内予選	13位（5完）	ICPC国内予選 2020 参加記 - kotatsugameの日記
模擬地区予選	12位（7完）	ICPC模擬地区予選 2020 参加記 - kotatsugameの日記
アジア地区横浜大会	10位（8完）	ICPCアジア地区横浜大会 2020 参加記 - kotatsugameの日記

2021年

メンバー

Yukly
ha15
kotatsugame

記録

大会名	順位（完数）	参加記
模擬国内予選	5位（7完）	ICPC模擬国内予選 2021 参加記 - kotatsugameの日記
国内予選	8位（5完）	ICPC国内予選 2021 参加記 - kotatsugameの日記
模擬地区予選	8位（9完）	ICPC模擬地区予選 2021 参加記 - kotatsugameの日記
アジア地区横浜大会	8位（6完）	ICPCアジア地区横浜大会 2021 参加記 - kotatsugameの日記

2022年

メンバー

ha15
mine691
kotatsugame

記録

大会名	順位（完数）	参加記
模擬国内予選	2位（7完）	ICPC模擬国内予選 2022 参加記 - kotatsugameの日記
国内予選	13位（5完）	ICPC国内予選 2022 参加記 - kotatsugameの日記
模擬地区予選	14位（6完）	ICPC模擬地区予選 2022 参加記 - kotatsugameの日記
アジア地区横浜大会	9位（6完）	ICPCアジア地区横浜大会 2022 参加記 - kotatsugameの日記

2023-01-18

ICPCアジア地区横浜大会 2022 参加記

2022/12/27-2022/12/28に行われたICPCアジア地区横浜大会に出場しました。チームはAobayama_dropoutで、メンバーはha15さん・ホスフィンさん・僕です。

これが自分にとって5回目、また早生まれでないため最後のアジア地区大会です。さらに2019年以来3年ぶりにオンサイトで開催されたということで、なかなか感慨深いものがありました。

前日（12/26）

日付が変わるくらいまで持ち込むライブラリの準備をしていました。自分のライブラリほとんどに加え他の人のライブラリからいくつか、さらにACLから二分探索付きセグ木も持ってきてA4用紙10枚分くらいになりました。特に写経のことは考えておらず、コピペ前提の長大なコードもそのまま印刷しました。

GitHub - kotatsugame/library

他の人のライブラリから窃盗してきたコードは以下の通りです。ほぼお守りみたいな感じです。

その後チーム紹介ドキュメントのメイキング記事を書いていたら寝るのが午前4時半になってしまいました。

1日目（12/27）

無事午前8時に起床し、午前9時半の新幹線に乗りました。自由席のない速い列車なので東京駅までは1時間半ほどです。車内では爆睡していました。

東京駅に着いて新幹線ホームでコーチのむげんさんやチームsuzukaze_Aobayamaの三人と合流し、そこから横浜駅に向かって自チームの残り二人とも合流しました。ちょうどお昼時だったので、横浜駅のレストラン街で昼食を摂りました。

午後1時ごろに会場に到着し、当然チーム全員が揃っているためすぐ入場しました。開始まで1時間ほど時間があるので、チーム紹介ドキュメントを読んだり、他チームと交流したりしていました。

午後2時に挨拶があって、リハーサルが開始されました。今年は4問で、Aは簡単枠、Bはインタラクティブの練習、Cはちょっと前のアジア地区A問題、Dはもっと昔の過去問でした。

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

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

ホスフィンさんがAをさっと通したあと、自分がBを通しました。US配列に慣れておらずかなり苦労しました。またこのとき、Vimを使う自分とhaさんで.vimrcに書く内容について合意を取っておきました。と言ってもタブ幅と自動インデントに関することだけなので、ほんの数行です。

その後は特にやりたいこともなさそうだったので、そのままPCを占拠しDを実装しました。この問題はリハーサルの場で何度か見たことがあって、記憶の通り書いたらFAでした。

残ったCはhaさんに押し付けました。問題なく通りましたが、実装されている間に順位表が凍結され、YesNoがあるわけでもないので、結局他チームがどのくらい解いたのかはわからないままです。

その後assertや副作用のない無限ループを書いてREやTLEがちゃんと出ることを確認していました。また印刷も色々試しました。メモ用紙が欲しい場合は適当なファイルを印刷してくださいとのことだったので、/dev/nullを印刷したところ、1文字以上あるファイルを印刷しないと紙が出ないと言われました。

オンサイト豆非知識ですが、実は0バイトのファイルを弾くという処理が1日目終了後に追加されました
— くりんぺっと (@climpet) 2022年12月28日

リハーサル後はチーム紹介です。自チームのスライドが表示された瞬間笑い声が上がったので、作った側としては報われた気持ちになりました。

チーム紹介の時間です。各チーム、ユニークなスライドを送ってくれました。 pic.twitter.com/75SD69TOdf
— ICPC2022JP (@icpcjapan) 2022年12月27日

全チームの紹介が終了し、解散してホテルに着いたのが午後5時半ごろでした。今日泊まるホテルは単にsuzukaze_Aobayamaと揃えただけですが、たまたま3年前と同じでした。ホスフィンさんと同室です。

1時間くらいしたら東北大勢全員で中華街に夕食を摂りに行くことになっていて、それまでの間に昨日書いたチーム紹介ドキュメントのメイキング記事を微修正して投稿しました。

再三強調しておきます。このコードは実行すると自分自身のソースコードをそのまま出力するプログラムになっているので、ぜひお手元で実行してみてください。チーム紹介に「Quine」と書いておきましたが、この語彙は一般的でなく、あまり伝わっていない感触がありました。

kotatsugame.hatenablog.com

中華街では当然中華を食べました。

食事
・青島ビール
・コーンスープ
・牛バラ肉の醤油煮込み
・マーボー豆腐 pic.twitter.com/OyAFeJiHZT
— こたつがめ (@kotatsugame_t) 2022年12月27日

・炭火焼きチャーシュー炒飯
・ゴマ団子
・愛玉子（オーギョーチー）←自分
・マンゴープリン pic.twitter.com/a7rkqLgyFr
— こたつがめ (@kotatsugame_t) 2022年12月27日

ホテルに戻ってから、US配列に慣れるため持ってきたキーボードを使ってPCKの問題を解いていました。このキーボードは2019年、アジア地区横浜大会の企業賞で獲得したものです。

LegalForce様からUS配列のキーボードをいただくことができました！
ICPCアジア地区横浜大会 2019 参加記 - kotatsugameの日記

午後11時半ごろ就寝しました。その時間からCF div.2がありましたが、流石にパスしました。

2日目（12/28）

午前6時半に起き、ホテルの朝食を摂って、部屋に戻ってきてからは昨日のCF div.2を解いていました。結局チームで集合する午前8時半までに解き終わらず、ホテルから会場に向かう途中で実装を終えてテザリングで提出しました。なんとか通りました。

午前9時前に会場入りし準備をして、いよいよコンテスト本番です。

コンテスト

問題文：https://icpc.iisf.or.jp/2022-yokohama/wp-content/uploads/sites/9/2022/12/all_with_cover.pdf

順位表：https://icpcsec.firebaseapp.com/standings/

序盤

全員で使うようなテンプレもないので、序盤の動きについてはあまり細かく決めていませんでした。.vimrcについては、自分が書くときにはいつの間にか必要なものが整備されていました。

ホスフィンさんがシステムへのログインとAを、haさんがBを担当し、自分はC以降を順に読んでいました。以下、読めた分までの各問題の印象です。

C：明らかにフローっぽい見た目をしていますが、どうすればいいかは全くわかりません。シャッターを「2枚」壊すというのはどうやって表現するのでしょうか。

D：ずらすコインを全探索して、平行移動はバウンディングボックスを見る、ということをしたくなりました。しかし実装もコーナーケースも辛いし、そもそもこの全探索は間に合いそうにありません。

E：dpの高速化を考えます。最近ABCで見た分割統治をしてみたくなりました。 $\bmod{998244353}$ が2べきを強調する形で書かれているので、統治部分では畳み込みをするのではないかと疑いましたが、効きそうな形にできませんでした。

F：適切な言い換えができるかどうかという問題に見えます。すぐには思いつきません。

G：木から辺を1本削除し、1本追加してできた新しい木において、特定の2頂点間の距離を最大化します。説明のため2頂点を $s$ 、 $t$ とおきます。削除する辺はもともと $st$ パスに乗っていたものとしてよいです。どれを削除するか全探索すれば解けそうに見えました。

Gを詰めているうちに、グリッドという問題設定を完全に忘れ去ってしまいました。どういうことかというと、どんな辺でも追加してよいと勘違いしたのです。この場合、辺を削除してできた二つの連結成分それぞれで $s$ 、 $t$ から最も遠い頂点を選び、結ぶのが最適です。実装もやればできます。

このあたりですでにAは通っており、Bも提出が行われました。残念ながらWAだったのですが、ただの出力形式ミスだったのですぐ直り無事2完となりました。インタラクティブではこういうミスはありがちで、まあどうしようもなかったと思います。

G問題

Gの考察をうまく伝える自信がなかったので、自分で書いてしまうことにしました。順位表を確認すると、AB以外にACが出ているのはDEFのみのようで、FAが狙えるかもとワクワクしました。

しばらくして書き上がるも、サンプルが合いません。ここでようやく勘違いに気づきました。それと同時にまだACが出ていないことにも納得が行きました。諦めてPCを空けようとしましたが、その時点では特にすることもなかったため、そのままPCの前に座っていました。

冷静になると、追加する辺 $uv$ を全探索する方針が生えます。 $st$ パス上で $u$ から最も近い頂点を $p_u$ 、 $v$ から最も近い頂点を $p_v$ と置くと、 $p_u\ne p_v$ を満たす場合のみその間の辺を削除することで $st$ パスが $uv$ を経由するようになります。

各頂点 $u$ に対し $p_u$ 、 ${\rm dist}(p_u,u)$ 、 $st$ パスにおける $p_u$ の位置が求まれば解けます。頂点 $s$ を根とすると $p_u={\rm lca}(t,u)$ と書けるため、ここから他の値はすべて求められました。

LCAライブラリを貼りたくなりますが、写経が面倒です。今はクエリの片方が $t$ と固定されているので、単にdfsするだけで求まることに気づきました。これを使って再度実装するとサンプルが合いました。

途中の計算も出力し丁寧に確認してから提出すると見事通りました。71分時点のことで、なんとFAが取れていました。結局勘違いしていたときのコードはほぼ使いませんでした。

D問題（1）

自分が実装している間に残りの問題はすべて読まれたようです。相変わらず解かれているのがDEFのみということで、多人数で詰めたほうが良さそうなDについて議論を始めました。

とりあえず、マッチ先のパターンを回転させて平行移動だけの問題にします。どれだけ移動するかをバウンディングボックスを見ることで決めたいのですが、コインの移動によって変わってしまうのが問題です。

ここで、マッチ元のパターンも回転させることで元のバウンディングボックスの左上をそのまま使えるようにするというアイディアが出ました。実はこれは正しくなく、コインを動かして置くことで4辺すべてが変化し得るのですが、気づかずに解けているものと判断しました。

細部の詰めと実装を二人に押し付け、自分は別の問題を考えに行きました。

E問題

E問題の分割統治を改めて考えます。他の $\bmod{998244353}$ の問題も2べきを強調して書かれていたので、この書き方だから畳み込みを使うというようなことはなさそうでした。

分割統治ですから、 $(l,r)$ があったとき $m=(l+r)/2$ として、 $S[l,m)$ のsuffixと $S[m,r)$ のprefixで足すとICPC-ishとなるものを考えたいです。prefixやsuffixに含まれるI、C、Pの文字数を、前者は $(I,C,P)$ 、後者は $(i,c,p)$ と置き、関係を考えます。

まず、Iの文字数がCの文字数と等しく、それよりPの文字数が多いケースを考えます。条件は $I+i=C+c\lt P+p$ で、 $I-C=c-i$ かつ $I-P\lt p-i$ と分割できます。 $(I-C,I-P)$ のようなペアを用意してsuffixとprefixを適切にソートすれば、分割方法に関するdpの遷移が簡単にまとめられました。

$(l,r)$ に対する計算量が $O( (r-l)\log(r-l))$ なので全体では $O(|S|(\log|S|)^2)$ ですが、TLが6secもあるので間に合うでしょう。

この間にDは、先程の勘違いを修正した上で実装に入っていました。印刷して一旦離れるタイミングがあったのでPCを借り実装しました。すぐサンプルが合って、ランダムケースも手元で3secだったため自信を持って提出しました。ジャッジにはしばらく時間がかかりましたが、無事通りました。

F問題

残りで解かれているのはDFKです。Dの実装が再開されたのを横目に、F問題の考察に入りました。このあたりで昼食が配られたため、すぐ食べました。

言い換えとして、それぞれの孤を始点から終点までの有向線分とみなすのを試しました。こうすると、元のループは角がすべて直角であるようなループと対応します。線分が縦横の向きになるよう全体を45度回転しておきます。

ループになるための条件の一つとして、当然ながらちゃんと始点に戻ってくる必要があります。これは、右向きの線分の長さが左向きの線分の長さと等しいこと、上向きと下向きについても同様であることが必要十分条件です。

またもう一つ、線分から孤に直した際にスムーズに繋がっている必要があります。孤に直す際には線分の向きに対し右側に膨らませるか左側に膨らませるかで2通りあって、線分の接続が直進・右折・左折のどれであるかによって規則が異なり扱いづらいです。

4方向の線分がそれぞれ奇数個ずつあれば、1回転するだけで見事に繋げられます。偶数個ずつあれば2回転すればよいです。 $N$ は偶数なので、残りは2方向が偶数個、2方向が奇数個となるケースです。

ここで、サンプル3が見事にそのケースであることに気づきました。このケースの答えがNoであることから一般に構築できないだろうという予想が立ちます。また、実は一つ目の条件の判定がそもそも難しいので、ここで変な条件は出ないだろうというメタ読みもありました。

結局、問題は次のように書き直されました： $r$ たちを四つのグループ $L,R,U,D$ に分割し、 $\sum L=\sum R$ 、 $\sum U=\sum D$ 、 $|L|\equiv|R|\equiv|U|\equiv|D|\pmod 2$ となるようにできるか。

OpenCupで4分割を2分割2回にするアイディアを見た気がするので、その方向で考えていたところ、見事に成功しました。

$r$ たちを総和が等しい二つの「サイズ偶数の」グループに分割する方法が、 $(A,B)$ と $(X,Y)$ の2通りあるとします。ただし $(X,Y)\ne(A,B),(B,A)$ です。このとき $L=A\cap X$ 、 $R=B\cap Y$ 、 $U=A\cap Y$ 、 $D=B\cap X$ とすれば条件を満たします。逆に $A=L\sqcup U$ 等とすれば $(L,R,U,D)$ から $( (A,B),(X,Y))$ を作れるので、これが必要十分条件です。

つまり分割方法を数えるdpをすれば良いです。ホスフィンさんに考察を聞いてもらって、実装はそのまま押し付けることにしました。Dが空いたタイミングで書いてもらい、横から口出ししていました。 $(X,Y)=(B,A)$ のケースを数えてしまうようでサンプルが合いませんでしたが、単に必要な分割方法を倍にすれば対処できて、無事通りました。

D問題（2）

Dは難航しているようです。印刷されたコードを少し読みましたが、時間をかけて読む必要がありそうだったので、この時点ではそのまま任せきりにすることにし、自分はKを考え始めました。

イベントの並びをbitDPで計算し、コストは折れ線のまま管理することで解けると思いました。折れ線の並行移動、累積MIN、折れ線同士の足し算・MINが必要で、それぞれ頑張ると実装できそうです。Dが通ったらすぐ書けるよう、しばらく紙コーディングしていました。

しかし、コンテストが残り30分くらいになってもDはサンプルすら通っていませんでした。この時間からKに手を付けても両方通らず終わるだけだなと確信したため、以降はDを通すことに全力投球することにしました。

今の所少なくとも、回転後の座標を回転前の座標に復元する部分にバグがあるらしいです。書かれていたコードのロジックが理解できなかったので自分の思いついた方法を伝え、さらに結局実装を奪い取って自分で書いてしまいました。

左上の $2\times 2$ マスを見ると、縦横それぞれについて回転前の座標の増分と回転後の座標の増分の対応が取れます。ただしそういう $2\times 2$ マスが取れるとは限りません。入力の受け取り、またバウンディングボックス外の切り詰めの際に、2行・2列に満たなければ右下に伸ばしました。左上さえ揃っていれば良いのでこの拡張は問題になりません。

10分程度かけて実装するとなんとか動き、出力も正しいものが出ました。後から考えてみればそういう対応は90度回転した回数からわかり、もともとそうするコードが実装されていたはずですが、多分マジックナンバーが間違っていたのでしょう。

見つかったコインの動かし方を一つだけ出力するのではなく全部出力してみてサンプルに対し想定通りの挙動をしているか確かめる、という方法で丁寧にチェックしました。少しだけ修正すれば残りは良さそうということで提出すると、なんと一発で通りました。

10分ちょっとの残り時間は順位表を見てワイワイ話していました。

コンテスト後

解説会まで1時間弱時間があったため、ホスフィンさんと一緒にスポンサーブースを回りました。LegalForce、現LegalOn Technologiesさんのブースがあったため、3年前に頂いたUSキーボードのお礼と感想を一方的に喋ってきました。半分くらい回ったところで時間になりました。

解説ではHが中難度枠だったということに衝撃を受けました。実は自分も目を通していたのですが、不等式が大量にあることを認識した段階で諦めてしまっていました。不等式の対称性についてはhaさんのメモにそれらしいことが書いてあったものの、真面目に考えようとはしませんでした。

またEの想定解がかなり天才寄りで面白かったです。分割統治を使わない場合でも、結局I、C、Pの個数を見てBITか何かで頑張った人が多いのではないでしょうか。自分はあまり理解していませんが、後からsuzukaze_Aobayamaに聞いた解法がそういうものでした。

CでS、T、Uが出現する位置は、問題文中で「outermost」と表現されていました。自分はこれを単に「外周のマスに存在する」と解釈したのですが、実はもっと強く、四隅のみを指していたようです。

YesNoの結果は6完9位でギリギリ一桁を達成しました。企業賞はありませんでした。

すべてのプログラムを終えた後、まずスポンサーブースの残りを回り、その後はずっと懇親していました。基本的には自分から名乗って特攻していたのですが、中にはTCO Finalsの際に公開された自分の顔を覚えていて話しかけてくださった方もいて感動しました。

午後6時くらいに会場を出ました。とうの昔に会場を去った東北大の他の人々は近くのビアバーに集まっているようだったので、そちらに合流してさらに午後8時過ぎまで喋っていました。

食事 pic.twitter.com/T2vg2pHmlW
— こたつがめ (@kotatsugame_t) 2022年12月28日

現在地から東京駅までの移動を考えると、実はこの時間は予定していた新幹線に間に合うギリギリです。酔っ払った状態で急いで移動し、何とか間に合いました。新幹線ではまた爆睡していました。

日付が変わる前に家に帰り着き、JAGへ入会メールを送りました。

帰宅しました。現役最後のICPCだったらしいです。Aobayama_dropoutをご愛顧いただきありがとうございました
— こたつがめ (@kotatsugame_t) 2022年12月28日

結果

先ほども書きましたが6完9位でした。昨年の順位は8位だったため、これまで順位を単調減少させてきたのが最後の年にして失敗してしまったということになります。これは残念でした。

しかしコンテスト中の動きには満足しています。特に3人全員が2問ずつ実装していること、冷えている時間がなくコンスタントに問題を解き続けられたことが良かったと感じました。実際は冷えていないと思っていたのは自分だけかもしれません。他の二人にはDの考察・実装を押し付けてしまったので、苦しい時間が長かったかと思います。

今回のコンテスト環境に関して、コマンドラインからファイルを印刷できるのはとても便利でした。何ならモニターにかじりつかなくてもよいし書き込みも自由にできるので、これについてはオンラインでやるより快適だったかもしれません。

やはりオンサイトは非常に楽しかったです。最後の年にこのような形で大会に参加できて嬉しく思います。これまでの5年間でチームAobayama_dropoutに関わった皆様、特に自分と組んでくださったチームメイトの方々に感謝します。

kotatsugame.hatenablog.com

2023-01-16

週記（2023/01/09-2023/01/15）

01/09(月)

午後2時過ぎ起床。半から指導教員の先生が海外の先生とオンラインでミーティングをするのに同席させてもらった。

かなり辛かった。話の流れでこういうことになったはいいが、あくまで先生の専門であって自分が今勉強しているグラフ理論からは微妙に遠い。事前に頂いた資料もあまり目を通せておらず、理解度が微妙な感じになった。終了時刻が決められていないのも応えた。結局2時間程度で終了。海外の先生が退室されてから指導教員の先生と少し話し、辛うじて理解できた部分について少し質問したりした。

じゃりみちさんのゆっくり実況シリーズ「ありきたりな惑星緑化」の最終回が投稿された。このシリーズは最初から最後までほぼリアルタイムで追っていた。終盤は単調な作業がかなり続いていそうだったが、動画ではほぼ全てカットされている。駆け足だったという印象もあるものの、最後まで濃密な内容が楽しめたのは嬉しいことだった。

www.youtube.com

夜までずっと週記を書いていた。午後10時投稿。相変わらず校閲はできていない。

食事してセミナー準備。今回から平面グラフの章に入る予定で、明日のセミナーではその準備としていくつか幾何学の用語の定義をしたり性質を見たりする。直感的に明らかなことでも直感を使わず示す必要があって、その匙加減が難しい。何が言えて何は言えないのかがうまく掴めず、結局二つほど証明を完成させられなかった。準備の時間も限られているため諦めることに。

午前4時頃終了。布団に入るもうまく眠れなかった。しばらくハーメルンの更新を読んでいたら午前5時半ごろに寝落ちした。

01/10(火)

午前9時過ぎ起床。布団から出るのに30分くらいかかった。

外は雪がちらついているようだが昼からの降水確率は低め。帰りには晴れているだろうと見込んで、冬タイヤに履き替えていない原付で山に登ることにした。午前10時ちょっと前に到着。すぐ教室に向かえば間に合うところを、空腹に耐えかね購買でパンを買ってから向かった。先生も少し遅れていて、数学棟の1階で鉢合わせた。

購買にて。年明けから生協の組合員証がスマホアプリに切り替わっている。アプリ登録は全員行う必要があって、そのアプリで決済もできるため便利というわけらしい。自分はスマホにそういう機能を持たせるのを嫌っていて、以前のカードも一部のレジで使えるという話だったから決済時はそうしようと思っていた。しかしこの「一部のレジ」というのは本当に一部らしく、今日寄った購買には置いていないようだ。仕方なくスマホで決済した。

【重要】HagiCo・ミールの利用には大学生協アプリの登録が必要になります | 東北大学生協

スマホをカードの代わりにすることを嫌っている理由についての自分語りをする。自分は、自分が組合員証などのカード類を忘れる・落とす・無くす確率より、スマホの充電を切らす確率のほうが高いと見積もっている。なぜなら、カード類は自分の注意力次第でどうとでもなるのに、スマホの充電に関しては何もできないから。満タンで家を出ても切れるときは切れる。

午前10時過ぎから午後0時半までは同級生のセミナーだった。今日はラムダ計算のη-変換。Unlambdaをやっているとき、λx.fxをS(Kf)Iではなくfと書けるということでかなりお世話になったが、これこそが関数の外延性であるということは意識していなかった。η-変換のほうが弱いように感じてしまう。

昼食を買いに購買へ。昼休みも半ばなのにかなり混んでいてびっくりした。どうやらレジ待ちが長いらしい。見ると、2台あるレジのうち片方を一人が結構な時間占有していた。スマホアプリでの決済に苦労しているようだ。その人が悪いわけではなく、レジが悪いわけでもなく、アプリが悪い。いろいろ不具合があることはTLに流れてきて知っていた。

食事をとっとと腹に収めてすぐ、自分ではなく博士課程の方のセミナー。証明にグラフを持ち出す定理があるらしく、昨年末から話だけは聞いていた。今日は大量に登場した添え字を追うのに時間を使ってあまり進まなかったが、終盤、本に書いてあるものと論文に書いてあるもので定義に食い違いがあっておかしいということを発見し、指摘した。来週に持ち越し。

セミナー中に外を見たら思いっきり雪が降っていてひっくり返った。原付を押して帰らなければならないのだろうか。

午後3時過ぎに終了し、その後休憩なしで自分のセミナーを行った。今日は準備してきた量も少なく、また後述する理由で急いでいたため、1時間半で話し終えてしまった。昨日完成させるのを諦めた証明二つについては、片方は議論しているうちに思いつくことができたが、もう片方は何もわからず。自分で考えるのも苦しいためネットで誰かに尋ねたいところだ。

セミナーの終了を急いだ理由は、午後5時に閉まる山の下の購買で予約したラノベを受け取りたかったから。教室を出た時点で残り20分くらいで、歩いていては間に合わないような時間だった。幸い雪が降っているとは言え路面には積もっていなかったため原付に乗って移動。下り坂で神経をすり減らしつつ何とか閉店前に滑り込むことができた。無事受け取りに成功し、学食で食事して帰宅。

生協でラノベを20万円分くらい買ってるので、もう顔パスで注文した本が出てくる
— こたつがめ (@kotatsugame_t) 2023年1月10日

今日はまず1冊出てきたので「あと8冊あるはずですが……」と言い放ち貫禄を見せつけた
— こたつがめ (@kotatsugame_t) 2023年1月10日

実は今日はインターン先定例会の日でもあった。昨日が休日のためずれていた。会議に接続すると勉強会の発表の終わり際で、その後の質疑応答だけ1時間ほど聞いた。線形代数とニューラルネットワークの話らしい。スライドを見るだけでもかなり難解な内容だったのがわかる。そんな中でも質問を通して何かを学び取る参加者のテクニックが印象的。自分からは、ニューラルネットワークの数式表現がうまく解釈できなかったので、何かノードと矢印の図はないかと聞いた。

しばらく部屋の掃除をしていた。以前言及した家飲みの日が明日である。注文した酒類やボードゲームは無事すべて到着した。

01/11にホスフィン・たいぺーと遊ぶ。いつものように外で食事してから我が家で家飲み。そのための酒類やボードゲームをいくつかAmazonで購入した。
週記（2023/01/02-2023/01/08） - kotatsugameの日記

午後8時過ぎからCF #843 div.2。開始が10分こどふぉった。

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

A1は全探索できる。A2に15分かかった。正確には、A2で入力される文字列がaとbしか含まないということに気づくのに15分かかった。今日は難しい回か、と思ってのんびりやっていたのが馬鹿すぎる。順位表を見たらみんなBどころかCまで通っていて一気に冷や汗が出た。解法は、両端以外にaがあればそれだけを真ん中にする、なければ両端1文字とそれ以外に分ける。

Bは $a$ を元の数列全体、 $b$ を $a$ から一要素取り除いたものとして条件を満たせるかチェックする。Cは $m$ を増やすことで $n$ の下のbitから順に消していく。次に消すbitを決めると $m$ をどんな値にすればよいかがわかる。

Dは各素数を表す超頂点を作り、それと数の間に辺を張った。復元がかなり面倒。数値からインデックスを求めるあたりが辛そうと考え、最初に $a_s=a_t$ のケースを取り除いておいたら、 $a_s=a_t=1$ かつ $s\ne t$ のケースにやられてしまった。

Eは二分探索。マイナスのために使った値は次はプラスのためにしか使えない。逆も然り。

Fは苦労した。 $u=1$ のケースは何とでもなるため問題は $u=2$ 。自分は最初「 $n$ より少し小さい長方形を作り、足りない分を付け加える」という方針で解こうとしていたが、これだと例えばサンプルの $n=7$ で、 $3\times 3$ の左上と右下を消したような形を数えられない。

今何気なく使った表現「 $3\times 3$ の左上と右下を消す」が解法。つまり、 $n$ より少し大きい長方形を作って過剰な分を消せばよい。ラボの形は凸だと思ってよく、この場合の周長は元となった長方形と一致する。長方形の縦横と、その長方形が答えの元になりうる $n$ の組み合わせは、ギリギリ全探索できるくらいの個数らしい。

あとは長方形とそこから消すブロック数に対し、凸を保つような消し方の数を求める方法について。凸を保つためには四隅から消し始める必要があって、実は四隅をそれぞれ独立に考えてよい。気になるのは消し方が干渉しないかだが、もし干渉するほどたくさん消せるなら元の長方形としてより小さなサイズのものが取れるため、考慮する必要がない。

同じ理由で長方形のサイズも気にしなくてよいので、まず削るブロック数に対して消し方を数え、上で述べた全探索の際にそのテーブルを見ることにする。四隅の一つについて解き、それを多項式と見て4乗するとテーブルが作れる。消すブロック数は最大で1000にも満たないようなので、これはどちらも特に工夫のないdpなり畳み込みで行える。

1度目の提出はWAだった。そこから30分近く理由がわからずに苦しんでいたが、適当に探索範囲を増やして出しなおしたら通った。元となる長方形のサイズが $n$ の上限 $4\times 10^5$ を超え得るのを見落としていたようだ。

遅めの全完で47位。Eは二分探索の判定をよく見ると貪欲でよいようだ。さらに実は、累積和の最大から最小を引くことでも答えが求まるらしい。累積和を取った状態での操作を考えると分かった。衝撃的。

全完に2時間かかってしまった。本当はとっとと切り上げてゲーセンに行こうと考えていたが、もはやそのような時間ではない。明日家飲みの前に行くことにする。

チュウニズムデュエルが終わっていない。01/11までにあと10クレほどプレイする必要がある。
週記（2023/01/02-2023/01/08） - kotatsugameの日記

明日に備えて早く寝るべきだが、今日の深夜に新春TCB2023が終了して結果が出るということで、その時間までTLを眺めたりYouTubeを見たりしつつ起きていた。

https://techful-programming.com/user/event/3814

午後11時55分に終了し、結果は4位。1問テストケースの不備で採点対象外になるので、もしかしたらずれるかもしれない。全完者の中では結構時間がかかっているほうだった。失点は124ptで、すべてタイムボーナスを失ったことによるものである。3位は遠く、5位は近いので、ペナルティを出さなかったのはかなり偉かった。以下各問題の感想。

天邪鬼な石取ゲームは、 $\max a$ が $\sum a$ の倍より大きいなら先手がその山を選び続けることで勝てる。それ以外のケースは実は全部の石が取られ、 $\sum a$ の偶奇だけで決まるのではないかとエスパーした。変なケースが思いつかなかったので出したら通った。制約が微妙に小さいため結構怖かった。

Restricted Gridは結構難しかった。条件を式で書き眺めていたら、全部足すことで答えの $M\sum x+N\sum y$ を上から抑えられる。勝ったなガハハ！と思っていたらサンプル4が合わなかった。冷静になるとそんなピッタリにはできない。さらにしばらく式を眺めて、 $\sum y$ を全探索すると全部計算できることに気づいた。少し時間オーバーして-5pt。

Sum Mod M againは非常に難しかった。まず $i$ が固定されているとして、 $j$ を求めることを考える。これはつまり全体を $B$ で割ろうとしている。すると $Ai+C$ が $\gcd(B,M)$ の倍数という条件が出てくるが、これを満たす $i$ はある $q$ 、 $r$ と適切な範囲を動く $k$ によって $i=qk+r$ という形で表せる。この $i$ を元の式に代入することで $B$ で割ることが達成できる。今の操作は問題を $B=1$ のケースに帰着したことに相当する。

$i$ と $j$ を入れ替えてもう一度行えば $A=B=1$ にできるぞ！と思い込んだが、残念ながら $B$ を変えるときに $A$ も変わるためうまくいかない。しかし実は $B=1$ とできた時点で解けていた。 $i$ を固定すると、 $Ai+j+C$ は $Ai+L_2+C$ から $Ai+R_2+C$ までの値を取る。このうち $M$ の倍数であるものの個数は冷静になると $\lfloor(Ai+R_2+C)/M\rfloor-\lceil(Ai+L_2+C)/M\rceil+1$ と表せて、 $i$ に関する和を取るのがfloor_sumで行える。

考察が一直線には進まず、迷走していた時間が長い。86分かかったようだ。タイムボーナスはすべて溶け消えて-56pt。ここまでは日曜日のECR前にやっていた。特にこの問題が解けたのは15分くらい前と結構ギリギリだった。タイムボーナスが残っていないからあまり関係はない。以降はECR後。

初夢スコアアタックは一つ前の問題と難易度が同じなのに、非常に簡単だった。使える限り多くの魔法を使いたい。使える魔法を増やす方向で考えると計算量が抑えられないが、減らす方向で考えれば、単に使えなくなったものを消していくだけでよい。問題文を把握するのに少し時間がかかるも14分で解けた。

Worst Conjectureはもう大変。 $c$ と $T$ で2重積分する。被積分関数の形が複雑なので、それを決定できるよう $c$ と $T$ の範囲を細切れにしてそれぞれ計算する。行った工夫としては $(c,T)$ の代わりに $(c,2T-c)$ で積分したことが挙げられる。 $X$ に関する条件がこの2数の間にあることと書けて便利。

$2T-c$ の積分を外側に持ってきたのは失敗だった。 $c$ の範囲に対する期待値はサンプルに書いてあるが、これをデバッグに使えず自分で積分計算する羽目になった。しかも結構最後のほうまで条件の不等号を逆だと誤読していて計算がやり直しに。非常に苦しみながら4時間と計算用紙10ページをかけて通した。当然タイムボーナスはないので-63pt。

しばらくTLを見て午前1時過ぎ就寝。

01/11(水)

午前8時半起床。布団から出るのに30分かかった。準備して出発。

まずゲーセンでチュウニズムデュエルを終わらせにかかった。「凛として咲く花の如く」の理論値が出た。曲も譜面も好きなので結構うれしい。時間的に7クレしかできず、クリティカルが全く出なかったためデュエルは終わらなかった。昼食後にまた来る。

凛として咲く花の如く理論値 pic.twitter.com/yvDiofitpJ
— こたつがめ (@kotatsugame_t) 2023年1月11日

午前11時半前にたいぺー・ホスフィンと待ち合わせして、ホスフィンが予約してくれたフレンチの店に入った。今日はフルコース。量的にはそれほどでもないなと思っていたが、2時間かけてゆっくり出てきたので満足感はかなりあった。ツイートに記された料理の名前は説明を聴き取れなかったりして不正確である。

食事
・いろいろ温野菜の菜園風サラダ
・ソーセージ、パテ、スモークサーモンのマリネ
・パン
・きのこのポタージュ pic.twitter.com/FoyNtJhdD3
— こたつがめ (@kotatsugame_t) 2023年1月11日

・メカジキのソテー
・牛ハラミのステーキ
・デザート（ガトーショコラ、りんごとカスタードのケーキ、ムース）＋紅茶 pic.twitter.com/XiQLVaf9do
— こたつがめ (@kotatsugame_t) 2023年1月11日

どれも明らかに美味しかった。サラダは飾りのドレッシングのほかにも野菜に薄く塩味がついているようで、丁寧な作業に感動した。きのこのポタージュは一口飲めば非常に濃厚なきのこのうま味が口の中に広がって圧倒された。たまにインスタントのスープパスタを食べていて、これもきのこが美味しいなと思っていたが、やはりモノが違う。牛ハラミのステーキは横の橙色のソースがわさびのソースだった。結構辛みが強く、わさび醤油が好きな自分にとっては非常に嬉しかった。

クノール®スープDELI® ポルチーニ香るきのこのクリームスープパスタ（容器入）｜商品｜味の素株式会社

食後、二人がドンキに買い出しに行っている間にゲーセンでチュウニズムデュエルを終わらせた。追加で2クレ使った。TiamaT F:minorはラストまでかなり上手かったのに、つまらないアタックやミスを出してSSS+もフルコンも逃してしまった。

あああああアウトロで切ったあああああ pic.twitter.com/gSXsPCi32C
— こたつがめ (@kotatsugame_t) 2023年1月11日

帰宅して飲酒開始。

飲酒します pic.twitter.com/k5AGKMEW7I
— こたつがめ (@kotatsugame_t) 2023年1月11日

購入したボードゲームをプレイした。最初は「ギャンブラー×ギャンブル！」。結構面白かった。各プレイヤーが0または1のカードを場に出し、その総和が当たりの数字になっているプレイヤーがコインを獲得する。獲得したコインで自分の当たりの数字を増やしたりしつつ勝利条件を満たすゲーム。カードを出す際には実際はもうちょっと手順があって、考えようと思えばいろいろ考えられる。出すときにブラフで何か言うだけでもかなり戦略ゲームっぽくなって楽しかった。

このゲームは3人または4人用とされていたが、3人だとゲームの展開が制限されると感じた。本来はゲームが進むにつれ手持ちのカードに2や3が増えるようだ。しかし3人でプレイしていると、それらのカードを手持ちに入れるメリットはあまりなさそう。似通った展開になるのを避けるため、最初から2を持ってみたり、少しルールを変えて何度かプレイした。

次に「タギロン」。個人的にこれは大当たりだった。数字と色の書かれたタイルが20枚あって、3人プレイだと一人5枚配った後、互いに質問し合って残りの5枚を特定するというゲームになる。残りの5枚に対しては何も質問できないため相手二人が持つタイルをすべて特定する必要があって、結果として誰か一人に質問が集中してもそれだけでは勝敗は決まらない。このバランスの取り方に感動した。

質問は、場にある質問カードを一つずつ消費しそこに書かれた内容を聞くことで行われる。数字に関する質問より色に関する質問のほうが少なく、それを一人にほとんどぶつけた結果もう一人の色がなかなかわからず苦労するという場面もあった。

購入したボードゲームは3種類で、最後は「ito」。1から100までの数字を一つずつ持ち、その大小をお題に沿って言葉で表現することで、大小関係がどうなっているのかを特定するゲーム。プレイ人数10人までのところを3人でプレイしたためか、前二つに比べるとちょっと微妙という感想。もしかしたら単にお題が合わなかっただけかもしれない。95と96の順番を当てた回があって、かなり嬉しかった。

一通りプレイしてからはいつものようにおすすめ動画（MAD）を見たりまたボードゲームをプレイしたりしていた。今日見たMADで印象深いのは以下の三つ。

www.nicovideo.jp

「背中の傷は剣士の恥ィ」。これは自分が紹介したやつ。最近結構な頻度で見ている。何もかもが好き。「ウソップはこの島に置いていく！帝京魂！」のセリフが特に意味不明で良い。

www.nicovideo.jp

「みゃー姉が死んだ回」。原作では死んでいないらしい。ホスフィンによる各シーンの解説があって、構成の巧みさに驚かされた。RubikunさんのTwitterアイコンになっているキャラはこの作品由来らしく、アニメではアイコンで見たことのない表情も多く違和感がかなりあった。

www.nicovideo.jp

「デスノートで人が死んだ回」。出オチ。先ほどの作品とさらにその元作品「おジャ魔女どれみで人が死んだ回」を見た直後だったため、落差で笑いが止まらなかった。

午前4時頃にラーメンを食べに行った。腹が減っていると思ったものの、食べたら食べたで少し気持ち悪くなってしまった。その後解散。正確には、たいぺーとは帰り道で別れ、ホスフィンとは帰宅して一休みした後別れた。

今日はキレートレモンやお茶をたくさん用意し積極的に飲むようにしたため、このように全員で外に出るような元気を残すことができた。今後も心掛けたい。用意したお酒のうちではカルーアミルクを結構な量飲み残してしまった。ミルク系の甘いお酒は好きだがだからと言ってたくさん飲めるわけでもないようだ。

47度のジンが一瓶空いたのはびっくりした。このジンをストレートで口に含んでみたところ、よく小説などで目にする「喉が焼けるような」という感覚を得ることができた。そんな感じだからきっと飲み切れないと思っていたのに、適当にジュースと混ぜると苦みがなく非常に飲みやすいお酒になってどんどん杯が進んだ。

少し部屋の掃除をして午前6時くらいに布団に入った。何かスマホを触ろうとした記憶はあるが、すぐ寝落ちした。

01/12(木)

午後3時起床。シャワーを浴びて準備し、大学に向かった。TA。

年が明けて初めての講義となる。内容は昨年最後の講義で行われた発表の続きからだが、その時特に難しいことをやったわけでもないため復習などはなかった。

30分次の人の発表を行ったところで時間になった。これで今年の講義は終わり。
週記（2022/12/19-2022/12/25） - kotatsugameの日記

超多面体の話。特に $n$ 次元の特別な超多面体に含まれる $k$ 次元単体の個数を数え上げるのがメインだった。 $n$ と $k$ に関する漸化式を立てて、それを解く。解くと言っても答えは教科書に載っているため、適当に帰納法で示すだけになる。

変数が二つあって混乱しているようだったので、その周りでいくつか指摘したり助言したりした。シンプルに $n$ だけ見ても解けるし、変わり種として $n+k$ についての帰納法を使ってもよい。そもそも前者がおぼつかない様子だったので、後者については特に何も言わなかった。

午後6時過ぎに終了し学食に向かった。5限終了直後でもないのに3台稼働しているレジにそれぞれ10人弱並んでいて驚愕。一体何をしているのかとよく見たら、現金払いが多いらしい。生協のアプリ登録に失敗した人々だろうか。またアプリを用意していた自分も決済バーコードの読み取りに微妙に時間がかかって、まんまとレジの詰まりに寄与してしまった。どうしようもない。

午後7時帰宅。メールを確認したらABC277の賞金が届いていた。アマギフ60000円分だった。この回は賞金がかなり高額な回だったらしい。額面がメール文面に書いていなかったためびっくりした。

生協のアプリについては今もTLにそこそこ愚痴が流れてくる。そんなツイートの一つに以下のようなリプライがついていた。これが本当なら少しだけ納得も同情もできる。不便になったのは覆しようのない事実のため、もうちょっと何とかならなかったのかとは思うが。

失礼します。大学生協で学生理事をしていたことがある者です。
もはや学内から人がいなくなり、生協の経営が悪化しました。これまでの野村総研のPOSレジは保守費用が高額だったので、簡易なレジを導入することになりました。そのため、電子マネーがカードからスマホアプリになりました。
— えぐっちー (@soki124) 2023年1月12日

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

01/13(金)

午後1時45分起床。15分後から1on1。

結局年末年始は何もしなかった。その間に自分ができるタスクがいくつか用意されたらしく、今日はその説明。まず一つ、昨年後半に携わっていたコードで大きなエクセルシートを処理すると実行が終わらなくなってしまうことの解決。二つ、昨年末に話題に上がったツールを本格的に使い始めるための下調べ。前者がかなり難題で、もっぱらそれを解決する方針決めに時間を使い2時間ほどのミーティングとなった。

大きなシートといっても真っ当にデータが多いわけではない。手作業のミスによって右・下方向限界ギリギリのセルに値が入っているようなシートが存在して、それを処理できないらしい。読み込みにはopenpyxlというライブラリを使用していて、そのデータにすること自体までは特に時間もかからない。なぜなら、値が入っているセルのみをdictとして保持しているだけだから。

しかしそこからうかつに行を取得したり列を取得したりした瞬間、一番端のセルに合わせてその間の値が入っていないセルも全部新たに作成してしまうらしい。この一番端というのは取得した行・列の一番端という意味ではなく、シート全体の一番端という意味である。つまり、セル $(1048576,16384)$ に値が入っていれば、すべての列が高さ1048576になるし、すべての行が幅16384になる。

こういう大きなシートでは、端にあるセルは単に無視することになった。しかしそれを実装するだけでも値が入っているセルだけを一つ一つ見ていく必要があって大変。そういうことをするメソッドは用意されていないようだったため、外から触られることを想定されていなさそうな_cellという変数を直接見ることになった。

たいぺーが水曜日に空けたジンの瓶を引き取りに来た。可愛いので取っておきたいらしい。洗って乾かしておいたのを引き渡し、ついでにその他の瓶をゴミ捨て場に持っていく手伝いをしてもらった。キレートレモンの空き瓶が10本あって一人では面倒だった。

午後4時40分からサークルバチャ。5問目はかなり最近の問題だから覚えていて、6問目は条件をいくつか集めたら通って、7問目は「二つの要素が同じタイミングで操作されると以降どちらが先に並ぶかは半々」というクリティカルな考察がスムーズに出てきた。結果35分で全完し、Estimated　Performanceが5029と見たことのない数字になった。

https://kenkoooo.com/atcoder/#/contest/show/57415d67-4fc2-4e97-a222-3e24052aaecd

解説をチェックしたりして時間を過ごし、バチャ終了後に少し感想戦をして解散。

日付が変わるまで今日期限のレポートと格闘していた。昨年末に受講した集中講義「理論言語学研究演習I」の課題である。最近の自然言語処理はニューラルネットでポンという感じで、言語学的知見が活かされているとは言えないとのこと。活かすにはどうすればよいか意見を書けという課題だった。

自分はまず、LSTMとAttentionという講義で扱われたニューラルネットのブレークスルーを達成した仕組みについて元の論文を当たり、本当に言語学的知見が活かされていないのか調べた。長距離依存という用語が出てきているのだし何かあるだろうと思ったのだ。しかし事実として何もなかったため目論見が崩壊。今更レポートの方針を変えるような時間もなく、適当なことをモゴモゴ書いてお茶を濁した。しかも提出が数秒間に合わなかった。まあこのくらいは十分許してもらえるはず。

その後はずっとラノベを読んでいた。午前3時頃「クラスで2番目に可愛い女の子と友だちになった」3巻を読了。ダダ甘。ついにヒロインたちとクラスでも関わるようになり、見せつけるような感じになって読んでいて非常にニヤニヤできた。タイトルにもなっているヒロインと恋人同士になったにも関わらず、結構な頻度でその友達を含む男1女3で行動していてこれも好きな展開。しかし主人公は一途なので、ちゃんと恋人を特別扱いしていた。偉い。

別のラノベに手を出したが、急激な眠気に襲われ午前5時くらいに寝落ちした。

01/14(土)

午後4時頃に冷凍弁当を受け取った。その前後1時間ほどは起きてスマホを触っていた記憶がある。二度寝した後、午後6時起床。

ラノベを読んで過ごし、午後9時からARC153に出た。

AtCoder Regular Contest 153 - AtCoder

Aは $(S_1,S_3,S_4,S_5,S_7,S_8)$ を辞書順に探索すればよい。6重ループを書いた。

Bは操作を把握した瞬間「全体をいくらかシフトして180度回転したもの」になるとの直感を得て、実際そうと確認できたところまでは順調だったものの、実装方針にかなり苦しんだ。何を計算すれば盤面の状態を表現できるのかわからない。最終的にはマス $(1,1)$ の行き先を追った。

Cは実装が面倒だと思ったら整理するうちにどんどんシンプルになっていった。最初の考察として、 $i\lt j$ について $(A_i,A_j)=(-1,+1)$ だと必ず $A_ix_i+A_jx_j\ge j-i$ になり、 $(A_i,A_j)=(+1,-1)$ だと $A_ix_i+A_jx_j\le-(j-i)$ になるというものがある。つまり、どちらかのペアだけで $A$ の要素をすべて使い切れた場合、条件を満たす $x$ は存在しない。そうでない場合を考えたい。

先ほどのような $i\lt j$ によって $(\pm 1,\mp 1)$ のペアを作った後、まだ $A$ が余っていればそれを使って調整、余っていなければ $(+1,-1)$ のペアと $(-1,+1)$ のペアを使って調整すればよさそう。ペアを適当に組むと考えにくいため、左からstackを用いる方法で固定した。これだと2種類のペアが固まって現れるため調整しやすい。

$A$ が余っている場合は簡単。例えば余っている要素で最も左にあるもの $A_j$ を選ぶと、ペアの作り方からそれより左はそこだけでペアが完結しているため、 $x_1\dots x_j$ から一気に $X\gt 0$ を引くことで、 $x$ が狭義単調増加であるという条件を満たしたまま $\sum_i A_ix_i$ から $A_jX$ を引くことができる。最も右にあるものを選んでも同様。最初に $x_i=i$ と決めておき、 $X=\left|\sum_i A_ix_i\right|$ としてどちらかを選べばうまくいく。

$A$ が余っていない場合も最初に $x_i=i$ としてみた。 $X=\sum_i A_ix_i$ が正だった場合のことを考える。 $(A_i,A_j)=(+1,-1)$ というペアを探して、 $x_j-x_i$ を今より $X$ だけ大きくすることで調整可能。ただし大きくしたときに他のペアと干渉するとまずい。

区間 $(i,j)$ が交差しないペアなら適切にずらせばよい。交差する場合、ペアの作り方から完全に内側にあるか、完全に外側にある。内側は関係ないため無視。外側はどうしようもないが、そもそも包含関係で最も外側にあるペアを選べばよい。復元はちょっと面倒だった。ペアに対して $x_j-x_i$ がいくつになるべきかという値を管理し、左の要素から順番にペアの相方と一緒に決めていった。

D。 $f(A_i+x)$ は $f(A_i)+f(x)$ から繰り上がりが起こった回数の9倍を引いた値となっている。また、 $A_i+x$ の計算時に $10^k$ の桁で繰り上がりが起こることと $(A_i\bmod{10^k})+(x\bmod{10^k})\ge 10^k$ であることが同値。さらに $x\ge 10^9$ のとき $x\leftarrow x\bmod{10^9}$ としたほうが得だと示せたため、繰り上がりの起こる桁は $10^0\dots 10^8$ のみだと考えてよい。

よって $x$ を決めるごとに9回の二分探索で $\sum_i f(A_i+x)$ が求められるようになった。 $x$ としては、ある $i$ に対して $A_i+x$ の下数桁を0にする最小の値だけが候補になると考えたが、証明できない。とりあえず書いてみたらサンプルは合ったものの、出したら当然のように落ちた。

$x$ の下5桁を全探索し、上4桁はデータ構造で決めるという方法を考えていたら、頑張ればできることに気づいた。こうやって別々に考えるとき問題になるのは下の桁からの繰り上がりが上の桁の繰り上がりに関係するケース。例えばサンプル4なら下5桁が46847以上のとき、そうでない場合に比べて上4桁が「8で終わる」「68で終わる」「468で終わる」「8468で終わる」ものそれぞれに対し繰り上がりが1回ずつ追加される。

上4桁を逆順に並べてインデックスとすると、これは区間加算で対応できる。例えば「68で終わる」数はインデックス $[8600,8700)$ に対応する。下5桁を昇順に試しながらこういう更新をしていけば答えが出る。逆向きにしたり68や468といった繰り上がり直前の値を求めるところで頭を壊してしまい、残念ながら5分ほど間に合わなかった。

結果は3完120位。今回は画面録画に加えマイクに向かって喋りながらコンテストに出ていたのだが、結果がひどいため動画データは即座に消去した。コードゴルフはAのみ。99999を足すと $S_1S_3S_4S_5S_7S_8$ という6桁の数が得られるため、適切に数字をコピーして求める数を作るという解法。Vimで実装した。

ずっとラノベを読んでいた。午前5時に「黄金の経験値」を読了。やはり面白かった。以下、微妙に書籍の先のネタバレを含む感想。

なろう版からの大きな修正として、ブラン視点がすっかりカットされていた。これは個人的には読みやすくなって良かったと思う。物語が軌道に乗る前から複数の、それも独立しているように見えた視点があると、それはほとんど別作品を並行して読んでいるのと変わらなくて話の進みが遅くなりちょっと辛い。

なろう版を読み主人公レアのキャラクター性を知っている状態で最初から読むと、ちょくちょくあったそれらしい描写を見つけることができて非常に楽しかった。レアのキャラクター性というのは、自分の捉え方ではわがままだったり、肝心なところでポンコツだったりというもの。この主人公、いかにも魔王然としたビジュアル・行動なのに性格にはそういうところがあって、そのギャップが可愛らしい。

また作品の設定も改めて上手いなと思った。PCとNPCの違いは「システムメッセージを受け取れるかどうか」のみであると最初に明確に説明され、以降の設定はすべてここに絡んでいる。例えばNPCがリスポーンできないのは、リスポーン用のシステムメッセージが受け取れないから、だろう。これが他キャラに「使役」されると自動的にリスポーンできるため、NPCも不死身になる。

別のラノベを読んで午前9時前に就寝。

01/15(日)

午後6時起床。食事してしばらく日記を書き、午後9時からコンテストに参加した。

今日は午後9時からABC285があり、午後9時5分からCF #844 combinedがあった。両方参加した。

AtCoder Beginner Contest 285 - AtCoder

Dashboard - Codeforces Round #844 (Div. 1 + Div. 2, based on VK Cup 2022 - Elimination Round) - Codeforces

まずABC。Aはよい。Bは $i$ ごとに $l$ をインクリメントしながらチェックすると高速。Cは適当にやれば合う。Dはよくわからなかったが、雰囲気から $S_i-T_i$ 辺にループがあるかどうかで判定できるだろうと思った。

Dの実装中にCFが始まってしまったが、A問題のページ読み込みに時間がかかっていたのでこれ幸いと書き上げた。結局ABCは4完の状態でCFへ。

Aは上方向の移動は必ず必要なので、それを無視して平面の問題として解く。床・天井を表す長方形のどれかの辺にタッチしつつ2点間を移動することになり、どの辺にタッチするか全部試せばよい。

Bは人数を全探索する。 $k$ 人だとすれば、 $a$ が昇順に並んでいるとして $a_k\le k-1$ かつ $a_{k+1}\gt k$ が必要。合わせるのに少し手間取った。

Cは何種類の文字を使うか全探索。 $k$ 種類だとすれば $k\mid n$ が必要で、各文字は $n/k$ 回ずつ使う。元の文字列における出現回数が多い順から $k$ 個使うことにして調整すればよい。復元が面倒。

Dは平方数になる最小のインデックスを $i$ とすると、適当な $x$ 、 $t$ によって $a_i+x=t^2$ と表せることになる。このときもし $j\gt i$ なる $j$ について $a_j+x$ も平方数となるなら、ある $d\gt 0$ が存在して $a_j+x=(t+d)^2$ 。展開して $t^2$ を先ほどの式で置き換えると $a_j-a_i=d(2t+d)$ となる。

すべての $j\gt i$ に対して $t$ の候補を求め重複を数えると、 $a_i+x$ とともにいくつ平方数にできるかがわかる。 $t^2\ge a_i$ が必要なことに注意。これを $i$ を全探索して行う。 $O(n^2)$ 回10⁹オーダーの値の約数を列挙するのは十分間に合う。

Eは面倒。覆う面積の最大値なんて簡単にわかりそうもない。自明な上界としてもともと覆われていた面積があって、実はこれが達成できるのでは？と考えたら達成できた。まず高さ2の長方形だけ考えて、覆う面積を変えないようにしつつ重ならないように変化させる。長方形を一つずつ追加することを考え、追加の際完全に覆うものは取り除き、他と重ならないよう縮めるという方法で行える。

残りは高さ1の長方形で、上の行と下の行それぞれ独立に先ほどの操作をすればよい。長方形を取り除く際、それが高さ2だった場合高さ1に縮めるという処理に置き換わる。面倒に見えて、同じことを3回やるだけなので実装は案外簡単だった。入出力が閉区間なのに注意。サンプル1が強いので適当に投げてもペナになりにくい。

ここまで1時間で、現在20位台。あらかじめこの辺りでABCに戻ろうと思っていたため、Fを頭に入れてからABCのEに戻った。

Eは曜日1を休日と固定してよい。休日1日とそれに続く平日何日かをまとめて生産量を計算し、それを組み合わせる遷移でdpした。

Fはかなり苦労した。結論から言えば、区間 $[l,r]$ が昇順に並んでいること、区間 $[1,l)$ と $(r,N]$ に $S_l$ より大かつ $S_r$ より小な文字が存在しないことが条件となる。セグ木にいろいろ乗せるとできる。具体的には、区間の両端の文字、区間にどんな文字があるかのデータ、昇順に並んでいるかどうか。

焦っていたら条件列挙も実装もミスしまくり、5ペナの末コンテスト終了4分前に通った。うっかりABCに30分弱も使ってしまったがCFに戻る。

Fは括弧列をいつもの累積和に直すと、 $x$ を取り除き、その位置に確率 $p$ に応じて $x,x\pm 1,x$ を挿入するという操作になる。これを3分木みたいに見ると状態がまとめられるのではないかと考えた。ノード $x$ があって、それ以下の部分木で $k$ 回操作するという場合、まず1回操作してノード $x,x\pm 1,x$ を作り、それらで残り $k-1$ 回操作するということになる。 $k$ を固定する必要があるため特に畳み込みにはならない。

ノードを選択する確率が計算できず困ってしまったが、冷静になると操作方法に依らず $i$ 回目の操作では $\frac 1{2i-1}$ となる。これを最後に掛けるだけでよい。

フレンド順位表を見てH1に進んだ。 $k=0$ は単なる包除原理でよい。 $k=1$ もシグナルのバウンディングボックスのサイズを決め打ち、シグナルを表示するために少なくとも1マス消灯させる必要のある領域を調べてこれまた包除原理を行うと求まる。しかし $k=2$ がどうにもならなかった。

6完29位で2841→2887(+46)。昨年秋にドカンと下げたのを多少は取り戻せただろうか。点数の差がかなり詰まっていたので、Fをもう少し速く解けるだけでも順位はそこそこ変わったようだ。この順位帯だとレート変動も大きく変わる。途中でABCに戻ったのは、やる前から明らかだったことだが悪影響しかなかった。

後悔しているかは微妙なところ。なんだかんだ言ってCFのレートは結構上がったし、ABCも250位でそこまでみすぼらしい順位というわけではなかったから。ただしABCに無理して参加した目的であるコードゴルフ的には、もう全然ダメだった。以下はそのコードゴルフの話。

Aは $2a\le b\le 2a+1$ という条件を見て縮まないなあと言っていたが、 $a=\lfloor b/2\rfloor$ でよい。明らかにdc。Bは愚直に書くとRubyもPerlも間に合わないところ、Perlで文字列XORをした後ヌル文字を探す方法だとかなり高速になった。その周りをかなり縮められて負け。Cは自分が見たときにはすでにコードゴルフされきっていて、言語を変えても縮まなかった。DはAWKでこれも大敗。以降は手付かず。

時系列は前後するが、CFの終了直後にABC-Gをupsolveした。結構素早く解けたとは言え10分ちょっとかかっているから、コンテスト中にGに進んでも間に合わなかっただろう。

そのまま二部マッチングにすると2を使い切るという条件がうまく表現できなかったため、頂点を倍加してみる。すべての2を使うようなマッチングが存在すればよいと考えた。ここは注意が必要で、 $1\times 2$ のタイルを置く際は覆う2マスを倍加したものが互いにペアになっていてほしいのに、そうでない可能性がある。

しかしこれも適切に修正できそう。そういう食い違ったペアを辿っていって、もし途中で途切れたらそこから遡って修正していけるし、サイクルができたら偶閉路だから全体を一気にずらせばよい。出したら通った。Nyaanさんのユーザ解説が同じことを言っている。

昼間までずっと日記を書いていた。合間にラノベを2冊読了。

1冊目は「ガリ勉くんと裏アカさん」。クラスのアイドルであるヒロインが裏垢女子であることに気づいて……という導入。しかしむしろ裏垢云々以外の部分が面白い。特に主人公のキャラクターが好み。自分の中に一本芯があって、いろんなことを自分には必要ない・関係ないとして排除するというかなり極端なものだが、自分にとっては望ましいものだった。

2冊目は「迷子になっていた幼女を助けたら、お隣に住む美少女留学生が家に遊びに来るようになった件について」2巻。1巻を読んでから10か月、2巻が出てから6か月くらい経っているが、昨年末に出た3巻にかなり好みのシーンがありそうだったため今更読むことにした。周囲の人間の行動が主人公にとってかなり都合が良いと感じるものの、それ以外の部分は良い。日記を読み返すと1巻を読んだ時はネガティブな印象を抱いていたらしく、それを忘れ去っていたのも良い方向に作用しただろう。

正午就寝。

2023-01-09

週記（2023/01/02-2023/01/08）

01/02(月)

午前11時ごろに起こされた。多少の二日酔いで軽い気持ち悪さがあるが、今日は昼から中華料理を食べに行くらしい。

幸い、車に乗っていても食事しても気分が悪くなることはなかった。ここでもコーンスープを頼んだ。かなりコーンポタージュに近い。

pic.twitter.com/6KR0EOLz7i
— こたつがめ (@kotatsugame_t) 2023年1月2日

百貨店に寄って帰宅。

夕食までは麻雀をしていた。この年末年始は自分の他に二人実家に来ていたため、父を加えるとちょうど四人になる。この二人というのは、片方は姉で、もう片方は……詳しく説明する理由も権利もないため、名言は避けておこう。

夕食は午後6時ごろだった。食後、先ほど述べた二人が帰るので見送った。

先週の週記を書き始めたが集中力がない。なろうから「剣聖と大賢者の正体が、落第貴族と呼ばれる俺な件について～しょうがないから守護神してるけど、さっさと変わってほしい暗躍学院ライフ～」を読了。

https://ncode.syosetu.com/n8008hz/

正体を隠す方法として、完全に影に隠れているのも好きだが、こうして複数の人間を演じるのも好き。最近投稿が始まった作品なのでこれからに期待。複数の人間を演じると言えば「セブンキャストのひきこもり魔術王」というラノベを思い出す。こちらは一人七役。設定がかなり好みで、今でも時たま思い出してはニヤニヤしている。

日付が変わる直前に週記を投稿した。せっかくの年明け一発目なのに時間に追われすぎて大したことが書けず、残念。できれば加筆したいものだが、校閲にすら手が回っていない以上実現可能性は低そう。

その週記の中で、2年前に読んだ本「〔少女庭国〕」に言及した。記憶が曖昧なので念の為確認しておこうとしたが、本棚を漁っても見つからない。レーベルに共通して本の背が少し高いので、見落としたということはなさそう。よくよく思い返してみるとたいぺーに貸した記憶があって、聞いてみたらどうやら返し忘れていたようだ。思い出せて良かった。

入浴し、午前1時半くらいからDMOJのコンテストに出た。明日の午後2時までなのでギリギリ。しかしここにコンテストの感想を書けるという利点もある。

DMOPC '22 December Contest - DMOJ: Modern Online Judge

P1は、 $N$ または $M$ が偶数の場合、相手が塗ったマスの点対称の位置を塗れば必ず半々になりそう。ヒカルの碁で見たことのある戦法だ。両方奇数なら中央のマスの分先手が1増えるな、と思って提出したらWA。

考え直してみると、中央に壁を作る感じで塗れば、先手は後手より1行または1列まるまる多く獲得できる。行と列のどちらであるかは後手が選べる。これで通った。

P2はかなり面倒。順列をサイクルに分解してから考えた。連結成分数は、サイクルの頂点全部が選ばれたら1減り、そうでない場合は選ばれた頂点だけ見たときの連結成分の数に分裂する。選ばれた頂点と選ばれていない頂点を結ぶ辺を、差分更新で数えることで求められた。

P3は非常に難しかった。答えを $H$ とし、 $H-h_i$ を1と2で埋め、1とそれより右の2をうまくペアにして全部使い切ることを考える。

もし $H$ と $h_N$ の偶奇が異なれば $i=N$ として操作しなければならないがこれは不可能。よって $H$ の偶奇が決まり、同時に必ず一度は1インクリメントする必要のある要素もわかる。そういう要素を右から順に見て行って、本当にペアが作れるかをチェックした。右に2がなければ $H\leftarrow H+2$ として無理やり作り出す。

さらに $NH-\sum_i h_i$ が3の倍数になるように $H$ を調整しておく。 $N$ が3の倍数だと不可能なケースも生じる。後は $H$ と $\sum_i h_i$ からわかる操作回数の分だけ、左から優先的に1で埋めていけばよさそう。

残りは1と2が入り混じる箇所でペアを作れず破綻するケースのみが問題。そのような位置を二分探索で求め、破綻するかどうかをチェックする式を作った。なかなか複雑だが $H$ の一次式になったので、この式を満たすくらい大きな $H$ が簡単に得られる。それをもとに $H$ を再調整すればよい。

ここまでも結構な回数のWAを重ねてきたが、最後のWAが一番衝撃的だった。最初の処理で1だけインクリメントする要素をチェックするとき、それとペアになる2インクリメントするインデックスも適当に固定していた。そのほうが後から操作回数などが扱いやすいから。しかし、この固定するペアも慎重に決めなければならないらしい。右のほうから貪欲だと落ちて、左のほうから貪欲だと通った。

すでに残り1時間しかなくかなり焦っていた。幸いP4はスムーズに解けた。解の構造を考えると、まず値札を動かさずに購入する商品を決め、その後一番高い値札を一番安い使っていない値札に付け替えるのを高々 $K$ 回行うことになる。値札を安い順にソートしておくと、この操作で使っていない値札が安い方から使われるため、ある位置が存在して「それより安い値札はすべて使われている」「それより高い値札で使っているものは付け替えていない」が満たされる。

この位置を全探索し、さらにいくつ付け替えたかも全探索する。付け替えた数が $K$ 未満なら、固定した位置より右側にはもう使った値札はないとしてよい。あったとすると、適当に付け替えたり、あるいは位置をずらすことでそのケースを考慮できる。従ってこのケースでは、右側から価値の高い順に付け替えた数だけ貪欲に取ることができる。左側は $O(NK)$ のdpで全部計算可能。

ちょうど $K$ 個付け替えた場合は、右側から値札を $K$ 個動かした後、余った金額でさらに品物を購入する可能性がある。 $K$ 個までタダにできるとした金額に関するdpを行いたいが、状態 $O(NC)$ で遷移がそれぞれ $O(N)$ となり当然不可能。しかしタダにするのは高いほうから $K$ 個なので、どの品物までで $K$ 個の権利を使い切るか全探索し、品物は価値を見て貪欲に取るという方法で状態 $O(C)$ に落とせる。これで間に合う。

残り20分ちょっとでP5とP6の部分点をかき集めた。P5は0を1にする以外値を増やす手段がないことに注意しながら値の大小に関するチェックをし、さらに0を1にするために必要な1をその左側から抽出できるか調べれば1行のケースは通る。P6は始点と周期を全探索する愚直で部分点1。部分点2は、周期を調べるときに探す文字列自体が周期的だったらスキップするという枝刈りを入れたら通った。計算量解析はよくわかっていない。

残り数分でP5がフローではないかと疑ったものの、コンテスト後にしばらくやっても通らなかった。450点。順位表を見ると、思ったよりP4が解かれておらず、代わりにP5とP6がたくさん通っていた。P6はrun列挙というやつだろうか。コンテスト中も頭を過ったが性質を知らないため手が出なかった。

それからラノベを1作読了。「あたしは星間国家の英雄騎士！」。「俺は星間国家の悪徳領主！」の外伝。モブ視点で本編主人公が語られるシーンは楽しめたが、それはごく一部にしかない。当然外伝主人公の話が多く、そちらにはあまり惹かれなかった。

午前8時過ぎ就寝。

01/03(火)

午後5時起床。

昨日参加したDMOJのコンテスト期間が終了していた。最終順位は9位で、レートは2854→2897(+43)。

夕食を食べた後、少しだけ買い物に行って、帰ってきてからはこたつに入ってラノベを読んでいた。テレビの音声で集中できず終いには眠くなってくる始末。よっぽど深夜のコンテストまで寝て過ごそうかと思ったが、スマホを弄っていたらそのタイミングすら逃してしまった。

入浴し、午後11時くらいに軽食をお願いしたところ、お雑煮と焼鯛が出てきた。思ったよりガッツリ食事して半からCF。今日はHello 2023。

Dashboard - Hello 2023 - Codeforces

Aは正規表現で書くと/R.*L/にマッチするのが条件、に見えて実は/RL/でよい。文字列がLのみまたはRのみの場合だけ不可能。

Bは、とりあえず $n$ が偶数のケースは $+1,-1,+1,-1,\dots$ とすることで構築できる。サンプルを見た感じ $n$ が奇数のケースは不可能だろう、という気持ちになったが、念のため証明しようとしたら構築できてしまった。まずすべての $i$ について $s_i=s_{i+2}$ であることがわかる。よって数列が $a,b,a,b,\dots$ とおけて、 $a+b=\lceil n/2\rceil\times a+\lfloor n/2\rfloor\times b$ が条件になり、 $n\ne 3$ なら $a,b\ne 0$ なる解が存在する。

Cはちょっと面白い。条件が $\dots+a_m\le 0$ と $a_{m+1}+\dots\ge 0$ で表現できて、左右それぞれ似た感じに解ける。例えば前者については、 $m$ 項目から左に値をどんどん足していって、どこかで正になったら値が一番大きなものの符号を反転するというのを繰り返せばよい。値の取得は優先度付きキューで行った。

Dは言われたことを丁寧に実装するだけ。 $x\lt b_i$ なる $i$ を含まないように区間を取って操作する。 $b_i$ が大きなほうから見て、含められない $i$ はsetで管理した。最初から $a_i=b_i$ であるような $i$ に注意する。

Eは面白かった。求めたいのは強連結成分であって成分外からの入次数が0なもの。トーナメントグラフをSCCするとパスグラフになるので、その始点と言ってもよい。出次数で降順ソートするとSCCと同じ順番で並ぶことに素早く気づけたのがよかった。これはクエリ $n$ 回で求まる。どこまでが始点の強連結成分になるかは、さらにクエリを $n-1$ 回使って調べた。

Fはサイズが偶数の部分木を全部0にできる。これを元にした自明な木dpで判定が行え、それを丁寧に復元する。遷移はXOR畳み込みで、愚直に $32\times 32$ 回計算したがかなり高速だった。

Gはエスパーした。三角形を適当な辺を下にして置くと、上から一つ、三つ、五つ、……の三角形が一つの行をなし、積み重なっているように見える。各行には上下方向の辺がいくつかあって、例えばこの辺がすべて同じ向きだと、明らかにその行を境に行き来できなくなってしまう。よって、どの辺を下にしておいた時の行を見ても、上下方向の辺の向きはどこかで食い違っている必要がある。

これは必要条件だが、実は十分条件でもあるのではないかと考えた。当然一般には十分ではないものの、今回の状況から最小手数で達成すれば実際に強連結になるらしい。出したら通ってびっくりした。以下では証明を考えず、単に最小手数を求める。

まず三つの $s$ の末尾が等しければOK。そうでない場合、適当に回したり反転することで $s_1$ 、 $s_2$ の末尾を1に、 $s_3$ の末尾を0にできる。いちばん外側の辺の状況をイラストと合わせたということ。このとき左下向きの行は両端の辺の向きが異なるため、考えるべき行が水平のものと右下向きのものの二つに絞られる。

基本的に1辺の向きを変えたら条件を達成した行が一つ増えるが、辺を共有している行があった場合はそこを変えることで一気に二つ増やせる。後者をできるだけ行うと手数が最小になる。条件を満たしていない行の検出はインデックスを丁寧に考えると簡単な条件になる。辺を共有しているかの判定はもともと簡単。

Hはラウンド2回を一気に行うことでサイズ $n$ の問題をサイズ $n/4$ の問題に帰着できそうに見えたが、それでも全然間に合っていない。

7完20位でかなり良かった。レートは2705→2841(+136)。Dはおそらくバリカンで髪の毛を刈る操作を表していて、昔それをchminと言っていたのを思い出した。Eはソートした列をどこかで切ったときに末尾のほうから先頭のほうに向かう辺があるかどうかが末尾側の出次数の和を見ることで判定でき、クエリ回数が $n$ になるらしい。

CFの問題言い当ててしまったな https://t.co/PvvwXR1zW9
— こたつがめ (@kotatsugame_t) 2023年1月3日

システスを見届けた後はラノベの続きを読んでいた。午前5時半就寝。

01/04(水)

午前11時半起床。軽くお雑煮を食べて、父の車で外出した。

まず、昨年末に購入した礼服の裾上げが完成していたので受け取った。ついでに真っ白のワイシャツと真っ黒のネクタイを買ってもらったので、これでいつ葬式があっても準備は万端というわけ。もちろん葬式なんてないほうがいいから、せっかく買ってもらってなんだがこの先10年くらいは実家で塩漬けにしておきたいものだ。

外出。礼服を購入してもらう。自分くらいの年齢になると一着持っておくべきらしい。
週記（2022/12/26-2023/01/01） - kotatsugameの日記

その後富山駅で下ろしてもらった。午後1時半、よことKRmei氏と合流。今日は夜までこの三人で遊ぶ予定。

最初に駅前に新しく経ったMAROOTというビルを見て回った。昔マリエに入っていたはずの書店がこちらに移動してきておりびっくり。

次に、駅に入って回転寿司を食べた。あまりお腹が空いていなかったため控えめに。二人の近況だったり高校同期のその後だったりが聞けて面白かった。自分は高校以前の交流がほぼ途絶えてしまっているのでこういう機会は貴重。

その後ゲーセンに移動。駅前のゲーセンといえばゲームインさんしょう富山駅前店だったがすでに閉店している。ところが最近、駅ビルにGiGOが入ったらしい。駅から非常に近いためかなり便利そう。チュウニズムは旧筐体と新筐体が1台ずつだった。2種類の筐体が混在している店舗を見るのは何気に初めてである。よくTLに新筐体の待ちでトラブった人のツイートが流れてくるため良い印象がない。

ゲームインさんしょう富山駅前店が今月末で閉店するというツイートが流れてきた。
週記（2021/10/25-2021/10/31） - kotatsugameの日記

混んでいたので、2時間弱で切り上げて夕食へ。ラーメン一心という店に行った。ここは富山地方鉄道の駅の裏にあって微妙にアクセスが悪い。雨も降っていて大変……と思っていたら、KRmei氏が駐車場などを辿って濡れずに移動する経路を教えてくれた。

さっきのゲーセンがある駅ビルに戻って、1階上のブックオフに行った。ゲーセンと同様これもつい最近入った店舗。しばらくうろついていたらよこが帰る時間になったため、KRmei氏と共に見送った。このまま新幹線で東京に戻るらしい。

KRmei氏も今日富山を離れるが、出発は3時間ほど先のようだ。せっかくなのでカフェに入り、時間になるまでしこたま話していた。自分は何でもかんでもツイートするがKRmei氏はそうではない。私生活についての話が興味深かった。おすすめの動画などを教えてもらった。

どういう経緯だったか忘れたが競プロの話になって、何やら興味がありそうだったのでしこたま布教した。なんとすでにPythonを少し勉強したことがあるらしい。おあつらえ向きすぎる。問題文をそのままコードに起こすのはできそうなので、最近の傾向だとABC-Bまでは問題なく通せるだろう。そこから先は知識が必要になってくるが、教材ならいくらでもネットに転がっているからぜひ頑張ってほしい。

午後10時前にKRmei氏を見送り、自分も父に迎えに来てもらって帰宅した。すぐ入浴。

THE名門校という番組が母校を取り扱った回の録画を見た。いろいろあったが今は素直に懐かしさを感じる。壁が黒板なりホワイトボードなりになっていたのは、大学にも同様の設備があるから、かなり便利だったのだろうということがわかる。それほど活用できた記憶はない。

その他、今日おすすめされた動画をいくつか見てからSRMの準備に取り掛かった。都合よくこどふぉっていたのでノートPCの環境を整えようとしたが、Appletを起動した後プラグインの設定中に時間切れ。結局Web Arenaで参加した。SRM843。

https://community.topcoder.com/stat?c=round_overview&er=5&rd=19527

最初に、EasyとMedを落としたことを明記しておこう。下にある解法はコンテスト中の自分のもので正しくないということに注意されたい。

Easyは、まず一周聴いても退店しないケースを除いた後、入店タイミングを各曲の開始時間として全探索した。これで何曲聴くかはわかって、さらに次の曲が始まる直前までずらすことでそのようなタイミングがどれくらいあるかも計算できる。

Medは+がいくらでも使えるので数の表現を考える必要がない。値の小さなほうからdpした。遷移は $+1$ 、 $+5$ 、あとは自分以下の数との掛け算で、最後のものは全体で $O(N\log N)$ となる。

Hardは謎。連結成分を頂点数で表現しその列を状態としてdpしたところ、TLには間に合わないが手元でそこそこ高速に動くコードが完成した。入力パターンがかなり少ないので、全部埋め込んで提出。

Medがチャレンジで落とされ、Easyはシステスで落ち、Hard 1完で10位。レートは2912→2894(-18)で何とか軽傷といったところか。

Easyは最初に取り除かなかったケースでも必ず全曲聴くことになるケースがあって、この場合入店タイミングはいつでもよい。自分の解法だと次の曲が始まる前に退店するケースしか考えていないため、「入店直後と退店直前で同じ曲を聴いている」ケースを考慮できていなかった。

Medは大きな数と大きな数を足し算する必要があり、上に書いた遷移では考慮できていない。やけに簡単に解けたから提出前に結構疑う時間を取ったはずなのに、何を考えていたのだろうか。

Hardは頂点数が $S$ を超えた連結成分を全部マージして扱うと十分高速になるらしい。これが1000点ってマジ？

朝までラノベを読んでいた。「現代社会で乙女ゲームの悪役令嬢をするのはちょっと大変」4巻を読了。3巻巻末で2021年冬発売と予告されていたのが1年遅れたわけは、後書きによれば「昨今の情勢と諸事情」らしい。昨年はなんともすごい年だったからわからないでもない。何であれ続刊してくれて嬉しい。

この巻は、これまで破竹の勢いでグループを拡大していた主人公が負ける話だった。なろう版でも読んだので展開は知っていたはずだがやはり辛い。ただ、改めて読んだことで前後関係への理解が深まり、納得はできたと感じている。

この先は金融以外のシーンも多くなりそう。なろう版では話がとっ散らかっていた印象もあるが、結局幼い主人公は金融に関して表舞台に立てないのだから、その分の無双を別の話で補給していく感じで楽しみたい。5巻出版は決定しているようだ。気長に待つ。

それに合わせてですが、五巻決定をご報告させていただきます。
　五巻は来年中に出せたらと思っているのですが、昨今の情勢から確実な日時が言えない事についてはお詫びさせてください。
　これも読者の皆様の応援の結果でございます。
　どうかこれからもよろしくお願いいたします。
— 二日市とふろう　(旧名:北部九州在住) (@hokubukyuushuu) 2022年12月25日

午前6時頃、父の朝食に便乗して自分の食事も用意してもらった。

布団に戻ってハーメルンを1作読了。「ナンジャモさんのお隣さん」。まだ3話しか投稿されていないが、転生前の手持ちがそのままということで、なつき度やレア度に関してニヤニヤできる設定が多い。

syosetu.org

午前7時頃寝落ち。

01/05(木)

午後1時半起床。久しぶりにメールの確認をしたら、指導教員の先生から一昨日届いたものを発見した。しかも返信を求められている。もはや謝るしかない。

そのまま布団でハーメルンを読んでいた。午後4時から午後6時半までの二度寝を挟みつつ、2作読了。

1作目、「消えた天才が喫茶店やってる話」。過去のバンド名をひた隠しにしているように見えて、早々にポロっと明かしているのが読んでいる側としては手っ取り早くて嬉しい。「音楽チートで世に絶望していたTS少女がSIDEROSの強火追っかけになる話」を読んでからオリ主が有名人なものを漁ってばかりいる。

syosetu.org

2作目、「ジム廃業して飛んでパルデア」。いろんな地方の、つまりいろんな世代の特殊なワザや能力を使っているのが面白かった。ポケモンのスカーレット・バイオレットが舞台だとナンジャモで配信者要素が摂取できるのがうれしい。

syosetu.org

今日の夕食は外食だった。どこに行くか決まっていないらしかったので焼肉と言い放ったら本当に連れて行ってもらえた。以前焼肉を食べた後の腹痛で救急車を呼んだのは記憶に新しい。今日はしっかり焼くことと、生肉を掴むトングと焼けた肉を食べる箸を使い分けることを意識した。

食事 pic.twitter.com/DGGs5TRUtt
— こたつがめ (@kotatsugame_t) 2023年1月5日

帰宅してハーメルン。「官能小説の世界に転生したらお隣さんが陵辱される直前の母娘だった件」を読了。R-18にならないくらいの淫靡さでよかった。

syosetu.org

入浴し、昨日のSRMのEasyをupsolveして、午後11時半からCF #842 div.2に出た。

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

Aは $x!+(x-1)!=(x+1)(x-1)!$ なので、 $x=k-1$ とすることで必ず条件を満たし、さらに明らかに最大。コーナーケースがあるのではないかと怪しんで $k=2$ など念入りにチェックしたが本当に何もなかった。

Bは要素の削除と追加を $k$ 個ずつ行うのではなく、一気に削除して一気に追加すると思ってよい。できるだけ多くの要素を削除しないままにしたいので、 $1,2,\dots$ の列がどこまで $p$ に部分列として含まれるかチェックし、その部分列以外の要素を動かす。

Cは値の降順に構築した。値 $i$ を埋める際は $a$ に出現する $i$ を数えて、3か所以上なら不可能、2か所なら $p$ と $q$ でそれぞれ置いてもう一方のマスを空きマスとしてチェック、1か所なら $p$ も $q$ もそこに置き、出現しないなら以前チェックした空きマスに埋める。

Dは操作後の数列 $n-1$ 通りを全探索する。完全に昇順に並べるケースとほとんど差がないので操作回数の差も小さい。具体的には $\pm 1$ になるので、どちらになるか判定。例えば $i$ と $i+1$ を逆転させて並べる場合、逆に最初の $p$ で $i$ と $i+1$ を入れ替えていると思うことができる。これを使って判定した。

Eは高々3回でソートできる。0回、1回、3回を数えて補正した。0回なのは最初から $p$ がソートされている場合で、1通り。1回なのは前 $n$ 要素または後ろ $n$ 要素がソート済みの場合で、 $2(2n)!$ から両端 $n$ 要素がソート済みの重複 $n!$ と全体がソート済みの場合を取り除く。

3回はちょっと面倒。前 $n$ 要素に後ろ $n$ 項に行くべき値があり、かつ後ろ $n$ 要素に前 $n$ 項に行くべき値があるケースである。包除原理で、全体 $(3n)!$ からどちらかを満たさないケース $2\times{}_{2n}\mathrm{P}_n(2n)!$ を引き、両方満たさないケースを足した。最後のケースは真ん中 $n$ 要素にいくつ前 $n$ 項に行くべき値があるか全探索すると求まる。

Fはジャンプする際 $\min(a_i,a_{i+1},\dots,a_j)=a_i,a_j$ になると分かったがそれ以上先に進まず。5完14位。

R-18のハーメルンを1作読了。「投げ銭アクメ系バーチャル配信者」。ちょっとついていきにくい描写もあるが序盤や番外編はなかなか好みである。

https://syosetu.org/novel/273699/

今日起きた時に発見した先生からのメールに今更返信。その後朝方までほかの人のブログ記事や動画を見ていた。午前6時頃に今日の昼食として用意されていたものを食べ、しばらく日記を書いた。

市役所の業務が始まるのを待ってマイナンバーカードを受け取りに行った。パスワードの設定は、希望の文字列を紙に書いて提出し、それを職員が見てPCに打ち込むことで行うらしい。パスワードを他人に見せるのが前提となる仕組みを、誰もおかしいとは思わなかったのだろうか。

帰宅して就寝。午前9時半だった。

01/06(金)

午後3時起床。

そのまま布団でR-18のハーメルン「セックスごっこをしてくれた幼馴染みとガチセックスする」を読了。腐れ縁なのでやり取りの口調が乱雑だが、盛り上がるとちゃんと引っ込んでくれるのは好み。

https://syosetu.org/novel/270067/

身を起こしてラノベを開いた。午後8時前に「紅蓮戦記」2巻を読了。面白かった。魔法でできることがかなりシステマチックに設定されているため、ファンタジー戦記モノとして読みやすいし、主人公の強さが魔力量のみでなく戦い方の点からもしっかりと感じ取れる。その二つを軸に面白いように勝つので、シンプルに楽しくもあった。

新しく出てきた敵国の王女様についてはちょっと消化不良気味。主人公を低く見積もる様子が念入りに描かれたので、終盤でスカッとした勝ち方をするのかなと思っていたが、そうではなかった。上で述べた魔法の制限もあって、王女様との戦闘は無双できるような状況ではなかったのが残念。

それ以外はスッキリまとまっていた。あまりにもまとまりすぎているためさてはと思ったら、案の定この巻で完結だった。ラストでその後について少し語られたのがありがたい。概ね満足していると言って良いだろう。

食事と入浴を済ませ、午後9時20分からyukicoder 372に出た。

yukicoder contest 372 - yukicoder

Aは $\max(A_1+A_2+A_3+B,3\max(A))$ 。 $A_1\le A_2\le A_3$ という条件に気づいていなかった。Bは和の中身が $n\ge M$ なら必ず0になるので計算しなくてよい。

Cは $a$ と $b$ を全探索。 $x=a(p^{-1}+p^{-3}+\dots)+b(p^{-2}+p^{-4}+\dots)=\frac{pa+b}{p^2-1}$ となるため、これが $1/N$ より大という不等式を解けば $p$ の範囲が求まる。分数が出てくると扱いが面倒なので、全体を4倍して $(2p-Na)^2\lt N^2a^2+4Nb+4$ と変形した。

Dはよくわからなかったので8次元累積和を計算した。値を周囲から包除原理のように集めてくる方法で計算したため、1マスのために $2^8$ マス見る必要があって1100ms。後から考えてみれば8方向に累積和を取るほうが簡単かつ高速だった。

Eは惑星の距離がいかついが実はギャグ。 $T_i\ne T_j$ ならどこかのタイミングで恒星から一直線に並ぶため、円運動の半径の差になる。 $T_i=T_j$ の場合は位置関係が変わらないため $(X_i,Y_i)$ と $(X_j,Y_j)$ の距離になる。これを使ってコストが $\max$ のdijkstraを行う。後者はもともと根号がついているため、それを外すだけでコストが求まる。前者は誤差が怖いので適当な範囲を調べて求めた。

Fを見て逃亡を選択。より多く解かれていたGに逃げ込んだ。いかつい式を丁寧に解釈すると $\sum_{n=L}^R\sum_{i=1}^{n-1}\binom{n}{i}^2$ になって、内側の和をWolfram|Alphaに投げたら $\binom{2n}{n}-2$ となった。あとは $\binom{2n}{n}\bmod M$ を一つずつ丁寧に求める。

$M$ を素因数分解して $\bmod{p^e}$ ごとに計算し、中国剰余定理で復元した。すべての値を「素因数 $p$ の個数」と「残り」の組として保持する。階乗をこの形式に直すのはルジャンドルの公式っぽく行えて、除算も「残り」の部分だけ真面目にやればよい。その「残り」は $\bmod{p^e}$ で計算する必要がある。うっかり $\bmod p$ で計算していたため、全然合わずかなり長い間苦しんだ。

Gに時間を取られこれ以上は解けず、6完9位。

何もやる気が出ずラノベに手を出した。「ブラックな騎士団の奴隷がホワイトな冒険者ギルドに引き抜かれてSランクになりました」8巻を読了。主人公が、政治的な事情もあってヒロインの一人と結婚した。そんなメインを張るようなキャラだとは思っていなかったためかなり衝撃的だった。そして次巻、完結らしい。ずいぶん急だと感じたが、実際未解決で残っている話は少ないのかもしれない。よく覚えていない。

仙台には明日帰る。乗車券の有効期限が明日までなのとABCがあるから。仙台から持ってきた本が1冊、帰省の道中で買った本が7冊だった。今読み終えた本で帰省中に7冊読んだことになるから、仙台に持ち帰るのはたった1冊。完璧。

午前5時まで日記を書き、布団に入ってハーメルンを1作読了。「グロリアス軽戦車」。途中絵が描けず逃亡したあたりで苦しくなって少し間が開いていた。読んでみると案外すぐに回復して、結局はハッピーエンドになってくれた。

syosetu.org

午前6時半就寝。

01/07(土)

正午過ぎ起床。なかなか起きられなかったため昨日考えていたスケジュールは破綻してしまった。まあABCまでに仙台に着けばよいので余裕は結構ある。その上年末年始だから臨時列車が走っているらしく、ちょうどよい時間にかがやきがあった。来るときも乗ってきた途中停車が全然ない速い新幹線。

食事して荷物をまとめ、出発。富山駅までは父の車で送ってもらった。残り20分で特急券を買う必要がある。改札横の券売機は1台が修理中で残り1台に数人待ちがいたが、みどりの窓口の中に3台あってそちらは待ちなしだった。無事購入に成功。父と別れ、乗車した。

持ち帰ってきた本を開いたが眠気が強く、大宮まではずっと寝ていた。乗り換えて仙台までは、今度はなろうをずっと読んでいた。結局本はほぼ進まず。

午後5時半ごろ仙台に到着し、即座にゲーセンに向かって午後8時前まで11クレプレイした。新曲を埋めたのと14+のSSS+が一つ、また新年初の理論値も出した。チュウニズムのグッズキャンペーンは今最後のキャラクターと引き換えられる期間で、今日で無事必要ポイントを集め終わった。一安心……と思いきや、チュウニズムデュエルが終わっていない。01/11までにあと10クレほどプレイする必要がある。

まぜそばを食べて帰宅。途中で、新幹線で読んでいたなろうを読了した。「Killer Queen～FPSで幼馴染(美少女)を最高に幸せにする方法～」。

https://ncode.syosetu.com/n7715hb/

主人公が強くてよい。現実感との兼ね合いかポロっと負けてしまうことも何度かあったが、FPSの競技シーンを知らないのでもうちょっと無双してくれたらなあとか考えていた。配信をサポートするのに会社を立ち上げたり、過去のしがらみが顔を出したり、風呂敷は結構広がっているものの残念ながらエタっているように見える。後者についてはしっかり向き合うと辛そうだし、順調なところで途切れているのはむしろ読みやすかったかもしれない。

午後8時半ごろ帰宅。準備して午後9時からABC284に出た。

AtCoder Beginner Contest 284 - AtCoder

Aは1行読み飛ばして残りはtac。readを無引数で実行するとジャッジの環境では何も読まれないらしく、 $N$ が出力に残って1WA。手元と挙動が違う。bashで通したあとVimで書き直したら縮んだ。

ここからはC++。BCはやるだけ。Dは $\sqrt[3]N$ まで調べると $p$ または $q$ が見つかる。 $p$ が見つかればよい。 $q$ が見つかれば $p=\sqrt{N/q}$ とわかるが、うっかり $q+1$ から順に試し割りで見つけようとしてしまいTLEを出した。続けて行っているから合わせて $O(\sqrt[3]N)$ だと思ってしまった。

Eはよくわからないが10⁶本見つかった瞬間打ち切るdfsで通るだろうと思って提出。案の定通った。Fは $T+{\rm rev}(T)$ と ${\rm rev}(T)+T$ それぞれにZ-algorithmを適用すれば解ける。

Gは $A$ をfunctional graphと見たとき、 $i$ からスタートしてループに入るまでの長さが $S_i$ になる。 $S=S_i$ となる $i$ と $A$ をまとめて数え上げた。ループの長さを $L$ とすると、まず頂点を $S$ 個選んで並べ、その後にループの頂点を $L$ 個選んで並べ、残りはなんでもよい。つまり ${}_N\mathrm{P}_{L+S}\times N^{N-L-S}$ 通り。これに $S$ を書けて足し合わせたい。

$S$ と $L$ でループを回すのではなく $S+L$ と $S$ でループを回すとよい。上の場合の数は $S+L$ ごとに一定で、 $S$ の寄与だけ別に計算することができる。 ${}_N\mathrm{P}_{L+S}$ は割り算を使わず計算できるので $\bmod M$ でも安心。

Exには手も足も出ず、残り時間はコードゴルフをしたりシャワーを浴びたりしていた。7完15位。水曜日に競プロを布教したKRmei氏も無事コンテストに出ていただけたようだ。今回はグラフを扱うテクニックを知らないとCが解けないので、解説を読むなりしてぜひ頑張ってほしい。

コードゴルフ。AはVim 9Bが最短でよさそう。提出時間の差で勝ち。Bは今のところdc。CはPerlで、負け。Dはfactorを使うまではよくて、文字列置換で答えを作れることに気づいてVim 35Bでホクホクしていたらdcに投げたほうがもっと短くなるらしく大敗。EはPerlがTLEしたので放置。以降は手付かず。

午後11時からTROC #30に出た。

https://tlx.toki.id/contests/troc-30

Aは $\max(N,\lfloor N/Y\rfloor\times X+(N\bmod Y))$ 。Bは $A$ の値を区間に伸ばすと見なせるやつで、 $B$ から隣接する重複要素を取り除いたものが $A$ の部分列になっているかチェックすればよい。FA。Cはいくつか手で試し、どうせ $2\min(N,M)$ だろうと提出した。

Dは $-1$ を全部取り除いた列と同じ値が達成可能で、当然最小。そこに $-1$ を入れると、bitごとにどのタイミングで切り替えるかの自由度が生まれる。それを掛け合わせたものが答え。

Eは最初に最小全域木を求め、その上のimosで必要な辺をチェックした。reading-zeroをつけないようにするなど出力が面倒。

Fの操作は $K$ 項まとめてswapすると読み替えられる。そこからかなり時間がかかった。結論から言えば、要素を $i\bmod K$ でグループ分けしたとき、それぞれをソートするだけで全体もソートされることと、各グループで転倒数の偶奇が等しいことが条件になる。

1項だけずらして2連続で操作することであるグループだけ転倒数をちょうど2変化させることができ、1変化させようとしたら1回の操作で全グループ一気に変える必要がある、ということから後者の条件が出る。前者のチェックし忘れで1WA。

順位表を見てHに進んだ。最初に $A$ 全部のbitwise ANDを全体から引いておくことで、両方のグループのbitwise ANDを0にする問題になる。2段階の包除原理を行った。つまり、まず最初の包除原理で一つ目のグループのbitwise ANDを固定し、二つ目のグループのbitwise ANDが0になる場合の数を数えるためにさらなる包除原理を行うということ。

決め打った二つのbitwise ANDは共通のbitを持たないため、全体で3²⁰通り調べればよい。しかし手元で2.5secくらいのものを提出したのにサンプルでTLEしてしまった。3²⁰通り全部計算するわけではなく条件のチェックなどが入るため、計算をまとめるのも難しい。

いろいろ見方を変えた結果、「 $i\subseteq j\subseteq i\cup I$ なる $j$ に $+1$ 」というクエリを2²⁰回処理できればよくなったが、解けただろと思っていろいろ試しても全然高速にならず愕然。そのままコンテスト終了。

終了3分後にHが通った。上のクエリが微妙に高速化できたようだ。 $i$ と $I$ のサイズを比べて小さいほうの部分集合を全探索する。 $I$ のほうが小さい場合はそのまま $+1$ すればよい。 $i$ が小さい場合は20次元のimos法、つまりゼータ変換を考えると、 $i$ の部分集合と区間の終端を表す $\pm 1$ を置く場所が対応していて、最後にゼータ変換することで必要な $+1$ だけがうまく行える。

Hが思ったより解かれており6完23位、2786→2771(-15)。優しい。ジャッジがAtCoderくらい強くてHの3²⁰を通してくれたらもっと優しかった。

しばらくYouTubeを見たりハーメルンの更新を読んだりした後日記を書いた。午前7時半就寝。

01/08(日)

午後4時起床。布団に横たわったままハーメルン「お辞儀様の娘はTS転生人外幼女」を読了。

syosetu.org

主人公以外の視点がちょくちょく挟まるのが嬉しい。ホグワーツとどう関わるのか楽しみにしていたが、最新話の時点でハリーは5歳。まだかなり遠そう。しかもすでに原作からかなり外れていて、全く先が読めない。

午後7時過ぎに布団から脱出して食事。

01/11にホスフィン・たいぺーと遊ぶ。いつものように外で食事してから我が家で家飲み。そのための酒類やボードゲームをいくつかAmazonで購入した。ボードゲームについては有識者に意見を聞き、「ito」「タギロン」「ギャンブラー×ギャンブル！」を注文した。

3人で遊べてAmazonで買えるボードゲームを探しています
— こたつがめ (@kotatsugame_t) 2023年1月8日

午後11時半からECR141に出た。

Dashboard - Educational Codeforces Round 141 (Rated for Div. 2) - Codeforces

Aは降順に並べると大体うまくいく。最大値が二つ以上あるケースが問題で、特に全要素が等しい場合不可能。そうでない場合は最大値でない要素を一つ先頭に置けばよい。

Bは $1,n^2,2,n^2-1,\dots$ と並べるだけであり得る差がすべて得られるらしい。行列をジグザグに埋めた。

Cは勝利回数 $k$ を全探索。基本的にコストが安い人から $k$ 人に勝つことを目指すが、 $k+1$ 番目の人だけは勝利回数が $k$ 回または $k+1$ 回となって自分の順位に影響するため、その人に勝つか負けるかは両方試す必要がある。

Dは次の操作に使う項の値を持ってdp。それが0なら2種類の操作のどちらを選んでも列は同じ。0でないなら他の列と重複しない新しい列が二通り得られる。

Eはちょっと手こずった。すべての $i$ で $\left\lceil\frac{a_i}k\right\rceil\le\left\lceil\frac{b_i}k\right\rceil$ を満たすことが条件。最初、商列挙で調べようとしたが、 $O(n\sqrt n)$ が2.5secくらいかかって間に合わない。改めて式をよくにらみつけると、これは $[b_i,a_i)$ に $k$ の倍数がないことと同値。この区間にチェックを入れておき、 $k$ ごとにその倍数のチェックを全部見に行くと $O(n\log n)$ で解けた。

Fは順列が一つの場合、それをfunctional graphと見たときの連結成分数を $n$ から引いたものが答え。 $i$ で操作すると $i\rightarrow i$ というサイクルが独立するが、すべてのサイクルがそのような1点のみのものになるまでの操作回数なので、各サイクルにつき一つずつ操作しないインデックスがある。

順列が二つの今も同様に、操作しないインデックスの個数を最大化することを考える。そのようなインデックス集合の条件は「どちらの順列でも一つのサイクルに二つ以上乗っていないこと」と書ける。これは最大流で表現できる。

Gは手も足も出ず、6完9位。Eを商列挙で通した人がいるらしい。どうやったのか見に行くと、 $\sqrt{b_i}$ で処理を分けるちょっと面倒な書き方だった。商列挙自体は、商が $q$ となる最大の除数が $q$ で被除数を割ることで求まるのを使うとシンプルに書けるのだが、こちらだと割り算の回数が少し多いようだ。

新春TechFUL Coding Battle 2023に参加した後日記を書いて午前9時半就寝。火曜日までなのでここには何も書けないし、正確な時刻を記録するのも躊躇われる。実はECRが終わってからTechFULを解き始めたというわけでもない。とりあえず点数が見える部分は理論値で通せた。

https://techful-programming.com/user/event/3814