週記(2022/10/17-2022/10/23)

10/17(月)

午後2時過ぎに目を覚ました。もうひと眠りできるくらいの時間。ただし今日は、先週の週記を書き上げた上明日のセミナーの準備までする必要があるので、このまま起きて取り掛かる。まず週記を完成させることにした。

午後4時半からインターン先定例会。先週の進捗報告を休んだので、今週は2週分まとめての発表となった。大層なことをできていないので話す内容が増えてやりやすいという側面もある。

勉強会はプログラムの設計の話だった。開発をやりやすくするための設計方針はいろいろあるだろうが、どれに対してもそのアンチパターンこそが正解となるシチュエーションが考えられそう。ただそういうコーナーケースばかり考えていてもしょうがなくて、自分はまず何か一つの方針に則って設計するということを体験しなければならないはず。

勉強会の終了からしばらくして、週記が完成した。今週はなんと校閲まで済ませてある。午後8時に投稿した。ちなみに一つ前の週の週記は校閲が終わっていない。先週はその週の週記を書くことに注力していたのだ。

いよいよセミナーの準備に取り掛かろうとしたものの、眠気が強くなってきた。それでやる気も出ずしばらくTLを眺めていたが、さすがにこのまま過ごすのは効率が悪すぎるということで仮眠を取ることにした。夜中にコンテストがあるので、それまで2時間、午後9時半から午後11時半まで寝ていた。起きてすぐECR137に出た。

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

Aは6\binom{10-n}{2}aは読み捨てた。Bは1と2を両端に置けばよい。Cは蓋をされている箱が連続する区間を求め、その一つ左を含めた中でどれに蓋をしないのが一番被害が少ないか計算。うっかり右からdpしてしまって、蓋が左隣より遠くにある箱に被せられてしまい1WA。

Dはちょっと面白い。立っている最上位bitを最も大きな値にしたいので、s_1としてはs全体を選ぶのが良い。特にこの段階で先頭に1が現れるまで文字を削除しておくと便利。1が出現しなかった場合は別に処理する。次に、s_1で立っていない最も上位のbitを求める。存在しない場合はまた別処理。このbitを立てるのが次の目標になる。複数の方法がある場合は、そのうち答えが最も大きくなるものを選ばなければならない。

ここで入力がランダムであることが効いてくる。立っていない最上位のbitは上から少し探せばほぼ確実に見つかるのだ。あるbitを立てるためにはそれより上位からずらしてくる必要があるので、試すべき候補数が十分少ないことが分かった。あとは全探索すればよい。

Eは難しかった。二つのレーザーが同時に発射された直後の相手の耐久値でdpする。まず、以降二つのレーザーが同時に発射されない場合は単純な二分探索で答えが求まる。そうでない場合、次にレーザーを同時に発射するタイミングは必ず、どちらかのレーザーがちょうど何回目かのチャージを終えたタイミングになるとわかる。そもそもh回もレーザーを打てば耐久値を0にできるので、これは全探索してもO(h)通り。状態もO(h)通りなので間に合う。

Fもちょっと面白い。集合に入りうる各値について、それが入るような演算子の決め方が何通りあるか数えることにする。S_{i-1}まで決めた時点でxが入っている場合の数がaだとし、次のS_i=[l_i,r_i]op_{i-1}について考える。これまでの決め方が3^{i-2}通りとなることに注意。

l_i\le x\le r_iのとき、\cup\rightarrow 3^{i-2}\oplus\rightarrow 3^{i-2}-a\cap\rightarrow aより2\times 3^{i-2}となる。それ以外のとき、\cup\rightarrow a\oplus\rightarrow a\cap\rightarrow 0より2\times aとなる。まとめると、[l_i,r_i]に対して3^{i-2}をセットした後全体を2倍すれば表現できる。これは遅延セグメント木に乗る。

Gは面白かった。文字列の各prefixに対して、それを分割する方法を数え上げるdpをする。メモリの制限でdp配列を持つことすらできないが、実はそもそも見るべき位置が少ない。遷移してこれない位置にだけ着目すると、そのような位置から今見ている位置までの部分文字列がフィボナッチ文字列になっている必要があって、短いフィボナッチ文字列が少ないことからわかる。

ただこのままでは判定ができないので、もうちょっとインクリメンタルに更新する方法を考えた。今見ている位置までの文字列が、あるフィボナッチ文字列のprefixとなるような位置を持つことにする。これが十分少ないことは実験エスパー。特に今出現しうるフィボナッチ文字列は、f_0以外は十分大きな、例えばf_{32}のprefixであるから、f_{32}から適切な位置の文字を取得してきて今見ている文字と比較することで、その文字まで見てもまだprefixであるか否かが判定できる。長さがちょうどフィボナッチ数のprefixだった場合のみ遷移元として不適切となる。

フィボナッチ文字列から位置を指定して文字を取得するのは、フィボナッチ文字列の構成を逆に辿ることで行える。f_0の取り扱いに注意。出したら3300msで通り、全完4位。

朝までセミナーの予習をしていた。Dilworthの定理は半順序集合に対するものだが、Diestel 2.5.2の証明においては推移律しか使っていないように見える。反射律を入れても仮定は前順序というやつで十分。しかしどこを調べてもそういう内容が書いていなくて不安になった。ツイートしたらmaspyさんから同意のリプライがもらえたので、少し安心。

先週から発表の原稿を事前にメールで共有するように言われていたので、少し丁寧に書いたものをスキャンして送信。その後コードゴルフをして午前8時就寝。

10/18(火)

午前10時半にインターホンの音で起床。MHC Tシャツが届いた。注文してからまだたったの五日であるためびっくりした。

その後二度寝できずずっとTLを見ていた。正午くらいに布団を脱出し、生協に寄りつつ山に向けて出発。午後1時からセミナー。

最初2時間は先生が講義で使用するスライドに載せられた演習問題を解いて議論していた。実際に解けるのか、難易度はどうかとか。特に一つ目の小問は、最初問題だけを見せられると明らかに知識が足りなかったが、スライドにある事実を認めればアイディア一発ですぐ出る問題でちょっと面白かった。行列に関する命題を、行列を構成する要素を一列に並べて数列に関する命題に帰着するというもの。

その後2時間で自分の発表。後期から教室が変わって黒板が小さくなり窮屈そうだなと思っていたものの、今くらいのサイズのほうが全体を行き来できて、それがわかりやすいかはともかくやりやすかった。関連することをうっかり黒板の両端に書いてしまったりすることがよくあるが、特に問題にならなかった。内容は途中結構質問が入ったため、昨日準備したもので時間的にちょうどとなった。予習して自分だけ理解しているからといって、ぼんやりした説明のまま進めてはいけない。

その後しばらく来週のセミナーや木曜日のTAについて打ち合わせをして解散。ホスフィンに誘われて学食に行き、1時間以上話していた。

午後7時半帰宅。非常に眠いため、早々にシャワーを浴びて布団に入った。午後8時半から午前2時まで寝ていたらしい。

食事してTAの業務。木曜日の発表スライドがもう共有されていたので、読んでコメントや指摘をした。結構丁寧にやっているのでTAとしては明らかに過剰な業務となるが、絶妙に知っているようで知らない分野なので、読んでいて勉強になる。あとは単純にスライドに対してあれこれ言うのが楽しい。

それが終わってからTCB52に参加した。日曜日終了なのでここに感想を書く。

1問目が微妙に面倒。制約の「文字列の長さが4以上」と「tech型またはful型である」というのを最初読み落としてちょっと戸惑った。2問目から5問目まではよい。

6問目はちょっと読解に時間がかかった。i番目を含む周囲の文字からiを特定する問題とわかってしまえば、左右に追加で何文字聞けばわかるか調べる方針が出る。それぞれl文字、r文字とすると、Aの長さはl+r+\min(l,r)とできる。制約が小さいのでこれでも解けるが、実はl=0またはr=0の場合しか考えなくてよい。

7問目はSA+LCP。各suffixがSAにおいてどこに出現するかもセグ木で持っておく必要がある。クエリごとにそれを用いてどこからどこまでのLCPを求めればいいか計算する。8問目はどのインデックスの文字を持ってくるか貪欲に決定してよい。先頭から順に最も近いものを選ぶのが最適。すると単に数列の転倒数を求める問題となる。

9問目はtrie木。10問目はABCに2値に制限された問題がある。この二つで考察が必要なかったため、普段の回と比較して高速に解くことができた。30分ちょっとで理論値達成。この合計解答時間については、「解答所要時間」ではなくコードの詳細ページから「合格経過時間」を見て和を取れば正確な値がわかることを知った。

G - Range Sort Query

しばらく日記を書いた後、少しコードゴルフをして午前8時半就寝。

10/19(水)

午後2時前起床。準備してオンライン会議に接続し、いつも1on1をしている方とのペアプログラミングに臨んだ。

コードの仕様が少し変わって今のままでは対応できないので、書き直す作業が発生しているらしい。今日はその初手の設計段階だった。早速月曜日の勉強会で学んだことが活かせる機会、に見えて、元あるコードを書き直すのを優先すべきなので、コードの構造に対して何か変更を入れるというわけではなさそう。とりあえず肥大化したファイルの分割だけはどうしてもとお願いした。

3時間くらいかけ、大まかな話がまとまりつつあるところで今日はいったんお開きに。タスクとしてはコードを読んでおくよう依頼されたが、どうせ読むならという気持ちで自分でもブランチを切って書き直してみることにした。ペアプログラミングといってもこちらはずっと手を動かしていなかったため意欲が増すばかりで、その分この後4時間くらいずっとガリガリ書いていた。

コードが動くことは確認できても、出力を生成する段階まで書き直し終えないと正しく動いているかどうかがわからないのはちょっと困る。また出力が得られたとして、その形式がこれまでと変わっているので、比較する方法についても考えなければならない。

TCO22 Finalistへのインタビューが公開されていた。顔面と本名とハンドルネームが紐づけられた状態で大公開。ちなみにこの顔写真は一ノ関駅にあった顔出し看板で撮ったもので、当時の日記にも言及がある。

tco22.topcoder.com

一ノ関駅ピカチュウポケモントレインの顔出し看板があって、そこでもホスフィンに写真を撮ってもらった。

週記(2022/09/05-2022/09/11) - kotatsugameの日記

ホスフィンから競プロっぽいという論文が送られてきたので、YouTubeに気を取られつつ読んだ。タイトルになっている部分をなんとなく理解するまでで、他いくつか載っていた細かな話題に関しては見ていない。

Depth-First Search Using $$O(n)$$ Bits | SpringerLink

普通にdfsするとバックトラックのためにO(n)要素保存する必要があってO(n\log n)Bitsかかるが、そこを改善したらしい。改善といっても空間計算量を減らした分時間計算量に押し付けていて、O(m\log n)時間かかっている。保存する要素を直近のO(n/\log n)要素にすることで空間計算量を減らす。するとバックトラックが行えないタイミングがO(\log n)回あるので、それらについてはO(m)時間かけて頂点の訪問状態を見ながら再構築するようだ。頂点の訪問状態もまたO(n)Bitsで表現できる。

まだわからない部分もある。隣接リスト形式のグラフを扱っているので、各頂点についてリストのどこまで見たかを覚えておく必要があるはず。その情報分、O(\log m)Bitsはどうやって保存するのだろうか。グラフに多重辺が大量にあったりするとO(\log n)\subsetneq O(\log m)になってしまいそうなものだが。

しばらくコードゴルフした後、今日もまたTAの業務を行った。明日発表する人がそれほど時間を使わなそうということで、もう一人も少し発表する予定になっていて、その人の発表資料が共有されていたのだ。非常に面白いことが書かれていたのでぜひ図にしたいと思い、POV-Rayでプログラムを書いてGIF画像を作成した。

POV-Rayでアニメーションを作るのは少々面倒。基本的に一枚絵しか生成できないので、それを大量に用意してつなぎ合わせる必要があった。実行時に+KFF100などとオプションを与えると、ここに書いた数だけ生成される。画像を変化させるためには内部でclockという値を使うようだ。枚数によらず0から1まで線形に変化するので、適当に三角関数をかませることで、アニメーションらしく端でゆっくり動くような周期的な画像たちが得られるようにした。

上のツイートに貼ったGIF画像は実際に100枚連結している。これはImageMagickで作った。コードゴルフ大会で触れて以来久しぶりの登場。特に何か実装するわけでもなく、ググって出てきたコマンドをそのまま実行したら便利に動いてくれたので助かった。

少し日記を書いてから布団に入り、ラノベを読んで午前10時就寝。

10/20(木)

午後3時起床。眠気が強く、布団から脱出するまでにはしばらく時間がかかった。準備して大学へ。

教室に向かう前に生協に寄った。またしても出荷メールが届いてしばらく経つのに入荷メールが届いていない本があるので、それの確認。探してもらってみると、なんと出荷メールすら届いていない本もすでに入荷されていた。富士見ファンタジア文庫ラノベなのでちょうど今日が発売日。聞くところによると、メール送信に不具合があって一時期メールがうまく届かなかったらしい。もう復旧しているようだ。

前みたいに店頭に並べられたわけでもなく無事受け取れたので、特に問題はなかった。改めて教室に向かい、5限、TA。

一人目の発表者のスライドが60ページくらいあったのでもしかしたら今日だけで終わらないのではと疑っていたが、蓋を開けてみれば1時間も使わずに終わってしまった。必要なことが全部スライドに準備されており、もたつく様子がなかったのがすごい。

最後に付け足された発展的な内容、グラフの種数を用いたオイラーの多面体定理の一般化は非常に難しく、当人の説明の後先生に言われて自分なりに補足してみたりしたがそれでもあまり伝わった気がしなかった。どんな事実を認めてほしいか明確化するべきだったかもしれない。あとは具体例か。しかしトーラスの上に交差のないよう描かれた種数1のグラフを即座に作れるわけもなく。今考えてみれば、平面的でない簡単なグラフを適当にもってこればよかった。

余った時間で二人目。話し始めは少しまごついていた様子だったものの、一度軌道に乗った後はずっとスムーズに進められていて良かった。昨日自分が作ったGIF画像による図については、発表者の方でも何か用意してみてほしいとアドバイスをしていたが、さすがに昨日の今日では用意できていないだろうなと思っていたら、なんとすでに完成していた。GeoGebraによるもので、GIF画像に比べて手で動かせる点が優れている。

講義後しばらく、質問に来た学生と先生と話して終了。食事して午後7時過ぎに帰宅した。

しばらくYouTubeを見ていた。「総理大臣によるサーモンラン」という動画シリーズで、どういう技術が使われているかは知らないが岸田総理大臣っぽい声のスプラトゥーン実況。非常に面白い。基本的には実況らしい簡潔で的確な発言ばかりで構成されつつも、要所要所に政治家一流の迂遠な言い回しを用いているバランスがいい。時たま政治答弁みたいなゲームとほぼ関係ない話をペラペラ喋るのも面白かった。

そもそもスプラトゥーンというゲーム自体が面白いのかもしれない。初めて見るのに何となくルールが把握できるのはすごい。たまにTLで目にする「シャケ」とか「サーモン」が一体何なのか知れたのはよかった。その敵キャラを含め、命名が特徴的なのもいい感じ。

www.youtube.com

午後9時前に布団に入って就寝。起きたら午前2時半だった。ECRがあるのを完全に忘れており、目覚ましをかけてすらいなかった。マラソン以外皆勤の状態を4か月ほど維持していたのが途切れてしまい残念でならない。

意気消沈しつつもぞもぞ起きだして日記を書いていた。午前9時になって切り上げ、布団に入ってラノベを読み始める。眠れずそのまま読み続け1冊読了。

「転生魔王の大誤算」5巻。前の巻を読んでから結構間が開いたのでいろいろ忘れていることも多かったが、そもそも発売自体が遅かったためか要所要所には設定の大まかな説明があって、問題なく読み進めることができた。内容については4巻が非常に面白かったので期待していたものの、盛り上がりが物足りず残念。主人公の強みと敵の相性が悪くあまり活躍しているように感じられなかった。この敵は今後も登場するようなので、その顔出しという側面があったのかもしれない。

午後2時から1on1。水曜日にドサッと実装したので、それをお見せして判断を仰ぎたいと思いセッティングした。うっかり睡眠に失敗してしまいちょっと眠気が強い状態での会議になってしまったが、必要なところは聞けたし決められたのではないだろうか。水曜日に実装しながらメモを残していたため、うまく回らない頭でも議題を出せたのがよかった。気になっていた点のうちいくつかは、とりあえず動くものができてから考えるべきとの判断が下され、確かに……という気持ちに。ひとまず今あるコードを愚直に書き直していきたい。

しばらくコードゴルフして午後6時就寝。

10/21(金)

午前0時半起床。サークルのバチャとyukicoderをスキップしたのは、今度こそ自分の意志である。

寝る前に縮めたコードがさらに縮められていて、そこで新手が出ていた。AWK\max(\ast,0)を行う際は、先頭に文字列0を連結した後数値として解釈すればよいらしい。値が非負なら負号がないため全体が十進数として解釈されるが、負号がある場合はその直前で数値としての解釈が終了するため、0となる。

atcoder.jp

Perlにおける特殊変数$-に代入する行為も同じく\max(\ast,0)、正確に言えば\max(\lfloor\ast\rfloor,0)という効果を持つが、それを利用した最短コードが大量にあることからもうかがえるように、これは非常に影響範囲の大きな更新である。というのも、これを利用することで一般に\max(a,b)=a+\max(b-a,0)\min(a,b)=a-\max(a-b,0)と書けるからである。これまではa<b&&a=bとしていたところがa+=0b-aと書けるだけでも-1Bである上、bを変数に持つ必要がなくなればさらに縮む。

朝まで数時間最短コードのリストを探し続け、20個弱縮めた。中には8Bも縮んだものも。

atcoder.jp

午前8時から2時間ほど日記を書き、布団へ。横になって教科書を読むつもりが、少し目を瞑って考えているうちに寝落ちしたらしい。午前11時半に一瞬起きて、このタイミングで就寝報告のツイートをした。

10/22(土)

午後4時過ぎに冷凍弁当を受け取った。この前後合わせて1時間くらいは起きていた記憶がある。その後また二度寝した。

午後8時起床。しばらくコードゴルフして、午後9時からABC274に参加した。

キーエンスプログラミングコンテスト2022(AtCoder Beginner Contest 274) - AtCoder

Aはまず\lfloor 10000B/A\rfloorを計算して出力する方法で解いた後、しばらくコードゴルフした。dcの出力を加工する方針には早々に見切りをつけて、printfとフォーマット文字列"%.3f"を使うのをいろいろな言語で試していたが、その方針なら当然ながらAWKが最短となる。これに気づくまで10分くらいかかった。

Bはよい。Cは入力の意味が少しややこしくて、題意も含めての把握に時間がかかった。Dは偶奇で分けると1次元の問題になり、さらにA_1以外は符号を好き勝手に決めてよい。復元が必要ないのがありがたかった。Eは巡回セールスマン問題をちょっと変えるだけ。

Fはxがちょうど魚iの位置であるとしてよい。このiを全探索し、すべての魚の位置を魚iに対する相対座標で表しなおすとかなり見通しが良くなった。各魚について、それが区間[0,A]にいるようなt全体の集合は、\emptyset\mathbb{R}_{\ge 0}または両端が有理数区間になるので、三つ目をイベントソートする。

Gはちょっと面白かった。まず監視カメラは障害物またはグリッドの端を背にしてしか置かない。さらに下向きに置いたカメラとそれが監視する最も遠いマスに上向きに置いたカメラは同一視できる。左右も同様。こうやって定めた置くべきカメラの候補について、それを置かなくてよいケースというのは、担当するすべてのマスを直交する向きのカメラで監視できている場合のみである。

ところがこうやってカメラだけに注目した言い換えをすると辛い。互いに干渉するカメラ間に辺を張ったグラフは二部グラフだし、いかにもフローで解きそうな見た目をしているのに、うまく流量や頂点の意味を設定できなかった。貪欲を考えてもすぐ反例が見つかる。しかし、この反例の図を描いているうちに「最小点カバー」という直観が得られた。

コンテスト中はこの段階で深く考えずに実装してしまったが、マスに注目して条件を観察すれば正当性もすぐわかる。各マスについてそれを監視できるカメラはちょうど二つしかなく、どちらかを設置しなければならない。つまり、その二つを結ぶ辺があって、選んだカメラ=頂点のどれかに接続している状態。これより選んだ頂点は点カバーとなっている。

二部グラフなので最小点カバーのサイズと最大マッチングのサイズは一致する。この事実を使った記憶が以前になく、その点に面白さを感じた。

Exは解けず。ローリングハッシュも値に乱数を割り当てたZobrist HashもXORで壊れてしまう。特に後者が壊れることについては実装が終わってから気づいたため、絶望してしまった。7完20位。Gは最初にマスに注目していれば燃やす埋めるがすぐ思いつけたかもしれない。

コードゴルフ。AはAWK解を提出するまでに10分経過していたため速度差で負けたかと思ったが、最短が取れていた。BはRakuで、各マスを0と1に変換した後列ごとの和を取る方針。2次元のリストの要素を変換するに当たってはメタ演算子Xが使えず、ネストしたリストにも再帰的に適用されるハイパー演算子>>を使う必要があった。Cは今の最短コードを縮められず。以降は手付かず。

しばらく無為にTLを眺めた後、午前2時から日記を書き始めた。午前6時就寝。

10/23(日)

午前10時半起床。

二度寝するつもりだったのにグラフのcutの定義を間違えていたことに気づき眠れなくなった。ちまちま教科書を読んでいたのがやり直しに。教科書の定義はWikipediaでいうcut-setであり、自分は単に取り除くとグラフが非連結になる辺集合だと思っていた。

Cut (graph theory) - Wikipedia

1時間くらい身悶えしたあと布団から脱出。準備して牛越橋に向かった。今日はそこの下の河川敷で競プロサークルの芋煮会を行う。昼過ぎから雨が降りそうなので徒歩。

到着すると、とりあえず火だけ起こされていて、近くに住んでいる人の部屋で具材が準備されるのを待つ時間だった。適当にうろうろしていたら雨が降り出したため、橋の真下に移動。改めて火が用意され、周囲に石を積んでかまどを作りながらさらに待機した。

具材と水が入った鍋が到着し、かまどが不安定なことが発覚。金網も購入されていたものの、その上に乗せても撓んで不穏なだけなので、直火で温めることになった。鍋は二つあったので、火を分割し、それぞれの周りに改めて石を組む。鍋が乗せられるよう思ったより小ぢんまりと作られた。この辺り自分はほぼ見ているだけだった。

鍋を温めている間にかかった費用の清算。大体1万円程度と聞いていたため、先輩風を吹かせ全額出すつもりで用意してきた。金は出すから準備は任せた!という気持ちでいたが、結局その場にいたもう二人のM1、ホスフィンとha15さんとの三分割になったし、その二人は結構準備や持ち込みをしていたため、自分だけ貢献度の低い人間に成り下がってしまった。

このころが一番雨が酷かったはず。橋の下にいるので大丈夫かと思ったら、上に排水口の出口があって大変だった。鍋を温めている位置が真下から少しずれただけの位置で、風の具合によっては見事吹き込んできたため、蓋を開けるときは傘でカバーしながら耐えていた。

煮えたら味を調え、完成。食後は焼きマシュマロをしたり、金網でソーセージや餅が焼かれたりして、お腹一杯になった。うっかりワインも飲んでしまった。

片付けが済んだらすぐ帰るつもりだったが、具材を用意していた部屋に数人集まるらしく、自分も転がり込んでよいようなので、そこからCFに参加することにした。ノートPCは一応持ってきてある。充電も満タンなので、2連戦には十分耐えられるだろう。

午後4時50分からCF #829 div.1。

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

A1はnが奇数なら明らかに不可能で、実は偶数の場合必ず可能。二つずつ見ると、[a_i],[a_{i+1}]とすればa_i+a_{i+1}[a_i,a_{i+1}]とすればa_i-a_{i+1}が達成できて、どちらかは0になる。それを集めてくればよい。A2も間の0を適切に扱うことで同様のことができる。

A1からA2に書き換える際、一か所そのままにしていて1WA。今思えばこの時点ですでにアルコールを摂取したことによる判断力の低下がみられる。

Bはa!a+1個集めて(a+1)!にするのを繰り返せばよい。配列で個数を数えながら計算する。これは簡単。

Cに1時間半かかって何もかもが崩壊した。初手がわからなかったため、手計算でサンプル三つ目のケースを求めようとしたのが間違いだったのか。そもそもこの計算すら失敗しまくって大変だった。最終的に正しい値が得られ、その途中計算をもとに実験エスパー+OEISで解いた。

それぞれの0に対しその前にある1の個数を数えた列を考え、これで状態を表す。サンプル三つ目のケースを解くためにはいくつかの状態に対して答えを求める必要があったが、それらはすべて15または75/4になった。いかにも何かありそうだ。期待値のループを解消したときに出てくる\binom{n}{2}を無視すると、値はnに影響されないようなので、そこだけ観察することにした。

Ruby有理数を使っていろいろ試してみると、15/449/36205/1445269/3600が登場した。まず分母が順にk!^2となっていそう。その時の分子の列は1,5,49,820,21076で、祈るように調べてみるとOEISに載っていた。まとめると、この数列は\sum_{i=1}^k 1/i^2らしい。

A001819 - OEIS

どういう基準でkが定まるのかはエスパー。作った列のうちkより大きな値がk個以下しかない、という条件を満たす最小のkが求めるものらしい。どういう計算になっているのか全く分からないまま実装し、AC。

残り10分ちょっとしかない。Dに進んだ。一応Cで詰まっている間に問題だけは読んでいて、空きマスの移動をグラフと見てdijkstraすればよさそうだとわかっていたものの、ダメなケースがありそうに見えてちょっとまごついていた。まあこの時間がなくても実装は間に合わなかっただろう。そのままコンテスト終了。

489位で2825→2668(-157)。ここ2回で300近くレートを落としている。2600台にまで落ちたのは去年の3月以来のこと。

次のCFまでの時間で少し感想戦を行った。Cは今ある値とソート後そこにあるべき値が異なる位置同士のswap以外無意味らしい。ソートを0だけ先頭に集めると読み替えて、0があるべき位置にある1の個数を減らしていくと見なせば自然だろうか。最初に転倒数を考えたので、そこで01列の転倒数をインデックスの差で計算する方法が思い浮かべば、もしかしたら至れた発想かもしれない。自分は期待値の線形性を利用できないか探るほうに進んでしまった。

素面だったとしても解けたか怪しい気がする。ただ、金輪際ratedの前に飲酒はしないだろう。

帰る人を見送り、15分後からCF #830 div.2。

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

Aからちょっと難しい。i=n-1,nで操作すれば条件を満たせるので、答えは3以下となる。あとは場合分け。Bは01列をソートする問題ということで、先ほどのC問題のトラウマが蘇ってきて苦しかった。連続する同じ文字を圧縮した列で実験して解いた。

Cは難しい。まず、区間を狭めてもXORの減少分が和の減少分を超えることはないため、最大値はf(L,R)となる。あとは区間の幅をどこまで狭められるか。狭めた区間でのfの値がf(L,R)と等しくなるためには、和の減少分がそっくりそのままXORの減少分に一致しなければならない。

とりあえずa_i\gt 0として考えると、区間の幅を狭めるごとにXORの立っているbitが狭義単調に減っていくと言えて、制約のもと幅30も縮めればXORが0になってもう狭められなくなる。よって全探索可能。a_i=0をあらかじめ削除しておけば元の問題でも同様に計算できる。

Dは計算量が謎。深く考えずに出したら通った。どちらもオフラインで解いた。D1はxに対してそれが挿入されたクエリ番号を覚えておき、同じkのクエリをまとめて倍数を調べつつ、クエリ番号を比較して早いクエリからどんどん答えを確定させていった。D2はkをまとめるときにクエリ番号をsetで持ち、倍数を調べるたびそれが集合に入っていない時間帯のクエリを削除するのが高速に行えるようにした。

Eは解けず。遅延セグメント木で、更新を区間の幅に応じて二通りの方法で行った。狭い区間の場合は単に全探索。広い区間の場合はxの約数を全探索し、それが\gcd(x,b)となるbの最小値を探す。後者についてはbの検索部分を前計算できる。ところが全く間に合わなかった。6完12位。

2連戦を終えて残っていたとりゐさんと感想戦。Dは最悪ケースの想像がつかないので計算量がよくわからなかったのだが、やはり小さいほうに詰まっているのが大変そうという結論になった。つまりいつもの調和級数

そろそろ帰るが、その前に部屋をちょっとうろうろさせてもらった。夕方この部屋にお邪魔したときからめちゃくちゃ広いなと思っており、興味に勝てなかった。ハリー・ポッターの本を見つけたので、自分は積んでいるのに「ハリー・ポッターと呪いの子」の話を振ってみたりした。

午後10時くらいにお暇し、コンビニに寄って解散。帰宅後疲れ切ってYouTubeを見ているうちに寝落ちしそうになったため、布団に滑り込んだ。午後11時半就寝。

午前3時に一度起きた。焚き火の煙で燻された服のまま寝てしまったため、布団にちょっと臭いが移ってしまった。とりあえずシャワーを浴びた。

TCB52が終了していた。今回は理論値達成者が多くいたが、そこでは2位に10分以上速度差を付け、全完者の中でも最速の圧倒的勝利。これで3連覇、しかもすべて理論値での優勝となった。最高の気分。

7問目は区間の幅が2以上の場合、LCPがすべて同じ文字になるらしい。気づいてみれば当たり前で、ある文字列とその先頭を削除した文字列の前からいくらかが等しい場合、その部分の文字が全部一致していなければならない。SAなど持ち出さなくても解けたようだ。

upsolve二つ。まず今日のdiv.1-D、やはりdijkstraで解けた。解説を見て正当性を理解。同じsunbetを2回動かしてしまったり、逆に2回動かさなければならなかったりする場合どうするか気になっていたが、そのようなケースはないらしい。2回目に動かそうとした時点でそこに十分なスペースができていることが、手で試せばわかる。

Submission #177691400 - Codeforces

次に今日のdiv.2-E。コンテスト中に試した2種類の更新を使って平方分割したら通った。バケットサイズガチャで4敗。バケットの中で一要素ずつ更新するには\gcdを計算する必要があるので、サイズは小さめがよいかと思ったが、一つのバケットに対して計算するのにもxの約数の個数だけ時間がかかるため難しい。というかなぜ通っているのかわからなくなってしまった。正しくは、各バケットとあり得るすべてのxに対して答えを前計算できるらしい。

Submission #177695805 - Codeforces

午前6時から4時間ほど日記を書いて就寝。

週記(2022/10/10-2022/10/16)

10/10(月)

午後11時起床。30分ほど日記を書いていたが完成するはずもなく、未完成のままメモ書きだけ削除して投稿した。

メモ書きとは時間帯とその時やっていたことを大まかに記録したもの。普段日記を書くときは、まずブラウザの閲覧履歴やTwitterからこれを復元した後、記憶に残っている行動・思考・事物で肉付けしている。このとき日記に書かないことも決めているため、そのフィルターを通さない状態のまま公開する気にはなれないのだ。

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

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

Aからちょっと考える必要があった。並べ替えの操作をするかしないか両方試すことにして、並べ替える場合は0の出現回数または1の出現回数を揃える。片方を揃えればもう片方も揃う。

Bは、a_{i-1}\mid b_iかつa_i\mid b_iよりb_i={\rm lcm}(a_{i-1},a_i)とするのがギリギリで、条件を満たしやすそう。ここから再度aを復元して一致するかチェックすればよい。

C1は(l,r)がgoodなら(l+1,r)もgoodなので、尺取りで解ける。配列サイズをミスして1WA。ただしこの考察はC2ではあまり意味がない。div.2のCだからシンプルに解けるだろうと思っていたのに全く見えず、何か見落としているのかと不安になった。順位表を確認したら全然通されていなかったので、安心して腰を据えて考えることができた。

(l,r)がgoodであることと、l\le\forall i\le rについてa_i\ge i-l+1となるのは同値。ところでi\lt lのとき、i-l+1\le 0\lt a_iよりこの条件を必ず満たす。よってlに対して(l,r)がgoodとなるrの数は、a_r\lt r-l+1となる最小のr(存在しなければn+1)を取ったときのr-lと等しい。

l\lt r+1-a_rと書き直すと見通しがよい。各r1\le l\lt r+1-a_rを邪魔すると言えて、lに対してそれを邪魔するrの最小値は単調増加。今、クエリごとにaの値が一つだけ変わる。もしr+1-a_rが大きくなるならば、対応するrがどこまで新たな最小値となるか二分探索で求まる。

小さくなる場合は、もともとそのrがどの範囲のlに対して最小値となっていたかを、こちらも二分探索で求め、削除することになる。削除後の最小値が知りたいので、最初に計算しておくrを小さいほうから二つ持っておくとよい。

Dのほうが多く通されていたので簡単なんだと思ったのに、初手すらわからなくてびっくり。ただ比較的すぐに解法が「降って」きた。s2i-1番目と2i番目をペアにし、高々1回のrotate操作ですべてのペアについて文字を揃える方針。最初の状態で文字が異なるペアを列挙したとき、これが奇数個だとそもそも01の文字数が異なるため不可能。偶数個の場合、先頭のペアから順に01を交互に取ってbとすることで、rotate後に見事文字が揃う。

EはO(n^3)のdp。ターンごとにスコアに加えられた値は、同じ値が連続するいくつかの区間に分けられて、それを長さ1に圧縮すると元の列aの部分列になっている。よって、次にどの値の区間を作るか、直前にどのターンまで使ったか、余っている操作回数はいくらか、の3次元で表現できる。

区間はまず長さ1とし、後から追加で1ずつ伸ばすことにすれば、状態ごとに遷移が定数時間で書ける。途中で余っている操作回数が負になるケースも計算に含めてしまい1WA。

システスも全部通って全完4位。C2をちゃんと通せたのも、Dで素早く天啓を得られたのも偉かった。

週記に戻ってほとんどの部分を書き上げた。読了したなろうについての感想部分を開けた状態で一旦更新。もう一度編集ページを開き、そのまま書き続けて完成させようとしたが、睡眠時間と明日の予定を鑑みて早々に切り上げた。午前5時就寝。

10/11(火)

正午起床。木曜日のチュウニズムのアプデでトンデモワンダーズが収録されるらしい。かなり好きな曲なので最高。

今週からセミナーが火曜開催になる。準備して山に向けて出発した。セミナー開始前に購買で昼食を買うのと、履修登録について教務課で行うべきことを一通りやっておきたい。後者は先週やろうと思っていたのに家から出られなくてできなかったこと。

他研究科の集中講義で面白そうなものがあった。ぜひ受講したいが、調べても日程が出てこない。そもそも履修登録の方法についても教務課に問い合わせる必要がありそうなので、早めに一回話を聞きに行く必要がある。

週記(2022/09/26-2022/10/02) - kotatsugameの日記

購買は12時45分までだから先にそちらに、と思ったら、教務課も12時45分から昼休みだった。ダッシュでパンと飲み物を買った後、教務課に滑りこんでとりあえず必要な書類を受け取った。セミナーの合間に記入して、あわよくば提出したい。

とりあえず教室に向かって午後1時からセミナー。最初は同級生の発表。集合とその上の二項演算の組(M,\mu)、いわゆるマグマについて、K,S\in Mであって\mu(\mu(K,x),y)=x\mu(\mu(\mu(S,x),y),z)=\mu(\mu(x,z),\mu(y,z))を満たすものが存在すれば、ラムダ計算っぽいことができるというのが面白かった。

ラムダ計算っぽいことというのは、変数x_1,\dots,x_nと定数が入り混じるどんな式に対しても、f\in Mが存在して、その式と\mu(\dots\mu(f,x_1),\dots x_n)が一致するということ。\muを関数適用だと思えばそれはそうなのだが、これまでと見方が違うように感じられて新鮮だった。

2時間半ほどで終了。ちょっと休憩をお願いして教務課に駆け込み、いくつかの質問と書類提出をした。他研究科の集中講義の履修について、結論から言えば、可能だが日程はわからないので文学部のページを定期的に確認せよとのこと。以下にURLを記録しておく。日程がわからないのはちょっと怖いものの、困ったら落とせばよいしと履修認定願いを出した。

講義・履修 | 東北大学 大学院文学研究科・文学部

この履修認定について、単位を卒業要件に含められるか否かはまた別の問題らしい。例えば僕が前期で取った講義のうち工学研究科で開講されていたハードウエア基礎は、学務情報システムから確認した限り卒業要件に含められないタイプの履修となっていた。認定願いでは含めてくれと言っておいたのにこの仕打ちは聞いてないんだけど……と遠回しに尋ねたら、システムのほうが間違っている可能性があるので成績証明書を見ると確実と言われた。どれくらい単位数が必要なのか計算が狂ってしまうので、近く確認しておきたい。

教室に戻って、今度は博士課程の方の発表。n\times nの対称行列Sに対し、n\times 1の列ベクトルuu^{\rm T}u=1のもと動かしてu^{\rm T}Suを最大化するという話が出てきた。Sの最大固有値が最大値になるらしい。なんとなく見覚えがあるだけで詳細がわからないため、そこまで踏み込んだ解説をしていただいた。ラグランジュの未定乗数法を用いるのだが、それすら忘却の彼方にあり、今日はここの説明だけで時間を使い切ることに。申し訳なさがある。

午後6時過ぎ終了。山の下の学食で食事して帰宅。

実は今日はインターン先の定例会があった。月曜日が祝日だったためずれてきて、セミナーと被ってしまったのだ。会議を覗いてみるとまだ勉強会の途中だったので、そこから30分ばかり参加した。チームマネジメントの話。メンバーにより多く意見を述べてもらう方法論は、自分の卑近な体験とも通じるところがあったので、そこに注目しながら聞いていた。具体的な質問を投げかけると良いらしい。

勉強会を終え、再度外出。ゲーセンに行く。今日は新しく解禁した曲を詰めるだけの日で、そのうち三つについては手元動画を撮った。またチュウニズムデュエルを終わらせた。かなりギリギリになってしまったが、今週木曜日に迫ったアプデ前にやり残したことはもうない。

午後11時過ぎにゲーセンを離脱。帰宅してシャワーを浴び、午後11時半からCF #826 div.3。

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

Aは文字列を数字に変換するのがよさそう。M0にし、他は文字列の長さを絶対値としてSLで符号を切り替えるとうまく比較できる。Bはn\ge 4なら2だけrotateすることで常に達成可能。n=2,3はサンプルにある。Cはsegmentごとの和として\sum_i a_iの約数を全探索。調べるべき数が十分少ないので、判定には毎回O(n)かけてよい。

Dはボトムアップに計算するのが楽。ノードごとに操作するかしないか、どうしようもないかは一意に定まる。Eはdp。長さが前に来ている場合は配る遷移、後ろに来ている場合は貰う遷移で対処する。

Fはちょっと時間がかかった。色に対して値を持つ区間MAXのセグ木を使う。ここは上位2種類だけ管理することで線形時間に落とせるはずだが、面倒だった。区間(l,r,c)に対し、l'\le rかつc'\ne cなる区間(l',r',c')であってr'が最大のものを求めると、\max(l-r',0)が答えの候補になる。lrの役目を入れ替えてもう一度同様の計算をし、小さいほうを出力すればよい。

Gは大変時間がかかった。解法はbitDPだが手数が多いし変数の扱いもややこしい。各hに対して1\rightarrow hの最短経路がpたちのどんな部分集合を巻き込めるか調べる。これは1と各h_pから全点に対する距離を求めておけば計算できて、巻き込みたいp1\rightarrow h_pの距離順にソートして順に辿るときの距離と、1からストレートにhに向かうときの距離が等しくなればよい。bitDPの遷移を行う前にこの判定を計算すればO(f(2^kk+3^k))が達成できるが、自分は判定しながら遷移するO(f3^kk)で解いた。

全完8位。FGでの失速が痛い。Cは一つ目の区間の長さを全探索してもよかった。

上にツイートを貼った手元動画はコンテスト後に投稿したもの。その後コードゴルフしたりハーメルンの更新をチェックしたりした後、先週の週記の昨日書き残した部分を完成させた。なろうの印象に残っている部分をリストアップするためとはいえ、ページを開いたのにサッとチェックするだけで終わるわけもなく、かなりじっくり読み返してしまったため午前8時くらいまでかかった。その後就寝。

10/12(水)

午後5時起床。なろうを読むのとチュウニズムのアプデ前公式生放送を見るのを繰り返していた。午後9時過ぎに寝落ちし、日付が変わったあたりで再度目覚めた。

www.youtube.com

自分がTAをしている講義は、先生が用意したpdf資料を分担して発表するセミナー形式で行われる。発表に用いる原稿あるいはスライドについて、講義前日までにClassroomに投稿されれば先生とTAでコメントをつけるということになっていた。初回の発表は明日なので、いつ投稿されてもいいようにメールや通知には気を配っていたが、結局寝ている間にも来ていない。

ところがClassroomを開いたらちゃんと午後5時くらいに投稿されていた。通知を見るだけではなく、しっかりページを確認しに行かなければならなかったようだ。確かに前日までに投稿されているので、コメントをつける必要がある。しばらくその作業をしていた。本当はこんな時間にTAに関する作業をしてはいけないらしい。

その後はなろうを読みふけっていた。午前6時に1作読了。「設定鍵インベントリア:シャンフロの諸々」。

https://ncode.syosetu.com/n6458eg/

先週読了した「シャングリラ・フロンティア〜クソゲーハンター、神ゲーに挑まんとす〜」の番外編や設定を集めたもの。掲示板回が読めてよかった。本来は投稿日を確認して本編と並行して読んでいくべきだったかもしれないが、しかし一度最新話まで読んでからこちらに触れる利点もあって、設定で伏せ字にされている部分がところどころ理解できるのが面白い体験だった。こんな昔から練られていた設定なんだなあと感動することが多い。

本編の2回目にプロゲーマーと対決する場面、509部分に「ヴィランが律義にエレベーターでビルを昇る」というギャグがある。これ単体でも面白かったのだが、実は1回目の対決中のシーンを下敷きにした天丼ネタだったということを知った。当時の本編には描写がなく、掲示板にのみ言及があった。

履修登録を済ませた後、指導教員の先生から依頼された、講義で使用するスライドのチェックを行った。チェックといっても誤植を見つけるだけ。ただ70ページ弱あってそれなりに時間がかかった。

午前10時半に布団に入り、ハーメルンを開いた。原作カテゴリに「シャングリラ・フロンティア」が存在するのを見つけ、試しに検索してみると、253件もあってひっくり返った。一つ選んで読み始め、2時間くらい経ったところで就寝。

原作:シャングリラ・フロンティア - ハーメルン

10/13(木)

午後3時半起床。TAのため大学に向けて出発。

まず成績証明書を発行した。火曜日に言っていた確認作業のため。結局学務情報システムから見るのと同じ状態、つまり工学研究科で開講された講義は卒業要件に含められない状態になっていた。せっかく頑張ったのにという気持ちはあるものの、まあ数学専攻なのにハードウエア基礎の単位で卒業するというのもよくわからないから、理解はできる。内容も自分の興味に近く、無駄になった気はしていない。今期取った講義もいくつかはこういう扱いになるのだろう。2年次ではちゃんと専門科目から単位を集めるようにしたい。

5限、TA。スライドを映すために自分のノートPCを貸したら、Ubuntuに入っているPowerPoint互換ソフトでは数式がうまく表示されないらしくて、結局先生のMacを使うことになってしまった。この切り替え作業で少し時間を食ってしまったのが申し訳ない。

発表は細部が丁寧だし堂に入っておりびっくりした。90分まるまるやりきるというのも含め、昨日スライドをチェックした時に感じた以上に、非常によく準備されていた。1年生ということで正直ちょっと舐めていたかもしれない。

残った5分で、先生に言われて途中の定理の別証明をサッと紹介し、終了。このとき発表の内容に関する補足も無理やり差し込んだ。本当はポジティブなフィードバックも含めたかったが、TAがどれくらい出しゃばってよいのかわからない。

学食で食事して帰宅。しばらくコードゴルフして、午後7時半に布団に入った。昨日読み始めたハーメルンを読了。「シャンフロ掲示板シリーズ」。

syosetu.org

主人公のスキルや挙動が外野にすぐ解説されてしまうのはちょっとモヤっとするが、それがなければただすごいすごい言うだけになってしまうので仕方ないのだろう。バランスはなかなか難しそうで、本家に比べて違和感があるのも当然か。それらを加味しても、掲示板回がたくさん読めるというだけで十分にうれしかった。

本編512部分、プロゲーマーとの対決2回目の決着は、意表をついて現れた子供NPCを見てプロゲーマー側が硬直するというものだった。いくら驚いたからといってそんなに動きが止まるか?と思っていたが、そもそも操作キャラの設定に子供NPCの泣き声で硬直するというものがあったのを、掲示板の言及で思い出した。その設定は182部分の後書きに書いてあったもので、本編を読んでいるときは忘れてしまっていた。

同じ原作の別の作品を開いて少し読んでみたが、恋愛をピックアップしたものなので気分に合わず、投げ出した。

午後8時半から3時間ほど仮眠していた。起きてすぐCF #827 div.4。

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

ABはよい。Cは横線がR、縦線がBと決まっていることが重要。横一直線のRがあるかどうかで場合分けする。Dは毎回O((\max a)^2)かけて計算する。このあたりですでにジャッジが詰まり始めていた。

Eは左から累積MAXを計算してその上で二分探索。Fはta以外の文字があるか、sa以外の文字がなく、stより短い場合のみYESとなる。a以外の文字を含むかどうかと文字列の長さをそれぞれ管理した。

Fを提出したときにDがサンプルで落ちているのに気付いた。a_i\lt a_jのケースだけ考えていたが、a_i=a_j=1もOKであるのを見落としていた。再度提出。

Gは累積ORが増えるタイミングが高々30回しかない。よって、累積ORが数列全体のORと等しくなるまで、残っている要素を全探索して最大にできるものを先頭に置くのを繰り返しても間に合う。

全完5位。Dのリサブで+9分となり残念。ただサンプルで落ちてくれたため、ペナがつかなかったのだけはラッキーだった。

結構長い間TLを見て時間をドブに捨てていた。MHC Tシャツを注文したというツイートが流れてきたのでメールを確認すると、自分のことろにも商品に関するメールが届いていた。ただしソーシャルのタブに入っていたので、ツイートが目に入らなかったらそのまま気づかなかった可能性もある。危ないところだった。

午前4時から日記を書き始めた。朝方になって一瞬だけインターン関連のコーディングを行い、午前10時に布団に入った。しばらくラノベを読んで正午ちょっと前に就寝。

10/14(金)

午後3時の直前に起床。すぐさま1on1。

昨日寝る前の一瞬で実装したものについては、その時に出力が期待通りであることまで確かめてあったので、今日はそれをお見せして新しいタスクの話をするだけだと思っていた。しかし改めてコードを確認すると盛大に書き間違えている。慌てて修正して実行すると、なんと出力が変化してしまった。これまで期待通りの出力をしていたのにそこから変化したというのは、今のコードが正しくないということに他ならない。

原因に全く心当たりがないので自分は早々に絶望してしまったが、今は大本となるコードを実装された方と1on1している。無事問題のある部分を見抜いてくださった。幸い修正も簡単で、すぐに正しい出力が得られるようになった。あとは来週のタスクについて話し合って終了。ペアプログラミングすることになったので、ちゃんと睡眠を取ってはっきりした意識で臨みたい。今日は寝起きだったので最初口が回っていなかったような感覚がある。

サークルに参加するため外出。大学の教室に着いてすぐバチャに参加した。6問目までは特に言うことがない。7問目はそれなりに苦労して30分程度でAC。ちゃんと参加したはずの、しかもそれほど古くないコンテストの問題なのに、どうやって解いたか全く記憶になかったが、実はこれは新規ACだったらしい。AGC045-C。当時はBと心中したようだ。

https://kenkoooo.com/atcoder/#/contest/show/9b2231e9-0635-4e29-a602-81cd00cac55d

Submission #35638627 - AtCoder Grand Contest 045

A\ge Bとなるようswapしてよい。ある01文字列が操作後としてvalidであることと、1B文字以上連続する箇所を全部0に揃えた上で0A文字以上連続する箇所があることは同値。0が連続する箇所を固定することで重複を取り除く方針が思い浮かぶが、かなり大変そうなので、条件をチェックしながら文字列を先頭から構築することにした。

現在0が何文字連続しているかを状態に持つ。その次に0を置くのは簡単。1を置くときが問題だが、連続する1をまとめて置くことで対処できる。それがB文字未満ならこれまで連続していた0の文字数はリセットされる一方、B文字以上ならリセットされず、さらに今置いた1の文字数が追加されるのだ。

どこかのタイミングで0A文字以上連続したことがあるかのフラグと、直前に置いた文字が01かのフラグを持って、状態数O(N^2)で遷移がO(N)のdpが書けた。この段階で一度サンプルを試すと合っていたので、いよいよ遷移を高速化する。といってもこの部分は簡単だった。dp配列に対して横や斜めの区間加算になったので、imos法を使えばよい。

しばらく感想戦を行った後、学食に寄らず帰宅。木曜日に仕送りの冷凍食品が届いて冷凍庫が満杯になったため、土曜日の冷凍弁当配達までに少しでも消費しておく必要がある。食事して午後8時から仮眠。

ちゃんと目覚ましは午後9時過ぎにかけてあって、一度意識を取り戻したことは覚えているが、yukicoderに出ようというモチベーションが足りず起きられなかった。次に目を覚ますと日付が変わっていた。幸い今日のコンテストは4時間もあるので、遅ればせながら参加。マラソンのA問題以外は時間内に解けた。

yukicoder contest 364 (Do you know Cherry Contest?) - yukicoder

Bは単にcinで受け取ったため最初の単語しか読めていなかったが、判定を先頭1文字で行ったため難を逃れた。

Cはちょっと難しい。A日後に行く回数を決め打つ。A日後にB回行くのとB日後にA回行くのは相殺できるため、T\lt 0の場合はB回以上、T\ge 0の場合はB+\lceil T/A\rceil回以上のケースを考えなくてよい。よって全探索可能で、この範囲ならオーバーフローも起こさない。T\ge 0の場合上限が大きくなることに気づかず1WA。

Dはよい。EはL\le i\le RについてD\lt T_iならA_iT_i\le D\lt T_i+A_iならA_i+T_i-D-1T_i+A_i\le Dなら0を足し合わせればよい。クエリをDの昇順に答えることにすれば、セグ木に値をセットしたり削除したりすることで計算できる。Fはローリングハッシュ。法が一つだと落ちたので三つ使った。このあたりいつも適当に増やしている。

コンテスト終了後に解説を確認した。Fの法は二つあればよいらしい。

snuke.hatenablog.com

しばらく日記を書いた後、ラノベを読み始めた。1冊読了。「最凶の魔王に鍛えられた勇者、異世界帰還者たちの学園で無双する」3巻。

面白かった。開幕早々大勢の前で主人公が自分の実力を見せつけるシーンがあり、一気にテンションが高まる。その結果で周囲から噂されるような描写こそなかったものの、その後も自重せずに能力を振りかざすバトルシーンが多く、大変楽しかった。ただ外面の順調さとは裏腹に、主人公の考えは良くない方向に先鋭化している。そのうち致命的に破綻しそうで少し怖い。やられ役のセリフにもそういう状態を揶揄するものがあり、そこだけは単純に主人公の無双を楽しむ気持ちにはなれなかった。これまで自分が思っていた敵味方の区別がラストの展開であいまいとなり、意表を突かれた。これからも楽しみ。

また日記に戻る。午前10時半ごろ、今日の終わりまでほとんど書き上げた段階で布団に入った。そこから少しハーメルンを読んで、午前11時過ぎに寝落ち。

10/15(土)

午後3時起床。冷凍弁当を受け取った。かなり苦労したが何とか冷凍庫に押し込むことに成功。1時間ほどハーメルンを読んでからまた寝た。

午後8時半起床。食事して午後9時からABC273に出た。

Panasonic Programming Contest 2022(AtCoder Beginner Contest 273) - AtCoder

AはN!を出力する。Rakuで書いた。1\dots N演算子*でfoldする……のだが、N=0のとき空集合をfoldすることになると気づいていなかった。幸いそのようなケースは単位元として1を返してくれるらしい。

Bはi=0\dots K-1の順に10^iの位の値を取得して四捨五入する。CはAを昇順にソートして、各iに対してi\le jであってA_j\lt A_{j+1}となるjを数え、それをKとした場合の答えをインクリメントした。

Dは面倒。mapとvectorで行・列に対してそこにある壁を順に並んだ状態で持つと、その上で二分探索することで、移動先にある最も近い壁を十分高速に求められる。

Eは永続化データ構造をあまり知らないので身構えたが、末尾の要素に注目することを思いついたらかなり簡潔に解けた。ADDクエリで追加された要素について、その直前の要素がなんであったかというのは以降絶対に変わらない。また直前の要素さえわかればDELETEクエリに対応できる。これら2種類のクエリは数列の末尾の要素だけ管理しておけば対応できるし、出力も行える。このことから、SAVEとLOADは末尾の要素が何かという情報だけ扱えばよいこともわかる。

Fは座標を全部まとめてソートし、区間dpをすればよい。状態数O(N^2)、遷移は左右に1広げるだけなので定数時間で行える。原点にゴールや壁、ハンマーがある場合について少し考えたが、制約から座標の絶対値が1以上なので気にしなくてよい。

G。R_i=1なるiの個数をr_1とおく。同様にr_2,c_1,c_2も定める。r_1+2r_2\ne c_1+2c_2なるケースは先に弾いておく。

C_i=2なる列に置かれた値の和は2c_2となるが、それだけで和がR_iになるという条件を満たした行が、R_i=1についてx行、R_i=2についてy行あったとする。二つの変数が満たすべき条件は0\le x,yx+2y\le 2c_2x\le r_1y\le r_2に加え、残ったz=2c_2-x-2yr_2-y行に割り振るためz\le r_2-yも必要となる。

まずx,y,z行の決め方が\binom{r_1}{x}\binom{r_2}{y}\binom{r_2-y}{z}通りある。次に、先にc_1の割り振り方を決める。2c_2を割り振った後、r_1-x+z行が残り1、r_2-y-z行が残り2を必要としている。ここをc_1列の1で満たす必要がある。残り2の行を二つに分け、一旦割り振り方をc_1!通りとした後、改めて2^{r_2-y-z}で割れば場合の数が求まる。

本題の2c_2の割り振り方についてはdpで求めた。割り振りたい値が2iあって、そのうち2jj行に2ずつ、残り2i-2j2i-2j行に1ずつ割り振る方法を数え上げる。(i,j)を状態とすれば遷移は2の行と1の行のどちらにどれだけ置くか決めるだけなので定数時間で行える。必要なのは(i,j)=(c_2,y)であった。以上を全部掛け合わせたものを、すべてのx,yに対して足し合わせれば答えとなる。

ExはStern-Brocot treeなど検索してみたものの手も足も出ず、終盤20分くらいはコードゴルフをしていた。7完8位。

コードゴルフ。Aはdcだと上手く書けなかった。今のところ最初に提出したRakuが最短となっている。Bは後述。CはRubyで書いたものの、Perlからbashを呼び出すほうが短くなるらしい。朝方になって、bashからPerlを呼び出すことでさらに1B縮んでいた。EはAWKで縮めたが改善点がいくつかあって負け。他は手付かず。

Bについて。コンテスト中の方針は10のべき乗を使ってXを操作する方針だったが、dcだとXを10でどんどん割っていくほうが短い。dcでループを書こうとすると再帰を使うことになるので、行きがけに10で割った分帰りがけに10を掛けるというのが簡単に行えるから。ところがもっと短い方法が見つかった。Xに5をK個並べた数を足し、10^Kの倍数になるよう切り捨てても答えが求まるようだ。そのコードを弄ってみたら1B縮んだので、今は自分が最短となっている。

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

Dashboard - Codeforces Global Round 23 - Codeforces

Aは1がどこかにあればよい。数列の長さがkになるまでその位置を避けつつ1番目の操作ができて、最後に2番目の操作をすれば達成される。

Bはほとんどの要素が0か1のままになりそう。操作後の数列における0と1の境界を、操作によるずれも加味しつつ元の数列の境界として戻してみると、そこより左の1はすべて操作によって削除され、右の0はすべて操作によって1以上になるか削除されている。この境界を全探索する。

左の1をx個、右の0をy個とする。まずx回の操作で左の1を削除し、できるだけ多く右の0を1にする。x\ge yのときは余ったx-yを右端の要素に押し付け、x\lt yのときは残ったy-x個の0をさらなる操作によって削除することで、いずれにしても\max(x,y)回の操作で広義単調増加にできる。全部0か全部1の場合は押し付けたり削除したりできないことがあるが、境界を全探索しているので問題ない。

Cは転倒数を0にできるはず。すべてのiについて、a_i-a_{i+1}以上の値をi+1から始まるsuffixに足すことができればよい。N\dots 1の順に、a_i-a_{i+1}が大きなiに当てはめていけばできそうだったので、証明せずに提出した。

Dはメモ化再帰。葉でない頂点uに対しそこをi回通る時の答えを求めるには、uの子の数をcとして、uの子すべてについてi\leftarrow\lfloor i/c\rfloor,\lceil i/c\rceilとしたときの値が求まればよい。iの変化から、各頂点についてikを何かで割って切り捨てたものと切り上げたものの高々2種類しか考えなくてよい。ここでうっかり\lceil i/c\rceilではなく\lfloor i/c\rfloor+1を使うと、パスグラフのときに2乗オーダーになってしまうらしい。まったく意識していなかったので、引っかからなかったのはただ運がいいだけ。

ここまで順調に解いて20分。しかしなんと、残り全部の2時間かけてもE1が解けなかった。別の問題に目を通したわけでもなく、4完303位で2949→2827(-122)。その後E1をupsolveした。

二分探索したいが、2分割すると全然情報が得られない。よって3分割することを考えていた。何回か聞くことで1/3または2/3にできればよい。前者なら8回、後者は2回が使える上限となる。嘘をつかれるタイミングを全探索して必死に実験していたのに、ここに致命的なミスがあった。

そもそもこういう問題は、直前までのクエリの結果を見て何を聞くか決めるべきなのである。なので固定した8セットあるいは2セットを探索していては見つかるものも見つからない。苦し紛れに5回のクエリで2/3にする方法を発見し、手で場合分けすることで最短2回で確定させるものを実装したが、ジャッジがadaptiveのため通るわけもなかった。このあたりでようやく、聞くものを動的に決めるべきだと思い至ったはず。

解法1。そうやってうまく聞けば2回か3回で2/3にできるらしい。常に3回かかった場合クエリが2回ほど多いように見えるが、通っている。

10/17追記:3回聞いた場合は集合のサイズが必ず\min(|B|,|C|)だけ減るので、n=|A|+|B|+|C|が3で割って2余る数だった場合、|A|=\lfloor n/3\rfloor|B|=|C|=\lfloor n/3\rfloor+1と分割することで普段より少し多く減らせる。実際に実験してみると見事に81回となった。

解法2。実は2回で2/3ではなく3/4にするのでもよい。A,B,C,Dと4分割してA\cup BA\cup Cを聞くことで見事に分離できる。最後に残った3個の候補を2個にするには、先ほど述べた5回で2/3にする方法を使ってもクエリが足りる。こちらを実装して通した。

つまり4分割することさえ思いつくことができていれば、固定した2セットを毎回聞くので十分に対応できたのだ。候補が2個になるまで減らすには3分割だよなあとばかり考えていて、最後微妙なところだけ別で処理しようという気にならなかった。それに、2/3にするにしてはクエリ回数2回が合計82回に比べてかなり余裕ある値だとも意識できていなかった。ダメダメ。

布団に突っ伏してラノベを読んでいたら寝落ちしてしまった。午前5時前のはず。

10/16(日)

午前9時前に起床。二度寝するかしないか迷いながらもラノベを開き、そのまま夕方までずっと読書を続けていた。3冊読了。

「アストラル・オンライン」。微妙。ストーリーがあまり面白く感じられず、主人公の設定が「シャングリラ・フロンティア」と似ていることにばかり目が向いてしまった。これはその2作を連続して読んでしまったのも運が悪かった。

「凶乱令嬢ニア・リストン」。面白かった。普通にバトルする話だと思っていたら、主人公がテレビっぽいものに出演し始めてびっくり。そういう展開があることはイラストやあらすじを見ているだけでは全然わからなかった。好みの展開なのでこのサプライズは嬉しい。

「君と紡ぐソネット」。面白かった。受験数学に焦点を絞るため、数学教育が偏重された世界という設定を加えるのがアクロバティック。登場人物の名前に数学用語が含まれていてニヤニヤしていたが、よくよく見ると日本人数学者の名前も使われていた。普通の苗字なのでしばらく気づかなかった。主人公は数学で点は取れないものの、考えるのが好きだから理系に進んだらしい。その進路の決め方はかなり勇気があると思った。

主人公たちが取り組んでいる問題の一部は実際に本文中に登場する。1行2行で記述できる問題ということで、ほとんど整数論の問題だった。競プロで鍛えた典型力を使うとホイホイ解けてしまうので、それに苦戦しているキャラを見るとじれったい気持ちになったが、その分成長して解けるようになってくれると開放感があった。以下のツイートにある説には同意できる。一問、解けると言っても結構頑張って計算する必要があった答えが、見方を変えると一瞬で求まったのにはしてやられた気持ちになった。

作中に競技プログラミングへの言及があってびっくりした。受験数学と競プロがそれほど関係しているとは思っていなかったが、今どきはOMCもあってかなり界隈が近くなっているのかもしれない。

その後3時間ほど日記を書き、午後9時からARC151に出た。

AtCoder Regular Contest 151 - AtCoder

AはS_i=T_iなる箇所はなんでもよいため0を入れておくのが最適。S_i\ne T_iなる箇所はどう決めてもSとの距離が1増えるかTとの距離が1増えるだけなので、そのような位置が奇数個ある場合はUを作れない。偶数個の場合どう決めるか迷ったが、後ろから貪欲にするのがよい。あらかじめ全部0を入れておいて、後ろから見てSとの距離とTとの距離の差が縮まるときだけ1に置き換える。

Bは辞書順で大小関係が定まるインデックスiを固定して考える。A_i\lt A_{P_i}かつすべてのj\lt iについてA_j=A_{P_j}となる場合の数を求めたい。等しいとされた要素の関係をUFで管理し、A_i=A_{P_i}となってしまう場合は除いておく。UFの連結成分数をcとすればc\ge 2であり、A_iA_{P_i}の決め方はM(M-1)/2通り、残りはM^{c-2}通りとなる。掛けて1\le i\le Nで足し合わせれば答えが出る。

毎回powを使ってM^{c-2}を求めるのが重いかなと考え、M^Nに適宜1/Mを掛けていく実装にした。しかしM=998244353のケースでRE。なぜM\lt 998244353という制約になっていないのか……。

Cは実験。両端に書かれた値が等しい場合、異なる場合、片方の端がマス目の端である場合、両端がマス目の端である場合と4通りの状態が考えられるので、それぞれ間にある空きマスの数に対応したGrundy数を求めてみた。ほとんど0か1になってちょっとビビるも、自分の実験コードが正しいことを信じて提出したら通った。ちなみに最初は前二つの状態だけ実験していて、その時は本当に0と1しか出現しなかったのでかなりの割合で自分のミスを疑っていた。

D。とりあえず一つのクエリにおける操作がゼータ変換っぽい形式になることは分かった。何かしらの変換を施した状態で列を管理すれば更新すべき要素が少なくなったりしないかと考えるも、うまくいかない。サンプル1を手で試していたら、クエリの順番を入れ替えても答えが同じになりそうだと気づいた。(X,Y)が同じクエリをまとめて遷移するのはできるので、実装。サンプル2も合ったもののWAだった。

そんな感じで1時間くらい使ったが解けなかったため、Eに移った。こちらはそれなりに素早く解けた。XからYに移ったとき、元のXで残っている部分があるかないかで場合分け。残っている部分がある場合は、その部分をZと置くと、Xから要素を削除してZZに要素を追加してYと遷移するのが最適。操作回数はP+Q-2|Z|となる。このようなZとしては最長共通連続部分列を取るべきで、SAとLCPを使って求められる。

残っている部分がない場合は必ずP+Q回以上かかっているので、XYに共通する要素があるならそれを残して操作するべき。よって後はXYで要素が一切共通しない場合を考えることになる。このとき、Xとしてはできるだけ短い状態でいたほうが自由に動けて嬉しいはず。空列は許されていないので、長さ1の状態と長さ2の状態を交互に取ることになると考えた。

つまり、初手でXから1要素選んでそれ以外を削除した後、長さ2の状態と長さ1の状態を交互に取ってYに含まれる1要素だけの列となり、最後にYを復元するのが最適。長さ1の状態から別の長さ1の状態に遷移できる条件は、使った2要素がAの中で隣接していることである。よってAを用いてグラフを作り、Xに含まれる要素からYに含まれる要素までたどり着くまでの最短経路問題を解けばよい。

Dに戻ってきた。よく見るとXが同じでYが異なるクエリの順番を入れ替えているのはまずそう。そこで、Xが同じクエリだけまとめて遷移することにした。Yに応じて値がどのように変化するかは、一組の(j,j')に関して係数を前計算しておけばわかる。それを2^{N-1}ペアに適用すればよい。出したら通った。

20分余ったがFのsolved数が絶望的。すぐ縮みそうな問題もないし、特に何をするでもなく時間を過ごしてコンテスト終了。5完38位。

午後11時半からCF #828 div.3に出た。

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

Aは同じ数に対応する文字が同じかチェック。Bはちょっとややこしかった。「最初偶数だった項」と「最初奇数だった項」でそれぞれ足された値を管理すれば、クエリのたびに今の偶奇がわかる。あとはそのような項の数と掛け合わせ、\sum_i a_iと足して答えになる。Cはsにおけるcと同じ文字に対し、それより先にあって最も近いgまでの距離を求め、最大値を出力する。gを一つ探し、そこから逆向きにぐるっと一周すればよい。

Dは最初の状態でどれだけ2べきが足りないか求め、2べきを多く含むiから順番に使っていく。Eはa,bの約数a_x,b_xを全探索し、xとしてc以下で最大のa_xb_xの倍数、yとしてd以下で最大のa/a_x\times b/b_xの倍数を使うことにして範囲の条件を満たすことを確認。a_xとしてありうる数、b_xとしてありうる数はE2の制約でもそれぞれ最大1344個なので、2乗で十分間に合う。

FはMEXをk=1\dots Nで固定。l_l\le l\le l_rかつr_l\le r\le r_rなる(l,r)についてp_l,\dots,p_rのMEXがkとなる、という情報が得られる。中央値がk未満となるのは、k未満の数の個数がk以上の数の個数以上となる場合のみ。前者はk個、後者は(r-l+1)-k個なので、k\ge(r-l+1)-kを満たす(l,r)の個数を求めればよい。丁寧に考えると定数時間で数え上げられる。かなり時間がかかった。

全完8位。Fに20分かけたのが気になる。今考えればlrの範囲はp_i=kとなる位置を含まないように決めているのだから、[l_l,l_r][r_l,r_r]のうちどちらかは、より大きなMEXを考えるとき常に[l_r,r_l]に含まれるようになる。つまり短いほうの範囲を全探索しても線形時間となるため、そこまで苦しい式変形は必要なかった。

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

週記(2022/10/03-2022/10/09)

10/03(月)

午後4時半起床。インターン先定例会が始まっている。飛び起きてオンライン会議に接続した。

先週の進捗は金曜日に産んだ分だけ。小さなタスクをちぎっては投げ、ちぎっては投げと、かなり楽しい期間である。ただし投げてから次にちぎるまでの間で毎回1週間休んでいる。

勉強会はHTTP通信について。原理などの説明があって、最後にコードを書いて実行していた。しかしほとんどのサイトではHTTPで通信するとHTTPSにリダイレクトされてしまうようだ。それはさておき、このリダイレクトというのは実はHTTPステータスコードで表現されており、サイト側ではなく我々通信を試みる側が対処する必要がある状態である、というのにびっくりした。ブラウザを使っているばかりでは、このことは全く意識できない。

午後6時半終了。思ったより早く終わったので学食に行って夕食を摂った。帰宅して先週の週記に取り掛かり、午後10時半ごろ一通り文章が出来上がる。読み返しはまだしていないが、そこまで含めると日付が変わる前には終わらないだろうと考え、先に投稿しておくことにした。

9000ACを突破していた。今年初めは8000弱だったらしい。10か月で1000問、1日3問強のペースと考えられるが、実際は「アルゴリズムと数学 演習問題集」で100問嵩増ししていたりする。

AIでコードを生成する新たなサービスがリリースされ、話題になっている。以下のツイートが面白かった。魔法のようなサービスに見えるのに、実際は入力に特定のコマンドをくっつけて汎用AIに渡しているだけらしい?真偽のほどはわからないが、だとするとアイディア一発でこういうサービスに仕立て上げられるのは夢がある。一方で、こういう自然言語の自由度を利用したインジェクションへの対処は非常に難しそう。画像AIがやっているように、コマンドではなく出力物をチェックするしかないのだろうか。

AI Programmer

30分ほど床で寝てしまったりしつつ、日付が変わってから週記の校閲を始めて午前2時半ごろに完了した。それから朝までかけてラノベを3冊読んだ。

「王様のプロポーズ」3巻。前半のギャグシーンは面白いが今の気分からは微妙に外れているな……と思ってなおざりに読んでしまったものの、ラストはちゃんとバトルしていて良かった。主人公が活躍してくれてうれしい。本のそでにあったコメントで、鬼と炎モチーフの妹が「デート・ア・ライブ」と被っていることに気づいた。色の印象が青と赤で全く違うため、似ているという感覚はない。

「ランジェリーガールをお気に召すまま」1巻、2巻。面白かった。ランジェリーという全く新しい題材を扱いながらちゃんとラブコメしていて良い。主人公が鈍感気味なのも好み。ストーリーの都合上全編お色気シーンみたいになっていて、脈絡なくそういう描写が挟まるより受け入れやすいなと思った。ただ表紙イラストから思い切り下着なので、ちょっと買いにくさは感じてしまう。恥を忍んでこれからも大学生協で買うだろうが。

ちょうど読み終わったくらいでTLにyukicoderのテスター依頼が流れてきたので、引き受けてしばらく取り組んでいた。一通り終わらせ、ゴミを出して布団に入ったのが午前9時。ハーメルンの捜索掲示板を漁って新しいなろうに手を出した。2時間くらい読んで就寝。

10/04(火)

午後7時ごろ起床。先週金曜日に参加したDMOJのコンテストの期間が終了していた。ここに感想を書いておく。

DMOPC '22 September Contest - DMOJ: Modern Online Judge

P1はA_1\lt A_2\gt A_3\dotsA_1\gt A_2\lt A_3\dotsを両方試す。忘れた要素は極端に小さな・大きな値で埋めておけば問題ないので、忘れていない要素が隣り合っている位置のみチェックすればよい。

P2は二人に被せる帽子の色を全探索する。あらかじめ二人からそれぞれBFSすることで、各人についてその人の帽子を交換で持ってくるための手数を求めておける。色ごとに集計し、交換回数が少ないものから二つ保存しておけば、それを用いて答えが求まる。

P3は面白かった。4人を選んだとき、その間にどのような「非」友人関係があれば条件を満たすか全列挙してみると、長さ3のループまたは長さ3のパスがあればよいことが分かった。なのでその個数を数えたい。ループを数えるのは難しいが、これも構わず長さ3のパスだとみなすことで可能になる。個数は0かどうか以外問題ではないので、長さ3のループを3回数えていても全く問題ないのだ。

つまり、次数が2以上の頂点を結ぶ辺を数え上げればよい。真面目に計算する必要があるのは次数が1と2の間で変化する場合だけなので十分高速。隣接リストをsetで管理した。

P4は少し手間取った。単純なdfs全探索で二つ目の部分点まで通ったが、満点解法は全く別の方針。各カードについて、引いたとき右から何番目に挿入されたかがわかる。一番右に挿入されたカードであって最後に引いたものは、十中八九Kのカードだろう。十中八九というのはただの四字熟語であって、本当は1-\left(\frac{K-1}K\right)^Nの確率でそうなる。

さらに右から2番目に挿入されたカードで最後に引いたものもほぼほぼK。これを用いてKらしきカードを確定させていける。求める場所に挿入されたカードがなくなるか、あってもこれまで確定させたカードより先に引いていれば終わりにする。すると、残ったカードだけ用いることでK\leftarrow K-1としても全く同じことができる。これを繰り返せばよい。Kのカードを引き切ってからK-1のカードが初出現したりすると壊れるが、N=100でそんなことはそうそうないだろう。

P5は解けず、しばらく粘ってからP6に進んだ。まず、a\le bのクエリは常に達成可能だから、最後にやることにして無視。その後sの値の降順に見ていく。s=Nなるクエリをbの昇順にソートしてみると、最小のb_iA_N以上で、またそれに対応するa_iは次に小さいb_j以下で……というような条件が得られる。

このもとでs=N-1のクエリについて考えたい。先ほどA_N\le b_i\lt a_i\le b_j\lt\dotsという列を得たが、このうち[A_N,b_i)[a_i,b_j)の部分にはまだ受け入れる余裕がある。つまり、A_{N-1}とのswapでvになったとき、a_i\lt v\lt b_jならば適切なタイミングで操作を実行することでこれまでの状態を壊さずにA_N=a_iをゲットできる。

ここからはエスパー気味。受け入れ余裕のある区間をsetで持って頑張ってみたがWAだったので、その余裕も数値として保存しておくことにした。実装を簡略化すると、最初に[A_i,\infty)という区間区間ADDで追加し、またクエリの度に[b_i,a_i)をデクリメントして負にならないかチェックしたら通った。正直よくわかっていない。

何はともあれ5完。今日確定した結果は全体5位で、レートは2666→2825(+159)と大きく伸びてくれた。当然highest。

布団に横になったまま10時間ほどなろうを読んで、午前5時過ぎに寝落ちしたらしい。

10/05(水)

午前8時前に目を覚ました。かなり眠いがなろうを読むのが止められない。この日は午前8時~午後3時半、午後5時~午後8時、日付が変わって午前1時~午前6時とずっとなろうを読んでいたらしい。微妙に空いた間は寝落ちしていた時間である。

10/06(木)

午前9時半に目を覚ました。布団で二度寝する代わりに1時間ほどなろうを読んでから外出。今日は大学でセミナーとTAの予定。

今週やろうと思っていたことが全くできていないので、どうしても外出しなければならなかった今日でいろいろ終わらせておきたい。まずバイク屋まで歩いて、木曜日から点検で預けたままになっていた原付を受け取ってきた。それに乗って大学に行き、ラノベを購入し、床屋で散髪。

ここでいったん帰宅し、シャワーを浴びて着替えた。切った髪の毛に首筋をチクチクされたままで過ごすのは耐え難い。再度大学に向かい、購買で買ったパンを昼食として午後1時からセミナー。

今日は3時間を半々に分けて二人発表する予定だったが、博士課程の方の発表のみになった。前回に引き続き定理の証明。必要な事実のうちいくつかは紹介されるにとどまったが、簡単な部分は我々も手を動かしてみよと先生に言われた。忘れ去った線形代数にしてやられ続け、大変なことになってしまった。

正則な行列ABについて、{\rm rank}(A-B)={\rm rank}(A^{-1}-B^{-1})となる。これがわからず苦労していたが、なんとA^{-1}-B^{-1}に左右からABを掛けるだけで示せてしまうらしい。A(A^{-1}-B^{-1})B=B-Aで、正則行列を掛けても{\rm rank}が変わらないこと、符号の違いは無視してよいことから従う。

その後教室を移動して5限のTA。このため、今日のセミナーは山の上ではなく川内キャンパスで行っていた。

今日は最初に自己紹介した後は普通に授業を受けていただけだった。そもそもTAとは最前列に座っているものなのか?人数が少なく、また今年から始まった講義なので、どういう立ち位置にいればいいのかがよくわからない。自分なりのアシストのつもりで、これからの講義に関する取り決めにあたって粗を潰す質問をしたりしてみたが、これも先生と馴れ合っているだけに見えるのかもしれないと考えてしまう。

授業後、先生の所に質問に来られた方が自身のPCにPOV-Rayをインストールするのを見守っていた。午後6時半くらいに完了して学食へ。夕食を摂った後、そのままゲーセンに行くことにした。

アプデで消える要素の回収のため、それまでに2回くらいはゲーセンに行っておきたい。

週記(2022/09/26-2022/10/02) - kotatsugameの日記

アプデで消える要素のうち楽曲削除に伴って取得できなくなる称号を回収。アップデートの度に有志が作るリストとにらめっこしながら2時間くらいかけて完了した。金の曲名称号とマッチングを要求するものは残っているが、そこまで集める気はない。

残り時間は手元を撮りながらX7124のSSSを狙っていた。しかし実際のところ、終盤が下手くそすぎて噛み合い待ちのレベルですらない。運指をちゃんと組まなければならない。

あとは理論値を2譜面出した。閉店まで遊んだ後、立ち食いそばを食べて帰宅。手元動画をツイートしたりメールをチェックしたりTUPCのテスター作業っぽいことをしたりして、午前2時半に布団に入った。そこから3時間なろうを読んで寝落ち。

10/07(金)

午前9時半起床。TLで面白い切り抜きが流れてきた。1回聞いてもわからないが2回聞くとわかる。ちゃんと動画で2回流されているのがありがたい。あまりにもマッチしていて最高だった。

ABC270の賞金、10万円分のアマギフが届いた。

全完3位、日本人2位で賞金10万円。

週記(2022/09/19-2022/09/25) - kotatsugameの日記

5時間ほどなろうを読んでいた。布団から脱出し、30分ほどインターン関連のコーディングをして、午後3時から1on1。

30分の間に思ったより進捗を産めなかったため、今日は特に話すこともないなあと思っていたら、その辛うじて産んだはずの進捗すら正しくない始末。ただし原因を探るとライブラリの噛み合わせの悪さに行き当たって、これは自分一人では解決できなかっただろうなという気持ちになった。そういう意味では、ろくにコーディングが進まないまま1on1に突入したのは実は幸運だったのだろうか。

終わってから外出。まず生協に行ってラノベ購入。実は09/27に出荷メールが届いた本の入荷メールが届いていない。発売日は09/30なのでその問題ではなく、同時に出荷メールが届いた他の本はすでに購入してあるので、輸送の問題でもない。そのうち届くだろうと楽観視していたが、発売から1週間経ち、さすがにこちらから何かアクションを起こすべきではないかと考え、店員に確認してみた。

なんと店の棚に並べられていた。その本だけ自分が予約したという印が外れていたらしい。見つかってよかったとニコニコしながら会計してきたが、やはり不特定多数の人の手に触れたということでちょっと気になってしまう。この件から得るべき教訓は、入荷メールを信用するべきではないということ。実は入荷メールは生協側が手動でチェックして送信しているらしいのだ。やはり人は間違える生き物。

競プロサークルが活動する教室へ向かう。上のようなゴタゴタがあって少し遅刻しながらバチャに参加した。後ろから解いたら最初の問題でかなり詰まってしまった。

https://kenkoooo.com/atcoder/#/contest/show/0290894f-f978-40e7-a718-69075354c6e3

終了後は感想戦、それに加えてTUPCの作問の話も飛び出て結構な長丁場になった。終わったのが午後7時半で、ギリギリ学食が閉店してしまっているので、そのまま帰宅。

午後8時から3時間ほど仮眠を取り、シャワーを浴びてCF combinedに出た。

Dashboard - Dytechlab Cup 2022 - Codeforces

Aはちょっと面倒。文字をカウントし、それを削りながら先頭からできるだけMEXを大きくしていく。このとき、最大のMEXを達成するために必要な文字以外の文字、つまりn/k文字のうち残りの文字のことを考えないのが楽。最後に余っているものを割り振ればよいし、そもそもそこを真面目に構築する必要はない。

Bはr以下の個数からl-1以下の個数を引いて求める。rについてだけ述べよう。\lfloor\sqrt x\rfloor=nとなるような数n^2\le x\lt(n+1)^2のうちnの倍数であるものは、n^2n(n+1)n(n+2)の三つ。これはnによらないため、r以下の個数を求めるに当たって1\le n\lt\lfloor\sqrt r\rfloorに対する個数は簡単に求まる。それ以外は愚直に三つそれぞれr以下か判定。

Cは大変。手で実験すると、初期状態のL字を保ちながら2マスずつ移動することができるらしい。ただコーナーケースとして、L字が盤面の角にあるとどうしようもない。この場合はそのL字から縦横に盤面の端を沿うマスにだけ辿り着ける。実装の際は、盤面を90度回転させ続けて特定の向きのL字にしか反応しないようしたため、その後が少しだけやりやすくなったと感じる。

Dは辺の端点を辺に沿って動かせると解釈する。答えとなるパスに辺が2本以上含まれるなら、そのうち連続する2本に対し1手かけて1本にしても損しないため、最終的には1nを直接辺で繋いで通るだけになる。このとき使う辺を全探索。入力に自己ループがないので操作の途中でも自己ループを作ってはならないと思い込んでしまい、しばらく考え込んでいた。

実際はそんな制約はないので、単に使う辺の端点をそれぞれ1nに持っていくまでかかる手数+1を辺のコストに掛けたものが答え。二つの端点をそれぞれ独立に持っていくか、どこか1点に片方だけ持っていき、1手かけて自己ループを作ってから持っていくかという方法がある。あらかじめワーシャルフロイドで頂点間の移動にかかる手数を求めておき、辺ごとにO(n)かけて最小の手数を求めた。

Eは結構すぐに正解の方針にたどり着いたのに、合わせるのに時間がかかった。蟻の向きをR\dots RLという形の連続部分列たちに分解すると、まずこれが合体して一つの蟻となり、さらに左から順にマージされていくことになる。この元で、それぞれの蟻に対し、その蟻がそれより左の蟻を全部吸収できる場合の数を求める。まず自分自身が右端の蟻であるかLである必要があり、また自分を含むR\dots RLの長さがそれより左にある蟻の数以上でなければならない。自由度を数えて2べきで求まる。

あとは右から順に、自分より右の蟻に吸収される場合を引いていく。自分もLなので、先ほど述べた十分な長さのR\dots RLに自分が引っかからないほど遠くにある蟻になら吸収されうる。ただしこの時、自分を含むR\dots RLに必要な長さのせいで自由度が減っているので、その分の係数を掛けながら引く必要がある。ここで1WA。そもそもnが大きいときにi=1に対する答えが0にならないので、提出する前に気づけてもよかった。

ここまでそれなりに時間がかかっていて順位はあまりよくない。FもGもsolved数がかなり少なく、両方読んで考えてみたが手も足も出なかった。システスは全部通って5完55位、レートは2969→2949(-20)。

そこから12時間ほどなろうを読み、午後2時前に就寝。

10/08(土)

午後4時半ごろ冷凍弁当を受け取った。また眠る前に、ちゃんとアラームをかけたかなと時計アプリを開いたら、アラーム音が小さすぎるとポップアップで怒られてしまった。ウィンドウのそれっぽい箇所をタップしたら自動で音量調整がされたらしいが、元がどんなだったか覚えていない。ちゃんと起きられるだろうかと一抹の不安を抱えながら二度寝した。

午後8時起床。とんでもない音量で飛び起きることになった。いつも耳元にスマホを置いて寝ているので直撃を食らい、しばらく心臓がドキドキしていた。音量はまた小さくしておいた。

30分ほどなろうを読んでから布団を脱出。食事して午後9時からABC272に出た。

AtCoder Beginner Contest 272 - AtCoder

AでN個の入力を求められてびっくりした。そういうものは出ないと聞いていた気がするが、時代は進むということだろう。びっくりしただけで問題自体は普段と比べても簡単。Ruby 16B、Raku 17Bを提出しておいた。ちなみにABC-Aで可変個の入力を要求するのは実は初めてではなく、ABC022-Aという前例がある。こちらはちょっと面倒な問題。

A - Best Body

Bは愚直に判定。これを提出した後、ふとA問題に戻ってdcで書いてみたら15Bができてしまいびっくりした。Cは偶奇で分けて上位2個を取る。Dは平方根を前計算した後BFS。遷移は行を決め打つO(N)で行った。

Eはちょっと詰まった。よく見ると[0,N)に収まる値以外はMEXと関係しないため、これだけ注目すればよい。i番目の要素がその範囲に収まるのはO(N/i)回だから、全部列挙することができる。FはS+S+T+TSuffix Arrayを計算。LCPがN以上の区間に分けて計算することでf(S,i)=f(T,j)なる場合に対応した。

Gは大変。A_i\equiv A_j\pmod MならM\mid(A_i-A_j)なので、(i,j)を全探索して約数を見ることで候補は絞れる。しかし間に合うわけもなし。Mとして素数だけ考えることにしてもダメそう。しばらく考えて、Aの全ての要素が相異なることから別の方針を考えた。M=pだったとすると、差がpの倍数であるような数が\lceil N/2\rceil個存在することになる。つまり\max A-\min A\ge(\lceil N/2\rceil-1)p。一方\max A-\min A\le 10^9-1なので、pとして考える必要のある値はある程度小さいのではないか。

チェックを線形時間で行うことにすると、N\ge 50もあれば十分間に合いそう。N\lt 50の場合は、最初に言っていた(i,j)を全探索してA_i-A_jの素因数を列挙する方針が使える。この二つを組み合わせた。しかしWA。pとして見る範囲が少し小さかったので直したが、変わらず。ここでM=4の場合に対応できていないことに気づいた。これを付け加える。

素数を列挙したvector4を追加。このvectorが昇順に並んでいることを仮定した実装だったのでそれに合わせるためにsortしたら、ギリギリTLEしてひっくり返ってしまった。ちゃんと列挙のタイミングで挿入するようにしてAC。ちなみに線形時間でのチェックは、出現頻度を配列でカウントするもの。Mが小さいからこそこういうことができるのであって、N\lt 50の場合はここに\logをつける実装になっている。

40分残したもののExはさっぱりわからず、途中からコードゴルフに逃亡してしまった。7完36位。Gは乱択らしい。

今回のA問題について、「ABC-Aでループを使う想定解はダメなのでは」と話題になっていた。以下のツイートをうっすらと覚えていたのもあってコンテスト中にびっくりしていたのだ。まあもう5年も前の話だし、上でも書いたように時代は進むんだなあというのが一つ。またそもそも入力ですら本質的にはループを回して文字を読んでいるからして、sum関数で一発の今回も、関数内に隠蔽されているので制約を違反しているとは言えないというのが一つ。まあ、普通に考えれば前者を理由とした出題だろう。

コードゴルフ。Aはdc 15Bが提出時間で負けているうえ、後から14Bに縮みすらした。Bは面倒そうな見た目をしていたが、コンテスト中にすでにゴルフされており、特に縮みそうな隙もない。CはRuby。要素を昇順に見て、直前に出現した偶奇が同じ値との和を求め、その最大値を出力。Gは想定解通りの乱択をRubyで。約数列挙は商列挙のテクを使うと短い、が、その周りで改善があって負け。他は手付かず。

Gの改善について。Rubyではa./b+1とメソッド呼び出しの形で演算子を書くことで、この例だとb+1を引数と解釈させて括弧を省略するテクがある。つまりこう書くとa/(b+1)になるのだ。ところが、これを使う周りでいくつかの文をまとめるために()を使っている場合、そこに(b+1)を押し込むことで縮む。他にもいくつか適用できる問題があったらしく、しばらく取られたり別の改善で取り返したりしていた。

しばらくなろうを読んで午前2時からMHC R3。

Meta Hacker Cup - 2022 - Round 3

Aから難しい。最大値を持っているプレイヤーを探し、それに対して他のプレイヤーがどのような行動をするか考えることで解こうとしたのが最初の方針。例えば、最大値を持っているプレイヤーがA1だった場合、他のプレイヤーは自分の持つ一番小さいカードを出すだろう。B1だった場合、A1の最大値に被せるように出すべきで、残りのプレイヤーは先ほどと同様。ただしA2B2が持っていた場合の行動がよくわからない。それっぽいものをいろいろ試してみるも、validationでずっと落ち続けていた。

方針を変える。一人ずつ順番に、全部のカードをN/4ゲームでどのように使うか決めることにした。まず、このままだと相手チームが得点してしまうゲームをできるだけ多く自分チームの得点に変える。次に、余ったカードで、自分チームが得点するゲームであってカードの最大値が小さいものを優先的に大きくする。いかにもそれっぽさはあるが正当性はわからない。とにかくvalidationには通ったのでそのまま提出した。コンテスト開始から1時間だった。

Aで詰まっている間に順位表をチラチラ見て察した通り、Bは簡単だった。すべてのtrie木で作れるすべての文字列に対し、それを答えに含むような三つのtrie木の選び方を数えて足し合わせる。ある文字列を表すノードが存在するtrie木は一つとは限らないので、全部vectorに持って、そのvectorを状態としてBFSする。いかにも重そうだが、BFSの過程で出現するすべてのvectorについて、その要素数の総和がノードの個数の総和で抑えられる。速度的には全く問題なく、無事提出。

また順位表を見て、D1に進んだ。とりあえずマージテクで色の変化は追えそう、では判定は……と考えて、「隣り合う二つの杭の色が同じになったタイミング」を全部求められることに気づいた。自分がどの集合にいるかを、色とは独立して代表元という形で記録しておき、マージテクで値を移動させつつ隣り合う杭と同じ集合に入ったか判定するのだ。実はこれを要求する問題をCFで見た覚えがある。探したが見つからなかった。

あとは適切な位置を飛ばして値の\maxを取ればよい。D2もほとんど同様に解ける。飛ばす場所が(N-1)/K箇所しかないため、K=1\dots Nで和を取ってもO(N\log N)。よってセグ木に乗せてチマチマ値を削除したり戻したりしつつ全体の\maxを計算するのがO(N(\log N)^2)となって十分高速。

1時間ちょっと時間を余らせてCに進んだ。VWのペアを全探索して異なる位置をSuffix Arrayで計算するO(NQ\log( (N+Q)L))の解法と、Wと文字が異なる位置2か所を固定してハッシュで一致判定するO(QL^2\log N)の解法が思い浮かんだので、ケースごとに軽い方を使えば解けそうだと信じて実装。しかし時間ギリギリで書きあがったのにサンプルが合わずお手上げ、そのままコンテスト終了。

出したものは全部通ってABdD、76位。Cを通せていてもペナ差でFinalには遠かった。上位200位には入ったので、Tシャツが少し特別になるのは楽しみ。Cは両方から1文字ずつ変えると考えればよいらしい。なぜ思いつかなかったのだろうか。

2時間なろうに意識を吸い取られた後、日記を書き始めた。今週は本当にずっと布団でなろうを読んでいたので何も書いていない。

1時間半ほど取り組んだところで集中力が切れ、うっかりまたなろうを開いてしまったのが運の尽き。ちょうど読んでいた章のクライマックスに入って、ただでさえ興奮しているのに急に「生配信」という自分のストライクゾーンど真ん中の設定が放り込まれて、夢中になって読み進めてしまった。「シャングリラ・フロンティア」の「謳えスカイスクレイパー:下」。この作品に今週の自由時間すべてが捧げられようとしている。

https://ncode.syosetu.com/n6169dz/

そのまま日記執筆に帰ってくることなく午後1時半就寝。

10/09(日)

午後8時起床。食事して、少し日記を書いて、午後9時からARC150に出た。

AtCoder Regular Contest 150 - AtCoder

Aは方針を間違えるとドツボにはまり込みそうな見た目をしている。連続するK文字をN-K+1通り全部試して、条件を満たす方法がただ1通りであるかチェックすることにした。連続するK文字に0を含まず、それ以外の文字に1を含まなければよいはず。0の個数と1の個数の累積輪を計算しておいて判定。提出したら通って安心した。

Bは難しかった。k(A+X)=B+YとおけばA+X+B+Y=(k+1)(A+X)となる。この値を最小化すればよい。Y\ge 0より、B\le k(A+X)を満たす整数k\ge 1X\ge 0であって(k+1)(A+X)を最小にするものを探すことになる。例えばX=0のとき、k=\lceil B/A\rceilとするのが最適。この値が十分小さければ、kをそれ以下の正整数として全探索することができる。ではB/Aが大きなときは?

今度はXを全探索できるようだ。Xを固定してkを調整し、B\le k(A+X)をギリギリで満たしたとき、B+A+X\le(k+1)(A+X)\lt B+2(A+X)となる。ここでX=0を考えることで、求める値はB+2A未満だとわかる。X\ge Aのとき(k+1)(A+X)\ge B+A+X\ge B+2Aよりそのような値はどうやっても取れないので、0\le X\lt Aで全探索することになる。以上でO(\min(A,B/A))=O(\sqrt B)で解け、十分高速。

Cは最初、パスが絶対に通らないといけない頂点ということで関節点のことを考えていたが、さすがに500点にこれが出るわけはないと信じて軌道修正。結局Bのどの要素まで出現したかを距離とする01BFSになった。そもそも今の場合頂点に割り当てられた値に重複があり得るため、関節点に注目しても解けないはず。

Dは初手だけは良かったがその後で大失速。各頂点について、その頂点がよい頂点となるまでに選ばれる回数の期待値を求めて足し合わせることにする。これは深さだけが重要となって、深さ1の頂点は1、2の頂点は3/2になるらしい。サンプル1から深さ3の頂点は11/6になるべきで、この値がどのように求まるのか気づくまでに非常に時間がかかった。

自分と親の計3頂点しか考えなくてよい。その3頂点のうち自分以外の頂点が最初に選ばれる確率は2/3で、そのとき残り選ばれていない2頂点を両方選ぶまでの話になるから、深さ2の頂点に対する結果3/2を流用できる。自分が選ばれた場合が問題。自分が黒であるという状態での期待値を文字で置いて遷移を考えたら解けた。

先ほどと同様、次に選ばれる頂点の深さで場合分けする。自分以外の頂点が最初に選ばれた場合、また残り2頂点を両方選ぶ話になって、ただし今回は「深さ2の頂点」かつ「自分が黒」である場合に対する結果を使うことになる。手計算すると1であった。そうでない場合は同じ状態に戻ってくる。求める期待値をEとおけば、E=2/3\times 1+1/3\times(1+E)よりE=3/2。自分が白の場合に戻ると、結局深さ3の頂点に対する期待値は2/3\times 3/2+1/3\times(1+E)=11/6と計算できて、確かにサンプル1と合致する。

深さと自分が白か黒かの状態をこのように浅いところから計算しておいて、あとは頂点の深さに対応する値を足し合わせればよい。実装は非常に短くなった。

Eはよい性質が全く見えず、4完48位。Aはやはり場合分けの方針を取ると地獄を見るらしい。Dは実は深さdの白い頂点と深さd+1の黒い頂点に対応する値が一致していて、それを用いて式を整理すれば深さdの白い頂点に対応する値が\sum_{i=1}^d 1/iとなった。なるほど11/6=1+1/2+1/3は何回か見たはずなのだから、感づけるべきなのかもしれない。

コードゴルフはD問題のみ。Ruby。深さを計算する配列と期待値を計算する配列を分けず、常に(d,1+1/2+\dots+1/d)を組にして持つとかなり短くなった。配列アクセスが長そうに見えて、結局親の値のみを参照して自分の値を決定できるため、その親の値を最初にアンパック代入すれば解決。

YouTubeを見ていた。内容はしょうもないSSなのに、それっぽいセリフをやたら上手い声真似で読み上げるので完成度だけは高くて面白すぎる。「この後のあんまり有名じゃないパート」に言及しているのも好感度が高い。スカイピースさん、というかミームの元ネタ一般に対するリスペクトが感じられる。

www.youtube.com

TUPCのテスター作業をした。木曜日の深夜の続きで、今日は実際にコードを書いた。午前2時からは日記に着手。溜めてしまった分を頑張って書きつつもしばしばなろうに気を取られていた。

午後6時、ついに読了。「シャングリラ・フロンティア〜クソゲーハンター、神ゲーに挑まんとす〜」。閲覧履歴から復元したところ、日記を書き始めてからの14時間のうち9時間くらいはなろうを読んでいたらしい。月曜日の深夜に読み始めたもので、他の日と合わせてだいたい66時間ほど費やした一気読みだった。

https://ncode.syosetu.com/n6169dz/

最高に面白かった。全体的な印象としてはやはり主人公のハイテンションさが心地よい。本編から外れて謎のゲームを始めたりしたときもだれることなく読み進められたのは、その主人公の溌剌とした様子がどこでも変わらずに見られたからだろう。以降は印象的なシーンを記録しておくので、少しネタバレ注意。

まず「見上げた空、広がる海、深淵の都市を駆けて」章のプロゲーマーと対決するところ。最高。VRMMOモノのリアル描写が好物なのに加え、真にプレイヤースキルだけの勝負で全一と渡り合う主人公の強さに感動。さらにバトルの展開も劇的だった。特に177部分は読んでいて身震いした。

次に「竜災未だ止まず、狼は吠える」章のクライマックス部分。初のPvP、しかも人前で戦うということで、これまで巨大なモンスターに挑んできたのとは全く異なるバトルが展開されて楽しい。周囲のガヤが少し描写されているのは僕の嗜好とマッチしている。このバトルに言及した掲示板回があったらもっと最高だった。

さらに「響けグレイトフルレガシー」章のプロゲーマーと対決するところ。また?と思われるかもしれないが、こちらは前に紹介したものとは趣向を変えたバトルをしつつも定期的にバトルの外側視点が入るということで、さらに最高になっていた。主人公がヤバい挙動しているのが、驚かれつつ解説されているのは良かった。非常に。

最後に「謳えスカイスクレイパー:下」章クライマックス。主人公が考察クランに対しバトル動画を共有するために生配信することになる。ただしプライベート配信ということでそれほど目立ちそうになく、ちょっとがっかり。しかし蓋を開けてみれば、配信の設定ミスでパブリックのままバトルが開始した!ベッタベタなミスだがもはや何でも良い。VRMMOと生配信が二つ揃ってまさに最強。その配信を見たいろいろな視点からの描写が続いて、これまでこの作品で摂取できていなかった栄養素を完璧に充填することができた。

それでいて、真にクライマックスのバトルに入ると外部の描写が一切取り除かれ、展開や演出の格好良さだけで魅せられた。描かれないだけでこれが配信されていることはずっと頭の中にあり、そのためこれまでとは違い主人公を画面の向こうに見ているような少し変わった没入感があって、これはこれで最高だった。ちゃんとラストに掲示板回があって、感謝の涙を流しながら舐めるように摂取した。

最後と言ったが、もう少し。本当に最後……というか最新話近くのネタバレになる。「誰そ彼の蛇」章ラストで主人公の愛用してきた装備のいくつかがプレイヤーキラーに取られてしまい、かなり気分が沈んでしまった。そのストレス展開を回収したのが833部分から835部分。命乞いを言わせておいて全く斟酌しない、それも「で?」とか「だから?」みたいな中学生のような態度ではなく、そもそも人の話を聞いていないというスタイルが最高にスカッとした。

「誰そ彼の蛇」章ラストは主人公の負けイベントだった。上に書いたような展開のほかにももう一つ悲しいことがあり、それは812部分と819部分で回収されている。こちらは手垢がついた方法での演出だったが、むしろそれくらいストレートなほうがより心にじんと響いて良い。

以上!序盤はほぼ毎日投稿の上作者のテンションによっては1日に2回3回と更新されていたのが、最近はメディアミックスでお忙しいのか更新が途絶え気味で悲しい。上のようなストレス展開がちゃんと回収されていたのは救い。そういうのを残したままエタられると数日落ち込んでしまう……。

その後も日記を書き続けていたが、眠気で頭が回らなくなってきたので、ところどころ未完成なまま午後7時就寝。

週記(2022/09/26-2022/10/02)

09/26(月)

午後4時半起床。インターン先定例会が始まっている。布団から飛び起きて会議に接続した。

今週の進捗、というか稼働状況は、勉強会スライドを作っただけ。先週やると言ったことに全く手を付けられていない……。今週こそ頑張りますと言って終了。勉強会は自分の番。質疑応答含め1時間半ほどの発表で、午後7時前に終了した。その後スライドを公開した。

勉強会0926.pdf - Google ドライブ

今日のテーマは文字列の列のソート。長さの総和にだけ制約がついているような文字列たちを辞書順でソートするとき、どういう計算量になるのか調べた。よくあるシチュエーションだが、初めて出会ったとき本当に間に合うか心配にならなかっただろうか。僕はちょっと戸惑ったことを覚えている。結局何も考えずにソートして間に合うので、そういうものだと捉えていた期間が長く、具体的な計算量とその証明方針を知ったのは結構後になってからだった。

列の長さをN、文字列の長さの総和をSとするときO(S\log N)でソートできることを、代表的なソートアルゴリズムであるマージソートクイックソートで証明した。解析がしやすいアルゴリズムなので結構簡単。ところがstd::sortでは証明できなかった。大まかな話はスライドに書いたが、後からリプライを頂いて、ヒープソートというよりはそのGCC実装が解析しにくい形になっているのが原因だと理解した。各要素のヒープ上で移動する回数を抑えられず、下のツイートの計算量解析が成り立たないのだ。

なぜそんな変な実装になっているかの理由付けもしてもらった。一般のケースではいかにも高速になっていそう。

発表に対するコメントで、文字列ソートの定数倍高速化について面白い話を聞けた。比較するときに勝手に求まるLCPを保存しておくと速いというのだ。例えばマージソートだと、ソート後に隣接する要素間のLCPが求まっていて、これを使うと次回のマージで先頭いくらかをスキップできる可能性がある。クイックソートはLCPでバケツソートすると単に2分割するより細かくできる。普通に比較していて求まるようなLCPが、確かに使いやすい値になっていた。

日付が変わるまで日記を書き続けていた。日曜日を勉強会の準備に充てたため土日の分がまるまる未完成だった。そんなことは先週の時点で分かっていたのだからもっとしゃかりき書いておけば良かった。夏休みの宿題を溜める癖は今になっても治っていないということだろう。宿題はぶっちぎることができるが、週記はそうもいかない。甘えればすぐ途切れてしまうから、自分をよく律さねばならない。

午前0時の直前になっていったん投稿。まだ微妙に書き足りない部分がある。とはいえ疲れた。集中が切れたので、ラノベを読み始めた。しばしばTLを眺めつつ、午前4時半に1冊読了。

「お隣の天使様にいつの間にか駄目人間にされていた件」7巻。文化祭。6巻の夏休みと同じく好きなシーンもあるし展開的には好みなのだが、頻繁に挟み込まれる主人公とヒロインの甘いやり取りにちょっと飽きが来てしまった。両片思いは好きなのにくっついたらあとは興味が離れていくだけとは、なんとも業の深い嗜好である。

また週記に戻って、書き足りない部分を完成させた。読み返しを一切行っていないが今日はここまでにしたい。明後日水曜日の来客に備えて部屋の掃除とゴミ出しを行い、しばらくPCでハーメルンを読んでから布団へ。TLを眺めていたら寝落ちしたらしい。午前9時半だった。

09/27(火)

午後7時起床。もう遅い時間だが今日はゲーセンに行きたい。準備していざ出発、と思ったら、日曜日にAmazonで注文したものがもう全部届いていた。お金を出してお急ぎ便にしただけはある。開けて冷蔵庫に入れたり段ボールを片づけたりしたら午後8時半になってしまった。

食事をスキップして閉店まで目一杯遊んだ。今日は新曲を埋めた後手元動画を撮影していた。成果としては理論値+1。OPがついに99%台に乗った。

ラーメンを食べ、日付が変わってから帰宅。手元動画を投稿した後、しばらくYouTubeで時間を溶かした。

CF #823 div.2のE問題を解説を見ながらupsolveした。数列の最小値か最大値を固定するという方針は明らかで、最小値に対してその倍数を全探索すると数列が1ばかりの場合にTLEするが、最大値に対してその約数を全探索すると十分少ないという話らしい。この事実はあまり意識したことがなかった。あとは区間の両端としてありうる範囲をそれぞれ絞り込む。前計算も実際に求めるのもそこそこ面倒だった。

Submission #173748947 - Codeforces

午前5時から先週の週記の校閲を行っていた。3時間ほどかけて最後まで目を通し、完了。その後しばらく日記を書いて午前10時くらいに布団に入った。しかしそこからノクターンノベルズを読み始めてしまい、就寝が午後1時前になった。明日は夕食を外で食べ、その後部屋に帰ってきて家飲みの予定。

09/28(水)

午後4時半起床。準備していたらたいぺーが部屋に来たので、店まで一緒に行くことにした。午後5時を過ぎてから悠々と出発したら、店が思ったより遠くて10分ほど遅刻してしまった。

今日は成龍萬寿山という中華料理屋。5品でかなり満腹になった。ツイートの写真に写っている順に水煮肉片、チンジャオロース、海老チャーハン、コーンスープ、杏仁豆腐。水煮肉片はホスフィンが注文した料理で、程よい辛さが非常に美味しかった。中華のコーンスープは、小さいころコーンポタージュだと思い込んで注文してがっかりした覚えがあるが、今ではどちらも好物である。

ドンキでおつまみやお酒の割り材とボードゲームを買い、帰宅。昨日届いたお酒を並べて飲み始めた。

買ってきたボードゲームは「Gobblet Gobblers」と「Blokus」で、どちらも二人用の対戦ゲーム。三人でプレイできるボドゲというのはなかなか難しかった。

「Gobblet Gobblers」は面白かった。基本的には3\times 3のマルバツゲームを駒で行う。ただしこの駒は大中小とあり、既に置いた駒を動かしたり、より小さな駒を覆い隠したりできる。普通のマルバツゲームと同様に考えれば、初手は中央に絶対に覆われない大の駒を置くのがよいはず。すると以降取れる手が二通りくらいしかなく、人力で解析できそうに見えたが、さすがにそんな単純なゲームではなかった。初手の最適性も謎だし、実は見落としている手があるかもしれない。

Blokus」は難しかった。相手からの浸食を完全にブロックしようとすると窮屈になるし、盤面がかなりスカスカになってしまって面白くない。自陣の隙をなくすよりは敵陣の隙をつくほうを積極的にするべきらしかった。このあたりが自分は下手くそ。

その他音MADやネトフリを見ていた。今日は自分を含め全員疲れていたようで、午前2時くらいにはみんな横になってしまった。自分は床で寝落ち。午前3時頃にたいぺーが帰宅する気配で一旦目を覚まし、見送った後布団に入って再度寝直した。

09/29(木)

午前6時、ホスフィンの起床とともにこちらも目を覚まし、二人で1時間くらい後片付けをした後帰宅を見送った。

昼前までずっとYouTubeを見ていたらしい。この動画が面白かった。ラストで急にピザを配り歩き始めたため、ゲリラ的に他ライバーとのやり取りを目の当たりにできて得をした気分になった。

www.youtube.com

しばらくラノベを読んでから原付で外出。学食は外まで人が並んでいたので諦め、生協でパンを買うにとどめた。その後ガソリンスタンドで給油し、バイク屋に点検のため原付を預け、徒歩で帰宅。またしばらくラノベを読んで、午後3時半ごろに寝た。

午後10時半起床。グダグダ時間を潰して午後11時半からECR136。

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

Aはn=1またはm=1のときは(1,1)、それ以外は(2,2)を出力した。Bはa_i=a_{i-1}+d_iとすれば1通り復元できるため、それ以外の方法があると-1になる。具体的には、d_i\ne 0かつa_{i-1}-d_i\ge 0なるiがあるとき。

Cはちょっと面白かった。まず先手がnを持っている場合は先手必勝。そうでなくて、後手がnn-1も持っている場合は後手必勝。このどちらでもない場合というのは、後手がnを持っていて先手がn-1を持っている場合となる。すると、この二つを組にして無視することができて、先手後手を入れ替えたn-2の場合に帰着される。

Dは二分探索。根からdfsするとき行きがけに辺を付け替えてしまい、WA。なぜなら、根に近い頂点のほうが少ないため、辺の付け替えはできるだけ浅いところで行いたいから。帰りがけに付け替えるようにしたら通った。

Eは非常に難しかった。左の列からdpしようとしたが、直前に掃除したマスの行を持つ方針だと、どのマスを掃除してはいけないのか正確に管理し続けるのが辛い。考え方を変えると非常にシンプルになった。行の移動を必要になる列でのみ行うことにすると、例えばある列で上から下に移動した場合、その次の列では上の行にあるマスを掃除できない。逆にこれさえ守っていれば良いようで、直前の列で行の移動を行ったかと今どちらの行にいるかを持つdpで解けてしまった。

Fは解けず、5完24位。

朝までずっとラノベを読んでいた。2冊読了。

「クエスト:プレイヤーを大虐殺してください」。非常に面白かった。VRMMOで暗躍する系の話は、「黄金の経験値」しかり、かなり好み。そもそも暗躍する主人公が好きだし、その上VRMMOということもあってあまり責任とか倫理とか考えなくてよいような気持ちになれる。1巻ということでゲームを始めるところからスタートしたが、大多数とは異なる行動をした主人公にだけ発生したイベントもあってスムーズに成長し、すでにいい感じに謎めいた強力なキャラとなっていて楽しかった。ゲームとして不平等じゃないか、などは考えないようにすべし。

「無気力ニートな元神童、冒険者になる」。主人公の勘違いが行き過ぎていてちょっと肌に合わなかった。そういう意味で振り切れているので、特徴的ではあったか。

午前9時就寝。

09/30(金)

午後1時半起床。午後3時から1on1があるため、それに向けて進捗を産む必要がある。1時間くらいグダグダしてからようやく取り掛かったが、ほんの数行書き足すだけで終わったので、30分で何とか形になった。これを持って1on1へ。

議論しながら少しずつコードを変えていったのだが、そのたびに不等号の向きを取り違えたりインデックスを間違えたりとバグを埋め込み続けてかなり大変なことになった。実質ペアプログラミングみたいな状態だったからこそ気づくことができたバグたち。出力がどうなってほしいかをあまり把握できていなかったため、一人だったらこんなものかと納得してしまった可能性がある。ともかく、これでまた小さなタスクが一つ片付いたため、次のタスクを振ってもらった。

1on1が終了したのが午後4時40分で、直後からサークルのバチャに参加した。自明四つ、覚えていた問題二つで、最後の問題は頑張って考察した。

解説の前半は同じステップを踏んだが、共通部分の長さの2倍だけ減ることが分かればこの時点で解ける。iに対してA_{i-1}を記録しておき、A_iを昇順に見てより小さい要素に対する記録を削除することで、A_i=\min(A_l,A_{r+1})のときの\max(A_{l-1},A_r)の最小値が区間MINによって求まる。

https://kenkoooo.com/atcoder/#/contest/show/239f29f1-3a23-4fc3-b019-8e081f9b9f13

バチャ終了までは解説をチェックして過ごし、その後通話を繋いで感想戦。除算の除数が定数の場合と変数の場合の速度差についてなど、1時間ちょっと喋って終了。

仮眠しようと布団に寝っ転がったが、あまり眠くなかったのでしばらくラノベを読んでいた。1冊読了。

「英雄と賢者の転生婚」2巻。主人公とヒロインのイチャイチャは今の気分に合わないので微妙だが、それ以外はよかった。1巻で登場した高慢ちきなかませ犬的キャラがまさか主人公グループに入るとは。相変わらず一皮むけば気風のいい男で、好感度は高め。この巻では主人公グループの主人公・ヒロイン以外のキャラのバトルシーンが多く、やはり主人公に無双してほしい自分としてはその点はちょっと残念だった。

午後9時20分になったので、yukicoderの問題を読んでから寝た。星がやたら少ないのが気になっていたが特に詐称というわけでもなかったようで、どれも見た瞬間頭の中では解けた。

yukicoder contest 362 - yukicoder

1時間半で起床。まだyukicoderのコンテストが終わっていなかったので、寝る前に考えた解法を実装した。危なげなく全問AC。ツイートを拝見する限りもっと高難度の問題も用意されているそうなので、コンテストとしてまとめて出題するならそちらも含めてほしかったなという気持ちがある。解説を読んだ感じ、教育的な問題にしようとの意図があるらしく、そこは理解できないこともない。

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

Dashboard - Codeforces Global Round 22 - Codeforces

Aからちょっと面倒。aの値でbXYに分けたとき、|X|\ne|Y|ならX,Yから\min(|X|,|Y|)個ずつを倍にできる。そうでないならどちらかが1個倍にできない。倍にするものは大きな値から貪欲に選ぶ。

Bはまず決定できるa_{n-k+2},\dots,a_nが広義単調増加かチェック。残りのa_1,\dots,a_{n-k+1}はすべてa_{n-k+2}以下なので、この和s_{n-k+1}a_{n-k+2}\times(n-k+1)以下である必要がある。逆にこの不等式を満たせる場合、必要なだけa_1を小さくすることで構成可能。k=1の場合はa_{n-k+2}=\inftyと思えば常に構成可能とわかる。

Cはよくわからない。とりあえず偶数の個数と奇数の個数を数えて、O(1)で判定できる方法を考えていたが、普通にメモ化再帰してよい制約だった。

Dも謎。まずb_1,\dots,b_k\gt kかつb_{k+1},\dots,b_n\le kであるようなkが一意に定まる。後はbが同じ値をまとめ、その値と等しいインデックスを配置した直後に並べればよい。複数ある場合は、元の列が存在するという制約からそのうち高々一つだけが後ろに並べたいものを持っているため、それがちゃんと一番後ろに来るような順番で置く。先頭はb=0またはb=n+1で、これも制約からどちらかしか存在しない。結局kの情報は使わなかった。k=0を見落として1ペナ。

Eは難しいというか面倒だった。右と左から累積和を取って、これが同じ値になる位置で切ればよい。a=0がない場合はそのような位置が高々一つなので更新も簡単。ただ、今はそうではない。そのような区間が交差していない場合は、長さをそれぞれABとすると、切る回数を全探索して答えが\sum_{k=0}^{\min(A,B)}\binom{A}{k}\binom{B}{k}=\binom{A+B}{A}倍になる。交差している場合はさらに一致していることもわかって、間はどこで切ってもよいため2べきを掛ける。端の扱いには注意。

実際はもうちょっとぎこちないことをしていた。\binom{A+B}{A}の部分は手で実験して違う式を得て、さらに閉じた形にしなくても計算量的に間に合ったため、ここまで整理できていない。端の扱いをチェックするにはサンプルが弱すぎてかなり不安になったが、この時点でかなり詰まってしまっていたのでわざわざ愚直と比較する気は起きない。エイヤと出したら通った。

Fはすぐ解けた。次数の降順に聞いて連結成分を作っていく。d_udのうち最大だったとすると、ud_u回聞くことでサイズd_u+1の連結成分ができる。ここの次数の総和は、それぞれの次数を上からd_uで評価するとd_u\times(d_u+1)\lt(d_u+1)^2となって条件を満たす。次に、今使った頂点たちを除いて同様のことを繰り返すが、途中で既存の連結成分が出てきた場合はそれとマージし、その頂点に関しては終わりにしてよい。クエリを投げるたびに連結成分が二つマージされるので、最大n-1回のクエリで解が求まる。

Gはかなり難しかった。どういう風にセルを消せば条件が達成できるのか実験してみると、興味深い性質が見えた。右上から左下に向けてk-1本のマスを共有しないパスだけ残せばいいらしいのだ。より正確に言えば、右上と左下にすっぽり収まる(k-1)\times(k-1)の三角形を作り、斜辺となるk-1マス同士を繋ぐようなパスと共に残す。

これが見えればあとは貪欲で解ける。入力で0となっているマスを全部通ればよいので、パスを左から順番に構築していき、左に進まないと通れない0が存在しない限り下に進むという貪欲が正当。パスはマスを共有できない、つまり交差しないので、一度取りこぼすと取り返しがつかなくなるから。斜めの座標を大量に使う実装方針を取ってしまったので、手元で図を描きつつ丁寧丁寧丁寧にコーディングした。その甲斐あってかなりスムーズにサンプルが合い、残り7分で投げたら通って感動。

システスも全部通り、7完35位、レートは2954→2969(+15)。Eに45分もかけているのがかなり痛い。

今年のTCO Finalsがオンライン開催になったことが発表されていた。参加者に対しては結構前に伝えられており、しばらく秘密にしておいてくださいと言われていたのだ。もうこちらからも言いふらしてよさそう。

2022 Topcoder Open Finals Announcement: Change of Plans — Topcoder Forums

30分後からTCO Finalsに関するオンラインミーティングがあるらしい。

週記(2022/09/19-2022/09/25) - kotatsugameの日記

午前4時から3時間でDMOJのコンテストに参加した。感想は終了を待って、来週の週記に書く。

DMOPC '22 September Contest - DMOJ: Modern Online Judge

昼まで日記を書いていた。布団に入ってラノベノクターンノベルズをそれぞれ少し読み、午後2時半就寝。

10/01(土)

午後8時半起床。9月分の読書記録をまとめてツイートした。積読の増分が3桁になってしまったのにはさすがに危機感を覚える。

午後9時からABC271に出た。

KYOCERA Programming Contest 2022(AtCoder Beginner Contest 271) - AtCoder

Aはdcチャンス!と意気込んだら2桁にゼロ埋めするのを忘れて1WA。また出力が本当に大文字か確認していたのもあって、手間取りながらのACだった。Bはよい。配列の長さを動的に決める練習だろうなとわかる。Cは二分探索。やたら大きなa_iの処理に少し手間取って、もっと簡単な方法があるのではと思ったが、適当に貪欲すると壊れそうだったのでそのまま実装しきった。

Dもよい。Eは面倒そうなことが書いてあるが、整理するとdp_B\leftarrow\min(dp_B,dp_A+C)という遷移をEの順に行うだけでよかった。Fでは一瞬手が止まったものの、何とか半分全列挙を素早く思いつくことができた。いわゆる解法ガチャ。

Gはちょっとややこしかった。N回目のアクセスまでの残り回数と今何時の直前かを持ってdpすると、いつものループがある遷移になる。このループはアクセスの残り回数ごとに独立なので、式変形で解消することで残りアクセス回数が1少なくなった状態から24\times 24の行列で遷移できる。これを行列累乗し、最後のアクセスに関する部分を別に計算することで解ける。

Exは謎。とりあえず適切に反転してA\ge B\ge 0の状態にした。全通りのsに対して各マスがどんな距離にあるかちょっと実験してみると、どうやら(+1,+0)(+2,+0)(+1,+1)という移動の組み合わせで書けていそう。なので、最初にBFSでそれらの移動にかかるコストを調べ、適当に掛け算して答えとしてみた。愚直と比較して合うまで移動パターンを増やすのを覚悟していたが、もうこの時点で一致してしまったので提出。無事通った。

全完6位。上に学生が3人いて賞金は手に入らなそう。Aの1WAがなかったとしても変わらないようだ。残念。

Cはやっぱり貪欲だと壊れる問題らしい。Gはdpのループ部分を解消する際に除算を行う必要があって、この除数がゼロにならないことを一切確認していなかった。ゼロになったら解けないだろ、みたいな気持ちで通してしまった。まだ痛い目を見たことがない。

コードゴルフをした。AはACしたときのdcが最短。BとCはAWK。EはRubyで書いたが負け、Perlでさらに縮んでいる。他は手付かず。

TopCoderに参加する環境を少し整えた。これまでずっとAppletのほうからコードのテストを行っていたのが非常に面倒だったので、手元で完結させたい。今はCodeProcessor、FileEdit、TZTesterというよくあるプラグイン3点セットを使っているので、これをGreedに乗り換えればいいのかと思ったが、それ以前によく見るとTZTesterなのだから今の状態でできてもおかしくない。実際、調べるとすぐ出てきた。

TZTester Home Page

テンプレートにテスト用のコードを追加すればいいらしい。適当な問題でコード生成を試しながら調整し、以下のようなものに落ち着いた。問題文をコード中に埋め込むと、乱数生成の際に定数の補完が効いて便利。しかし手元でこのファイルをコンパイルする場合はその部分のコメントアウトが必要になるので、テンプレートの時点でそうしておいた。これまではコンパイル以降を全部Appletから行っていたので特に問題なかったのだ。

あとはテスト用コードのためにヘッダファイルvectorsstreamをインクルードする必要もある。テストの実行については、グローバル変数が初期化されないのに注意しておきたい。

$BEGINCUT$
/*
$PROBLEMDESC$
*/
$ENDCUT$
#include<iostream>
#include<algorithm>
#include<vector>
#include<sstream>
using namespace std;
class $CLASSNAME${
    public:
    $RC$ $METHODNAME$($METHODPARMS$){
        
    }
$TESTCODE$
};
$BEGINCUT$
int main(){
    $CLASSNAME$ __test;
    __test.run_test(-1);
}
$ENDCUT$

そうやって準備を整え、午前1時からSRM839に出た。

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

Easyは選ぶ人数をあらかじめ決め打つdpで4乗。どこか見覚えがあると思ったら、ABCで出題されていたらしい。まあこの難易度で既出も何もあったものではない。

Medは難しかった。直感的には、各要素に対してその左にあってswapで飛び越えられないようなものを見て、転倒数への寄与を数えればよさそう。ただしこれを達成する過程でうっかり余計なものまで飛び越えてしまい、転倒数が増える場合がないかが心配だった。このことは、値xが飛び越えられる要素はx以下の値でも飛び越えられるということから問題ないとわかる。

最初の状態において、どの位置より左にある要素を飛び越えられないかチェックするときは、stackで見ている位置から左に進んだ時の累積maxの変化点を管理し、その上で二分探索すればよい。stackはランダムアクセスできないので実際にはvectorを使った。セグ木上の二分探索でもよいが、ACLSRMで使えないし、自前のセグ木には二分探索を実装していないので、今紹介した方法を考える手間が発生した。これを前計算しておき、値の大きな要素から順に見てBITを弄ることで、具体的な転倒数への寄与が求まる。

HardはMo。これが1000点はちょっとあり得ない、と舐めてかかったら実装に手間取って点数は低めになってしまった。

30分残して全完。チャレンジフェーズは特に何もせず、Roomでも何も落とされていなかった。しかしシステスで8つも落ちてびっくり。Medで2乗の解を投げている人が二人もいたので、ちゃんと確認しておけばよかった。自分は無事全部通って9位、レートは2785→2807(+22)。最近の傷が深すぎてまだまだ癒えない。

朝まで日記を書いていた。午前7時半から30分ほど椅子の上で眠ってしまったらしい。意識を取り戻してすぐ布団に移動し、就寝。

10/02(日)

午後5時起床。食事したりTLを眺めたりして2時間ほど使った後、後期の履修を決めようとした。

前期に取った単位と必修を除く、残りの能動的に集めなければならない単位は八つらしい。うち六つぶんくらいは今セメスターで履修登録しておきたい。めぼしいものを見繕っていたら、他研究科の集中講義で面白そうなものがあった。ぜひ受講したいが、調べても日程が出てこない。そもそも履修登録の方法についても教務課に問い合わせる必要がありそうなので、早めに一回話を聞きに行く必要がある。

そのうちに午後9時になったので、ARC149に出た。

AtCoder Regular Contest 149 - AtCoder

AはM\mid(10^k-1)/9\times lを満たす1\le k\le N1\le l\le 9であって(k,l)が辞書順最大となるものを探す問題。とりあえず分母の9を払ってさてどうするか……と一息ついたら、(k,l)を全探索できることに気づいた。また、10^kkをインクリメントしながら求められるのに、毎回二分累乗法で求めようとしてしまい、\bmod 9M上の積がlong longをはみ出てしまうので__int128を持ち出したりと、後から振り返ればかなり遠回りして解いてしまったようだ。

Bはこんなの片方をソートするのが最適じゃないと解けないだろと思って実装。不安だったので、Aをソートする場合、Bをソートする場合、一切いじらない場合の3種類の値を求めた。考察も証明もせずにAC。

Cは面倒。とりあえず偶数を作りたい。Nが偶数の場合は上半分に偶数を、下半分に奇数を並べることでだいたいOKになる。真ん中はa2aを隣接させることで3の倍数にできる。Nが奇数の場合もほぼ同様だが、中央の奇数は下だけでなく右にも偶数が隣接するので、これを何とかする必要がある。適当なペアを選んで並べておくことにした。

ここから3素数であることを完全に忘れた考察。真ん中に並ぶのはa=1,3,\dots,2N-1となった。すると、2a\le 4N-2N^2以下でない場合はこのような並べ方ができない。計算したところN=3の場合だけ壊れるらしいので、そこは全探索して埋め込んでおいた。またNが奇数の場合に中央に並べるペアは(1,2)(4,8)にした。1+8=9が非素数になる。

WA。3素数であることに気づいて考察を修正。まず、真ん中に並ぶのがa=3,5,\dots,2N+1となるため、4N+2\le N^2が必要となりN\le 4の場合にうまくいかなくなる。N=4は全探索では求まらないが、適当に順列をシャッフルし続けるとすぐ見つかったので、それを埋め込んでおいた。サンプルにあるのを完全に忘れていた。Nが奇数の場合のペアは(3,6)(11,22)に更新。これで通った。

Dは面白かった。操作はx\mapsto|x-D|のように書けて、例えばxとして区間[l,r](ただしl\le D\le r)があったら[l,D-1]\mapsto[1,D-l]D\mapsto 0[D+1,r]\mapsto[1,r-D]に分けて[1,D-l][1,r-D]をまとめる、イメージ的には折り畳むような変化と捉えられる。ここまでは結構早めの段階でたどり着けたが、畳んだものをうまく戻せないように思ってかなり長い間詰まっていた。

実は戻せる。[1,D-l][1,r-D]のうち短いほうについて、それぞれ長いほうの区間のどの値と重なっているかメモしておくと、以降は長いほうの区間しか見なくてよい。こうやってメモするたびに区間が短くなっていくので、メモする回数はO(\max X)。答えを求めるときは、メモした値と対称の位置にいることがわかるので、答えが確定している値まで辿っていくことでちゃんと復元できる。この部分はUFのようにして実装した。変数名のミスで1WAしつつ何とか通した。

残り15分しかなく、Eの考察はあまりできなかった。4完34位。Bの証明は言われてみればという感じ。コンテスト中は本当に何も思いつかなかった。

コードゴルフはBのみ。LISのコードを過去問から引っ張ってきたが、アドホックな改善で1B負けている。他は手付かず。

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

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

Aはちょっと難しい。休日云々を忘れるとl_1+l_2+l_3=n-3かつl_1,l_2,l_3\ge 1が条件とわかる。ここでl_1\le l_2\le l_3とし、x=l_2-l_1y=l_3-l_2と定めると、条件がl_1\ge 1x,y\ge 0l_1+(l_1+x)+(l_1+x+y)=3l_3+2x+y=n-3と書き直せて、このもとで\min(x,y,x+y)=\min(x,y)を最大化する問題になった。まずl_1=1が確定し、2x+y=n-6となる。\min(x,y)=kだったとすれば2x+y\ge 2k+k=3kなので、k\le(n-6)/3が必要。逆にk=\lfloor(n-6)/3\rfloorが達成できるので、これが答えになる。

Bは最小値を最大化すればよさそう。実際、a_1が達成できる。できるだけ2a_1-1のブロックを作るように分割したとき、ブロック数を変えずに各値を区間[a_1,2a_1-1]に収まるようにできるから。

Cは先頭から順に変換前の文字として都合の良い最小のものを当てはめていく。使用済みの文字でなく、今見ている文字と同じでなく、さらにその変換を確定させたときに長さ26未満のループができてしまわない文字。一番最後の条件は、毎回ループをたどって判定した。

D。setはそのうち2枚が決まると残り1枚も一意に定まる。よって5枚のカードでsetが二つあるということは、その共通部分がちょうど1枚であることを意味する。O(n^2)かけて2枚のカードを全探索することでsetを全列挙し、各カードについてそれを含むsetの種類数を求めておくと、meta-setの共通部分となるカードを決めたとき、残りはsetを二つ組み合わせる場合の数になる。どんな二つを取っても、先ほどの話から決めたカード以外に共通部分を持たない。

Eは大変だった。d_{1,i}d_{2,j}が対応するとき、d_{1,i}+d_{2,j}または|d_{1,i}-d_{2,j}||p_1-p_2|に一致するらしい。これを使うと|p_1-p_2|の候補がO(n)通りになるので、とりあえず全探索する。この値がpだとすると、d_{2,j}=p-d_{1,i},p+d_{1,i},d_{1,i}-pのうちどれかだとわかる。|p-d_{1,i}|p+d_{1,i}だと書いておこう。

d_{1,i}を大きなほうから順に見たとき、d_{2,j}=p+d_{1,i}なるjがあるなら、必ずそれとペアにするべきである。なぜなら、より小さなd_{1,\ast}に対してこのd_{2,j}は対応できないから。このような貪欲を、d_2をmultisetで管理しながら行って、すべてのiに対して対応するjが見つかるかチェックする。

ここまでくれば必ず解を作れる。p_2=p_1+pと決め打っておく。対応するペアが(i,j)だったとして、d_{1,i}+d_{2,j}=pまたはd_{1,i}-d_{2,j}=pのとき、h=p_1+d_{1,i}とできる。そうでなければd_{2,j}-d_{1,i}=pであり、この場合はh=p_1-d_{1,i}とすべき。この値が必ず非負になる程度にp_1を大きく取ればよい。ここでp_1=10^9と決め打ったりしてはいけない。p\gt 10^9の可能性がある。

Fに1時間くらい残したが解けなかった。地獄のような実装をしてサンプルが合う直前にタイムアップ。5完8位。

Fのupsolveをした。持っているpebblesとbeadsの組を(x,y)と書く。各xに対して達成可能な最大のyを取り、これをグラフに書くと、折れ線がつながった上に凸な形になる。これを管理すればよい。i日目は折れ線上の点に対し(-p_i,+q_i)から(+p_i,-q_i)までできて、これはx座標の範囲が2p_iで傾き-q_i/p_iの線分を傾きが降順になるような位置に挿入することで表現できる。

こうやって書くとイメージ的にすぐ納得できるが、コンテスト中は大変な苦労をして式変形から導いた。折れ線をなす線分や担当する区間を変数で書いて、どのような遷移がありうるか考えればそんな感じになる。流れで実装時も各線分の情報をまじめに管理しようとし、遅延セグ木に乗せたり頑張ったのが上で触れた地獄のような実装。しかも書き上げたものを提出したらWAだった。グラフのx\lt 0またはy\lt 0の部分を削除する必要があって、今の実装だとどうやっていいのかわからない。

いったん式の具体的な形を完全に忘れると解けた。折れ線の両端点を持ち、形は傾きとそれが担当するx座標の区間の長さだけを管理する。線分の追加は、端点をずらした後新しい傾きと長さの組を挿入することになる。折れ線上の点は線分たちを傾きの降順に舐めて更新していくことで求まるのだ。典型テクなので思いつくべきだった。線分の追加後に折れ線を辿って端点をずらし、座標が負でないようにすることで、不適な部分の削除も行える。doubleだと精度が足りないようで、long doubleを使ったら無事ACした。

また履修を決める作業に戻った。上で触れた集中講義は受講できるか、できたとして卒業要件に含められるかちょっと怪しい気持ちになってきたので、そうでない講義を追加で一つ受講することにした。これを決めるのにまたリストを上から下まで眺めていたので時間がかかった。

昼前まで日記を書き、布団に入って少しラノベを読んで正午就寝。寝る直前にチュウニズムの大型アップデートの情報が流れてきた。アプデで消える要素の回収のため、それまでに2回くらいはゲーセンに行っておきたい。

週記(2022/09/19-2022/09/25)

09/19(月)

午後2時起床。先週の週記を少し書きつつ、もっぱらハーメルンを読み続けていた。午後10時前に1作読了。「犬とお姫様」。

syosetu.org

先週日曜日、つまり昨日読了した「女王様と犬」の続編で、比企谷八幡が高3、その他雪ノ下雪乃をはじめとする原作組がほぼ一律で高1となっている。雪ノ下陽乃は大1になっているので姉妹の年の差は原作と同じらしい。高1、高2と雪ノ下陽乃に付き従うことで鍛えられた比企谷八幡のスパダリっぷりが良い。年下になった原作ヒロイン組との関係やその中で改めて構成された原作と同じイベントたちが目新しく、非常に面白かった。

午後11時半を目前にして何とか週記の文章を作った。量が少ないのでハーメルンにかまけていても間に合ったのだ。読み返さずにいったん投稿。

CFの準備をしていたらスマホに通知が来た。30分後からTCO Finalsに関するオンラインミーティングがあるらしい。「午前12時から」と書いてあったので火曜日正午のことなんだなあと思っていたのに、実は日付が変わった瞬間だったようだ。心構えだけしてCF #821 div.2に出た。

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

Aはインデックスを\bmod kで分類してそれぞれ最大値を取る。Bはxyのどちらか一方が0で、もう一方がn-1の約数であればよい。Cはちょっと手間取ったが全要素を等しくすることができる。a_1と偶奇が一致するところだけ見て一番後ろの値を全体にコピーし、その後残りにa_1をコピーする。

D1はちょっと面倒。abで異なるインデックスを取り出し、奇数個であれば-1となる。偶数個なら必ず達成できて、特に4個以上なら2個ずつコストyで揃えられるので、これが明らかに最適。問題はちょうど2個のときで、ここを頑張って場合分けした。まず隣接していないならコストy。隣接しているとき、その左または右に2マス以上空きがあったら、そこを経由することで2yで揃えられるので、必要コストは\min(2y,x)

n\ge 5なので最後の条件は必ず満たされる。コンテスト中はこれに気づかずまだ場合分けを続けた。左右に1マスずつ空きがあった場合は\min(3y,x)になって、これも満たさなかった場合はどうしてもxかかってしまう。

D2はdp。あらかじめy\le xの場合をD1によって取り除くことで、先ほど場合分けしたような左右の空きマスを経由する場合を考える必要がなくなる。あとはどのようにペアにして揃えていくか。異なるインデックスだけ取り出したときに隣り合うペアをxで揃えるという遷移と、yによって揃えるペアの一方として確保する、または以前確保したものとペアにする遷移だけ考えればよい。

確保している個数を次元に持ってO(n^2)。実際は2個確保した段階でその二つをペアにしてしまってよいので、O(n)でも解ける。今x\lt yなので、うっかりインデックスとして隣接するペアをyで揃える遷移をしても問題ない。

ここまで解いたらちょうど日付が変わったので、オンラインミーティングに参加。その間はEの実験を行っていた。そうやって別のことに意識を取られていると、まず英語が全く聞き取れない。内容は全部チャット欄にまとめられた文章で把握していた。一方でEの考察も全然進まなかった。

ミーティングが終了してから改めて考えるとすぐ解けた。t秒後(x,y)にスライムがあるとしたら、それはもともとt-x-y秒の時点で追加されたものであり、それより前に追加されたt-x-y個のスライムだけが今注目しているスライムの動きに影響を与える。

ここで、(0,0)に追加されたt-x-y個のスライムのうち、\lceil(t-x-y)/2\rceil個が右に、残りが下に進んだとわかることに気づいた。以降同様に各マスにいくつのスライムが到達したかわかるので、これを全体に対して求めた後、t-x-y+1個目の動きをシミュレートすればよい。

全完7位。上に4人も日本人がいるのは何事だろうか。

ハーメルンを1作読了。「ようこそ元暗殺者のいる教室へ」。主人公の間延びしたセリフが好きになれなかったが、暗殺教室とよう実のクロスオーバーはいいなと思った。もっといろいろ読みたいと思って探したところ、ほとんど存在しないことが分かって残念。

syosetu.org

週記の校閲を済ませて午前4時くらいに布団に入った。30分ほどハーメルンを読んで就寝。

09/20(火)

午前11時起床。

布団に横たわったままハーメルンを1作読了。「RPG要素があるエロゲのRPG部分にドはまりしてエロそっちのけでハクスラするタイプの転生者」。日間ランキング1位だったので読んでみた。なぜ狂人と思われているのかの理由付けが上手い。最新話まで読み進められたくらい面白くはあったが、今の気分とは微妙にずれているように感じて、それほど印象には残っていない。

syosetu.org

昼食を摂り、しばらく本を読んでいた。午後5時前になってからノートPCの前に陣取り、インターン先の定例会に備える。月曜日が祝日だったので今日のこの時間にずれていた。

ノートPCにマイクがなくて、チャットによる参加になってしまった。先週の進捗はない。勉強会はOpenCVの話で、様々な画像処理や図形検出の関数が紹介された。幾何の問題として出くわしたら逃亡を選びたくなるほど面倒そうな処理がいくつも実現されていて、その手厚さに感動した。

夕食と入浴を済ませた後、リビングに転がって午後9時から2時間ほど寝てしまった。起きてからSRMに向けた準備をする。Appletを導入するつもりだったが、うっかり寝入ってしまってそれほど時間的な余裕がないので、今日もWeb Arenaで頑張ることにした。午前0時からSRM838。

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

Easyはシンプルに実装が遅かった。最初にbitsetでdpして復元することを考えて、さすがに面倒だったので、選んだ要素を直接vectorで保持したままdpできないか考えてみた。定数倍もよくて十分間に合いそうだったので実装。サンプルを合わせてから、本当に間に合うかもう一回見積もりをやり直したり、最大ケースを試すかどうか迷って結局試さなかったりと時間をドブに捨て続け、提出したら200点を切っていた。

Medはバカ発見器で、自分は発見されてしまった側。ダイスの面数Sを昇順に見る。これまでの期待値をEとしたとき、新しい数が出る確率が1-E/Sになるらしいので、E\leftarrow(1-E/S)\times(E+1)+E/S\times E=E+1-E/Sと更新する。1/Sを前計算すれば十分高速。これに気付くのに30分以上かかってしまった。

後から計算して納得。期待値がE=\frac 1 A\sum_k kC_kと計算されたとする。ここでC_kは種類数kであるような場合の数で、Aはすべての場合の数の和、つまり\sum_k C_kである。ダイスを面数の昇順に考えているので、今の面数をSとしてこれまでの種類数は必ずS以下であることを用いると、各k=1\dots Sについて新しい数が出る場合の数は(S-k)C_k通り、そうでないものはkC_k通り。

よって更新後の期待値は\frac 1{SA}\sum_k((S-k)(k+1)C_k+k^2C_k)。整理すると\frac 1{SA}\sum_k(SkC_k+SC_k-kC_k)=\frac 1 A\sum_k kC_k+\frac 1 A\sum_k C_k-\frac 1{SA}\sum_k kC_k=E+1-E/Sとなり、先ほどの式に一致する。

Hardは辺の長さ昇順に見て、それ以前の辺によって端点が連結になっていない確率を求められればよい。これはABCで数え上げ版の出題がある。その場で再現できなかったので、少し時間を使って以下の問題を探し当てた。しかし数え上げを確率の計算に書き直せず、それっぽいものを書いて試そうとしているうちにコンテストが終了した。

G - Connectivity 2

チャレンジフェーズは何もせず。Hardが結構落ちてくれたので少し順位は上がったものの、27位となり、レートは2887→2785(-102)。今日はシンプルに僕が悪い。僕の頭が悪い。Hardはコンテスト中に書いていたものを完成させてみたがサンプルすら合わず。Nがやたら小さいことに注目し、UFの状態を全通り持つべきだったらしい。

読書に戻り、午前4時半に1冊読了。「虚構推理短編集 岩永琴子の純真」。第一話「雪女のジレンマ」が好み。雪女とその恋人の馴れ初めが延々語られ、推理は最後のアクセントに。その使い方も苛烈ではあったが人を幸せにする方向で、ハッピーエンドで良かった。ただこれだけで表紙にまで雪女が描かれるのはびっくり、と思っていたら第五話も雪女に関する話だったらしい。こちらも優しい終わり方だった。

さらにハーメルンを読んでいたが、午前6時を過ぎたあたりで寝落ちしたらしい。その後いったん目覚め、そのタイミングで就寝報告のツイートをしていた。

09/21(水)

午前10時半起床。午前11時からTA研修会というのに出たが、これは心得を読み上げるだけで10分程度で終わってしまった。

昼食を摂り、荷物を纏めて昼過ぎに実家を出た。仙台に帰る。母に車で駅まで送ってもらい、午後2時半の新幹線に乗った。車内では1時間ほどハーメルンを読み、残りは本を読んでいた。

午後7時帰宅。PCを起動してしばらく触っていたら眠気が強くなってきて、午後8時から午前1時半まで布団で寝ていた。

起きてノクターンノベルズを1作読了。「無愛想な転校生の裏垢を見つけてしまった。」。もうすぐ電子書籍になるようで、TLに流れてきた表紙イラストに興味を持って読み始めた。それなりに話数はあるものの思ったより進展が遅かった。主人公のリアルとSNSアカウントが紐づけられる展開を期待していたが、まだ描かれていない。

https://novel18.syosetu.com/n0085hq/

その後もノクターンノベルズを漁っていくつか読んでいた。朝が近づいてきて、さすがに明日のセミナーの準備をしないとまずい気持ちになるものの、なかなか手が動かず、結局午前8時になるまでずっとTLを見たりYouTubeを眺めたりしていたらしい。そこから1時間だけ前回の発表資料の残りに付け足したりして、午前9時就寝。

09/22(木)

午前11時半起床。二度寝は怖いしかと言って身を起こすほどの元気もなく、布団に横たわったまましばらくスマホを触っていた。正午くらいにやっと起き上がって準備し、出発。山の上の購買に閉店間際に滑り込んで確保したパンやおにぎりを食べ、午後1時からセミナー。

まず自分の発表が3時間弱。頻繁に止まって確認したり例を挙げたりしつつ丁寧にやっていたら、昨日新しく用意した部分まで進まなかった。なかなか伝わらず大変。うまい具体例を用意できなかったのはあるが、説明も悪かったのだろうか。証明を、「お気持ち」がわかりやすくなるようにと教科書のものから少し変えてみたら、必要な性質を正確に導くのがかなり面倒になったので、そこは失敗だったなと思う。感覚的には明らかなので深く考えていなかった。

次に博士課程の方のセミナーが2時間弱。先々週の続き。これまでずっと前提知識の部分で詰まっていたのが、じわじわ進んで今日ついに補題の証明に入り、感動した。肝心の証明は道具を念入りに確認していただけあってスムーズに理解できた。

午後6時帰宅。小一時間TLを眺めた後、思い立ってラノベの新刊チェックをした。一通り調べていざ注文、という段階で眠気に耐えられなくなり、布団へ。午後9時から午前0時半まで寝ていた。起きてからしばらくノクターンノベルズを読んでいた。

PCの前に戻ってリストアップしておいたラノベを注文。9月下旬から10月下旬まで一か月ちょっとの間に出る作品で、今回は28冊とかなり多めだった。新作にはそれほど手を出していないので、追っているシリーズの最新刊の出版時期が被っただけらしい。

午前3時から昼まで日記を書いていた。途中頻繁にYouTubeハーメルンで集中を切らしてしまうのでそれほど捗らなかった。書いている間に話数が少ないものを2作読了。

syosetu.org

「大学生、上杉風太郎。インフルエンサーでホストやってます」。五等分の花嫁は原作をほとんど知らないのに、これは完結後の話だったので、回想の描写から結末に至るまでどういう展開やシーンがあったか薄々想像がついてしまった。まあこれは原作を知らないのに二次創作を読むときの宿命か。内容については良くも悪くも感じていない。ただ、ホストっぽいキャラはよくても主人公がホストそのものというのは好きになれなかった。

syosetu.org

「国民的大物女優観察記録」。こちらの原作は全く何も知らなかったので、ほぼオリジナルと変わらない感覚で読んでいた。好感の持てる勘違い主人公で面白かった。エタりかけに見えるが、ちゃんと一段落するところまで投稿されていたのが嬉しい。

午後1時前に就寝。

09/23(金)

午後8時半起床。今日はコンテスト二つ。まず午後9時からCF #822 div.2。

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

Aはソートして連続する3要素を真ん中に寄せるのを全探索。Bは実験エスパーで各段の両端だけ1にした。Cは1\le k\le nに対してその倍数を全部見てどれを消せるかチェックすることで、逆に各値を消せるkの最小値が求まる。実際、小さい値から順にいま求めたkで消していけば達成できる。今考えてみれば、kを昇順に見て消せる値を貪欲に消しても同じことだった。

Dは難しかった。吸収したスライムの区間[L,R)として、aの累積和Sを取ることで必要な条件がS_R\ge S_Lと書ける。Lを固定してRを右に動かすことを考えたとき、先の条件を満たせる限界までいったん動かしてみて、その中でSが最大となるところを新しいRにして損しない。ただし端まで到達できるなら即座にYESとなる。Lについても同様のことを行い、どちらでも[L,R)を変化させられなくなったらNOである。

Eも難しい。a_{i,\ast}が交差iの等差数列になるように定めると、a_{r_k,c_2}-a_{r_k,c_1}\equiv r_k(c_2-c_1)となる。0\lt c_2-c_1\lt nかつr_1\ne r_2よりこの値はk=1,2で一致せず、よって条件を満たす。どうやって思いついたか定かではない。確か、行または列の値を揃えて少しずらすことを考えていたのだった。

Fも難しい。難しい問題だらけ。n+m\le 2^{k+1}を満たすkを取り、S_{[2^k,2^{k+1})}S_{[0,2^k)}のflipであることを利用することで、いくつかのより小さいn,mに分けて再帰的に求められるが、クエリの個数が爆発してしまいそう。しかしよく観察すると種類数が少なかったため、メモ化することで十分高速になった。トリックはこうだ:分割後にn+m=2^kを満たさないものは高々一つであり、さらにn+mが2べきの場合、以降何度分割してもその回数ごとに高々2種類のクエリしか生成しない。

Fに1時間かけて順位が崩壊した。全完19位。

シャワーを浴びて午後11時半からCodechef、September Lunchtime 2022 div.1。3時間半もあって大変。ペナルティがないので提出し放題だったのだが、各問題に60個程度テストケースがあって、提出するたびにいちいち神経をすり減らしながら待つ時間が発生して辛かった。

https://www.codechef.com/LTIME112A

INCADDはA_{i+1}-A_iを観察するとすぐ解けた。この値をすべて非負にしたい。区間更新はある範囲に+1したあと右端を大きくマイナスする操作になるので、常にR=Nとして操作することでそのマイナスを無視するのが明らかに得。さらにL=1とすることで全体に+1することにして、-\min_i(A_{i+1}-A_i)回操作すればすべて非負にできることが分かった。セグ木で管理してAの更新に対応。ただし操作回数も当然非負である必要があり、これはセグ木に乗せるモノイドの単位元0にするだけでは不十分だった。all_prodの際わざわざ単位元を掛けたりしていないのは当たり前。

ADJACNTPAIRSは簡単。最終状態を決めたとき、それと異なる値を一つ一つ揃えなければいけないのに加え、ちょうど一つずれたような連続部分列があればその長さlに対して\lfloor l/2\rfloorだけ余分に操作しなければならない。これは高々O(N)種類しかないのであらかじめ計算しておく。あとは最終状態の偶数番目と奇数番目としてそれぞれAにおける出現回数が多い順に値を試していく。O(N^2)通りあるが、明らかに答えを改善しない場合スキップすることでO(N)になる。なぜなら、偶数番目の値を決めるごとに、奇数番目の値としては余分に操作が必要ないもののうち出現回数最大のものしか見なくてよいから。

RMVNUMBERSは難しかった。相手の選択によらず適切に動いてAを空にできるか考える。これまで出現した値のLCMを今見ている値が割り切った場合、またはそのLCMが4\times 10^{14}を超えた場合にそうなるので、操作回数がある程度あればよさそう。2べきが昇順に並んでいる場合が最悪ケースのはずで、これでも50回も操作すれば十分。つまりM\gt 100のとき、先手も後手もやろうとすればAを空にできてしまうので、答えは必ず0となる。

あとはM\le 100の場合が解ければよい。Aを単純にvectorで持って再帰した。一段階再帰するたびにBで割り切れるか否かでAが完全に分かれるため、各深さにおいてvectorの長さの総和がNとなる。よって、空になったらさっさと0を返すのに注意すればO(NM)が達成される。コンテスト中は何を考えたかメモ化してしまい、0.49sec。この問題のTLは0.5secなので本当にギリギリ。日記を書いているときにこのメモ化が必要ないことに気づき、消して出しなおしたら爆速になった。

UNFRIENDLYは謎。どうせ持つべき候補が少ないタイプの問題だろうと思って、列の長さが\maxまたは\max-1なペアしか持たないようにしたら全然合わなかった。この下限をどんどん引き下げて何回も提出してみたが、TLには間に合っているもののWAのケースが全然減らない。そもそもA\le 3のケースですら盛大に間違えている。手元でランダムケースを作ったらすぐ落ちて、ようやく何がダメだったのか気づいた。

A\le 3のときの繰り返しパターンは2種類しかない。序盤でそのうち片方が一定以上優位に立ったとき、そこからもう片方のパターンに切り替えられないようだ。そこで、あるペア(a,b)を持つか決めるときに、対応する列の長さが\max-3以上という条件のほかに、すでにペア(b,a)を持っている場合も持つとするコードを書いてみた。とりあえずA\le 3のケースでは正しく動くはず。これで提出したら、なんと満点を取れてしまった。

残りは部分点。LCAINTERACTは直径を一つ求め、その端点の一方が根でないことを確認した後、そこから根がどれだけ離れているか二分探索で求め、その距離にある点の集合を半分だけ聞くのを繰り返して実際の根を特定するというコードでクエリ回数12回を達成した。直径の端点が根になってしまった場合に次数3の頂点を使った。中心を使うともうちょっと減らせそうだったがWA。BNDSPANTREEは区間スケジューリングで部分点1のみ。

合計481点で9位、レートは2799→2832(+33)、highest。BNDSPANTREEは明らかな必要条件からLRを調整するだけで区間スケジューリングの順序と辺の重みの順序が噛み合ってうまくいくらしい。すごい。パスに対するクエリに答える必要があってHLDを使いそう。自分もそろそろ履修しなければならない。

UNFRIENDLYの解法の正当性がよくわからない。下のツイートを元に考えてみる。持つか持たないか迷っているペアが発生するとき、\max\ge 4であるから、今のところ最適とされている選び方の直近四つが(w,x,y,z)と取れる。ここでw=zかもしれないが今は異なるとする。候補として確実に持っているのは(w,x),(x,y),(y,z)で、この三つのうちどれにも繋げることができないのは(y,x),(x,z)のみ。

実際、今確実に持っているペアを反転してみると、挙げた二つはそれぞれ(x,w),(z,y)に繋げることができる。しかしわざわざこのペアを選ぶ必要はないので、なぜこれだけチェックしておけば十分なのかがわからない。例えば(x,z)なら(w,x)というすでにあるペアにzを足すことで再現できるため問題ないと言えるものの、(y,x)のほうはどうやって吸収されているのか本当にわからない。

ちなみに、こういう考え方は\max-2以上を持つとしても同じところまで進める。なんと条件をこれに強めてもACしてしまった。\max-1ではさすがに落ちた。

食事して午前4時からTCB51に参加した。

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

3問目はこの位置としては難しめに見える。ずらす幅を全探索し、対応する要素の差を足し合わせる。4問目は前から貪欲に操作しなければならない。5問目はfの和をA_i\sum_k B_k+MA_jと書き直す。\sum_k B_kの符号を見れば答えの候補は高々二つだが、念のためA_iを全探索した。

7問目はかなり面倒。ある頂点の親を1にするのが最適で、変更した頂点を根とする部分木に対する{\rm dist}(1,\ast)\maxはその場で計算、他の頂点のそれは全方位木dpのように計算して伝播してきた値を使った。

8問目は謎。最初にO(NM)のdpで値の種類数が1\dots\min(N,M)の数列を数え上げる。種類数がN未満の数列は必要な値をすべて含むような列ならどれからでも作れるが、そのような数列の数え上げにも今計算した値が使える。種類数がちょうどNの数列はそれ自身からしか作れない。

9問目は区間dp。10問目は|S|=cと決め打つとO(Nc)のdpが書ける。まだ決めていないSの要素数を持つことにして遷移をAの値で場合分けしてみると、A=-1の場合はdp_i\leftarrow dp_i+dp_{i+1}i=0\dots cで行い、A\ge 0の場合はdp_A\leftarrow dp_Adp_{c-A}\leftarrow dp_{c-A+1}だけ計算して残りは全部0にするという遷移になることが分かった。シンプルでいかにも速そう。これを実装すると、最悪ケースである全部A=-1のケースも手元で2.5secになり、提出してみると3.7secで通った。

理論値。時間は50分弱で、各問題ともボーダーまでかなり余裕がある。10問目はまたしてもTL 5secを悪用して定数倍高速化で通してしまった。改めて考えてみたところ、A=-1の場合の遷移を遅延させることでdp_{\ast}の非ゼロ要素が高々2個になり、具体的な値の取得も定数時間で行えて|S|を決め打つごとに計算量O(N)が達成できた。あまり見ない高速化で面白かった。

このあとYouTubeとネット小説に1時間ずつ時間を吸い取られてから日記を書き始めた。午前11時に切り上げてから少し読書。本を1冊読了。

「虚構推理 逆襲と敗北の日」。長編、ただし最初に短編のようなものが一つ付属していた。ちょうど解決シーンに入るところで数日読むのが止まっていたためちょっと没入感が薄い。そもそも解決自体割とあっさり目で、サブタイトルの意味もそこにはなく、続く主要キャラクターたちのやり取りがメインだった。この部分は興味深かった。岩永琴子はもうちょっと非人間的な性質だと思っていたのにそうではないようでびっくり。がっかりもしかけたが、その分は桜川九郎でバランスが取れているらしい。

ネット小説を読んで午後1時半就寝。

09/24(土)

午後8時半起床、午後9時からABC270。

TOYOTA MOTOR CORPORATION Programming Contest 2022(AtCoder Beginner Contest 270) - AtCoder

Aはbitwise ORを出力する。とりあえずRakuで書いたあと、もっと短くならないか4分ほど試行錯誤していた。

B問題は難しい。まずX\gt 0となるように適切に符合を反転しておく。0\lt Y\lt Xのとき壁を破壊する必要があって、Y\lt Zならハンマーを拾いにすら行けないため-1。そうでなければ|Z|+(X-Z)である。そもそも壁を破壊する必要がなければ答えはそのままXとなる。丁寧に確認していたらかなり時間がかかった。

CはXから祖先のリストを管理しつつdfsし、Yにたどり着いた時の状態を出力。Dはdp。Eは何周するか二分探索し、残りをシミュレート。Fは港と空港用の超頂点を用意し、その二つを連結成分に含めるか22通り全探索してそれぞれ最小全域木を求める。

GはX_i=A^i S+B\sum_{j=0}^{i-1}A^jと書ける。A=1は別に計算することにすれば、和を閉じた形にしてX_i=A^i S+B\times\frac{A^i-1}{A-1}=A^i\left(S+\frac{B}{A-1}\right)-\frac{B}{A-1}となる。これがGに等しいので、S\leftarrow S+\frac{B}{A-1}G\leftarrow G+\frac{B}{A-1}と置きなおすとA^i S\equiv Gが求めるiの条件。S=0は場合分けにより、それ以外はA^i\equiv G/SをBSGSで解くことで答えが求まる。

Exは難しい。しばらく唸っていたら綺麗な表現を見つけて一気に解けた。カウンターの操作を、初期値A_iであるような値C_iをデクリメントするかC_i\leftarrow A_iとするかで表し、状態をS=\max_i C_iで定める。この値が0になるまでの期待値を求めたくて、遷移はカウンターiを操作するときS\leftarrow\max(S-1,A_i)と書ける。これでループのある期待値dpに帰着できそう。

dp_Sを状態Sから0に遷移するまでの操作回数の期待値とする。E=\sum_i dp_{A_i}とおいて、dpの値をすべてEの一次式で表す。S=x\ge 1に対してdp_x=1+\frac{\sum_i dp_{\max(x-1,A_i)}}Nとなり、x-1\ge A_iなるiの個数とそれに対するdp_{A_i}の和が求まっていれば、適切にEから引いたりdp_{x-1}を足したりして計算できる。

最終的にdp_x=X+Y\times dp_{x-1}という形で書けて、XYは次にx=A_{\ast}となるまで変化しないので、その間の遷移をまとめて行うことができる。これによりS=A_1,A_2,\dots,A_Nのみ求めるのが十分高速。最後にE=\sum_i dp_{A_i}からEの値を求め、dp_{A_N}にそれを代入したものが答え。

本当にEを求められるのか、つまり\sum_i dp_{A_i}におけるEの係数が1にならないか不安だったが、エイヤと出したら通った。ではどんな値になるのかということでコンテスト後に式を追ってみたが、複雑すぎて断念した。

全完3位、日本人2位で賞金10万円。1時間ちょっとで全完したので時給10万円らしい。こんなことならAでコードゴルフしてなければよかった、と思ったが、実際のところ2位との差は10分以上あってどうしようもない。それより4位との差が2分ちょっとだったことのほうが重要で、B問題を丁寧に解いたことやG問題の式変形のコーナーケースを見落とさずノーペナで通せたことはかなり偉かった。

Gはこういう式変形をしなくても直接BSGSできるらしい。結局fのべき乗が同じ形で表せることが重要。解説のBonusは、通常のBSGSを非素数modで計算する場合と同じでf^{-1}を使わず頑張れるという話だと思う。このfでも\log Pステップくらい進めば周期に入るのだろう。

コードゴルフ。これはMHC後に縮めたものも含む。AはRakuよりAWKのほうが短くなった。Bは0XZの間にYがあるかで場合分けしていることになって、この「間にある」という条件は例えば(0<Y)==(Y<X)のように書ける。正確には区間のちょうど端にある場合に注意する必要があるが、今は制約から関係ない。これをAWKで実装したものが最短になっている。

Cは根をYとして各頂点の親を求める方法を実装したがコンテスト中の方法に負け。言語はPerl。DはAWKでdpしたらPerlより縮んだ。EはRuby。以降は手付かず。

午前2時からMHC R2に出た。

Meta Hacker Cup - 2022 - Round 2

A1は文字を取り除いたときに文字列の中心になる場所を2通り試して、左右に出現する文字ごとの個数の差が一つだけ1、残り全部0となることをチェックした。あらかじめ文字ごとに個数の累積和を計算しておく。

A2でも中心を2通り試すのは同じ。その前に列全体のXORを計算することで取り除く値が何であるかを確定させておき、チェックをmultisetのハッシュで行った。値に素数を割り当て、その積を\bmod pで管理する。このpとしては素数をたくさん用意してあり、提出コードでは7個だが、思ったより高速に動作したため手元で18個使っても出力が変化しないことを確かめておいた。ちなみに、原始根を考えることでこれが\bmod{(p-1)}における和を管理しているのと変わらないことがわかる。コンテスト後に気づいて拍子抜けした。

Bは各クライアントに対して上位K個のパスを管理する。遷移も、適切な順序でクライアントを見ることで日付ごとに上位K個のパスを更新しながら行えるため、十分高速。

Cが解けずDに進んだ。D1は左右の和の差が交換によって\pm 2\pm 4しかされないため、\pm 4、つまり13の交換を貪欲に行うべき。

D2は12しかないため交換しなければならない個数がわかって、それがc個だったとすると、Zから左に見てc個目までの1を右に見てc個目までの2と入れ替える、あるいはこれの12を逆にしたものを行うことになる。個数を管理するセグ木の上で二分探索することで範囲がわかり、その範囲内でインデックスの総和を求めると、差が答えになる。

Bが落ちて64点、178位。オーバーフローしていた。パスの利益は\max_i X_iで押さえられると思っていたのに、Y_i\lt X_i、つまり高く買って安く売る能無しクライアントのせいで壊れていた。

朝までC問題と格闘していた。はかりの左右どちらに乗せるかが重要だと思っていたが、対称性から無視できるらしい。とはいえ解説のこの部分はサラッと流されてしまっていたので、自分で説明を加えた。計算量は少し悪くなったものの間に合うオーダーに落ち着いたので満足。まずW_1と同じ重さのクッキーを1個以上はかりに乗せる確率を求める部分について、これは単に選ぶ順番(K+1)!通りを全部キャンセルしているだけなのでcombinationでよい。

次に、W_1と同じ重さのクッキーをk=1\dots C_1+Y個使う場合について考える。このケースに制限すると解説の文言が納得できた。k個をどのタイミングで選ぶか決めるごとに、そのうちどの位置に置かれたものが最後まで残るか一意に決定して、そこに置かれる確率はk個どれでも等しく1/kになるのだ。これによって、相変わらず選ぶ順番(K+1)!通りをキャンセルしてよいことがわかる。選び方を数え上げ、すべてのkに対して和を取った後、\binom{C_1+X+Y}{K+1}-\binom{X}{K+1}で割ることにしよう。

k個のうち0\le j\le k個がバッチ1由来である場合を考えると、まずこれが起こる場合の数が\binom{C_1}{j}\binom{Y}{k-j}\binom{X}{K+1-k}通り。そのうちj/kが当たりなので、これを掛けて足し合わせたい。Wolfram|Alphaに投げるとうまいこと閉じた式にしてくれて、C_1\binom{C_1+Y-1}{k-1}\binom{X}{K+1-k}/kになった。kは全探索できるので、これで解けている。

しばらくABCのコードゴルフの続きをした後、昼前から日記を書いていた。金曜日のCodechefの部分に差し掛かって、UNFRIENDLYを通した自分の解法の正当性が証明できず、布団に逃げ込んだ。午後3時就寝。

09/25(日)

午後8時半起床。午後9時から久しぶりのTOKI、TROC #27。

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

Aは列Aに偶数が含まれているか調べる。Bはそれより大きい最小の2^k-1までインクリメントし、一気に消すのが最適。

Cはインドネシア一流の謎パズルで、(N-2)(M-1)+M+1とそのNMを入れ替えたものの\maxを提出して1WA。4\times 4を考えて右上と左下を結ぶ線の上以外を暗くすることが可能だと気付いた。答えはNM-\max(N,M)

Dはやたら合わせるのに時間がかかった。F=1の場合は自明。F=2の場合、「先頭が1で隣接項の差が2以下の長さiの順列」をi\le Nに対して前計算しておけば、適当に足し合わせることで答えになる。この前計算は挿入dpを考えるのが正解だったらしい。隣り合う2項を交換するか決めるだけでは1,3,5,7,6,4,2のような並び方を生成できない。

EはM\le 2という制約に気づかず1WA。しばらく実験して、N以下で最大の2^k-1と、2^k\le Nならそれも聞くことで特定できることに気づいた。前者によって1\le s\le 2^k-1を、後者によって2^k\le s\le Nを区別できている。

Fは面白い。好きな辺を選んでそこまで往復することでウォークの美しさを\pm 2W_iすることが可能。これでユークリッドの互除法を行えるため、g=\gcd(W_1,W_2,\dots,W_{N-1})として2gで割ったあまりを求められる。この時点で、とりあえず根を一つ決めて各頂点までのパスの重み\bmod{2g}を求めておいた。それをd_uとすればf(x,y)\equiv d_x+d_y\pmod{2g}である。{\rm LCA}(x,y)より上のキャンセルも\bmod{2g}に吸収される。

d_x+d_y0(0,2g)[2g,4g)に分類するのは難しいな、と思っていたが、冷静になると\forall i.\;g\mid W_iなのだから、d_u0またはgだった。これなら0+02gに置き換えるだけでよいので簡単。

Gも面白かった。実験するとN回コピー後に値M\binom{N-1}{M-1}個あることがわかる。この値は\binom{N-2}{M-1}+\binom{N-2}{M-2}と等しく、先頭から\binom{N-2}{M-1}個は1回コピーをキャンセルしてもMで、残りはM-1になるということがわかる。このことから、NをデクリメントしながらDMを丁寧に更新するO(N)の方針が得られる。ただしcombinationは適切に差分更新を行う。

Nがとんでもなく大きいと困る。しかしM=3ですでに\binom{N-1}{M-1}=(N-1)(N-2)/2からN\approx\sqrt Dとなるため、M\ge 3では十分間に合いそう。よってM=1,2のケースさえ別に判定すればよく、この部分は実験で容易に解ける。

Hは解けず、7完8位でレートが2732→2762(+30)。highest。

10分のインターバルで午後11時半からCF #823 div.2。

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

Aはよい。Bからすでに難しかった。xでソートしx_k\le x_0\le x_{k+1}となる場合を考えるのを繰り返す。t_i+|x_i-x_0|i\le kかどうかによって絶対値記号を外せるので、それぞれ外す。x_0の項を除いて適切に\min\maxを求めるのは、あらかじめ左右から累積的に計算しておける。これを使うと最小化する値が\max(x_0-L,R-x_0)のような形になり、二つの値が等しい場合に最小値を取る。

Cは簡単。後ろから見て累積\minとならない位置の文字は動かすべきで、それもちょうど1回動かすとしてよい。するとどんな数字に変化するかわかり、残した累積\minの広義単調増加を壊さないような位置に挿入するのが最適になる。

Dは信じられないほど難しかった。ずっと実験で文字がどう入れ替わるか観察していたが全く光明が見えない。ふと不変量について全く考えていないことに気づき、その気持ちになって眺めると、s_1i文字目とs_2の後ろからi文字目がペアとなり、必ず異なる文字列に入ることに気づいた。ペアの列を並び替えたり、要素の順番を逆にするのは自由にできると信じる。

もし文字abのペアが二つあれば、文字列における対称の位置、例えば先頭と末尾に置くことでそのインデックスを揃えることができる。同じ文字のペアが奇数個しかない場合、それがaaのような形をしていれば文字列の中央に置ける。逆に、異なる文字のペアだったり、文字列の中央が埋まっていたりするともうダメ。この判定を書いたら通った。1時間かかったらしい。

次により多く解かれていたFを考え、bitDPをしても見るべき状態数が少ないから間に合いそうだと思ったが、とりあえず書いたらサンプルが合わず、そのままコンテスト終了。4完。かなりの大失敗だった。Bはx_0の位置にかまわず|x_i-x_0|=\max(x_i-x_0,x_0-x_i)として展開してしまう方法が賢い。コンテスト中のようにLRを使った形に整理できる部分は同じながら、x_0の範囲が制限されておらずここから即座に答えが出る。

コンテスト後にFをupsolveした。まずbitDPの説明から。インデックスiを見ているとき、v=p_{q_i}としてここに置ける値の範囲を考えてみる。まず自分より左にi-1個の値があって、これらはすべてv+k以下である必要がある。そのような値はv自身を除いてv+k-1個しか存在しないため、v+k-1\ge i-1よりv\ge i-kが得られる。同様のことが右に対しても考えられて、v\le i+kもわかる。

つまり値をこれまで置いたかどうか記録しておかなければならない情報が2k+1個分、v=i+kはインデックスiで初めて置けるようになった値なので、正確には2k個記録しておけば十分で、bitで表現できる。

端を除けば2k個のうちちょうどk個が埋まった状態しか考えなくてよい。k=8で計算してみると\binom{16}{8}=12870通りだった。これで出してもTLEしてしまうが、ここで「また値vを置いていないのにv+kより大きな値が置かれている」という状態をちゃんと無視することで十分高速になった。値vを置くときにダメだと気付くのでは遅く、状態数が多くなりすぎるようだ。そのほか、転倒数をあらかじめi-k\le v\le i+kに対して計算しておくなどする高速化を入れて提出すると、1400msで通った。

TCB51の結果が出ていた。理論値は3人いたが時間差で優勝。10問目を非想定で押し通しているとはいえ、2位と20分以上差をつけていて気分がいい。

来週水曜日にたいぺーとホスフィンと3人で家で飲む予定。いつもはドンキでお酒を購入するのだが、今回はAmazonで見繕ってあらかじめいくつか購入しておくことになっていた。ギフト券残高の消化。これの希望が出そろっていたので、しばらく時間を使ってそれが本当に最安値か調べたりした後注文した。

午前4時から午前11時まで月曜日のインターン先勉強会のための発表スライドを作っていた。内容は考えてあったので今日一日で何とか完成。

途中でRating Historyを確認したらAtCoderCodeforcesのAC数が両方ほぼキリ番だった。

生協に行って菓子パンやラノベを購入し、正午就寝。

週記(2022/09/12-2022/09/18)

09/12(月)

午後1時起床。布団に横たわったまま1時間くらいTLを眺めていた。シャワーを浴びて生協とコンビニへ。予約していたラノベを受け取り、パンやお菓子を買ってきた。帰ってきてしばらく先週の週記を書き進めていた。

午後4時半からインターン先定例会。先週火曜日の1on1までを進捗として報告。週あたりの稼働時間はこれまでと特に変わらないが、今回は求めるものにかなり近い出力が得られているので、ウキウキで発表した。今週は帰省のため全く稼働しない予定。

勉強会はビームサーチの話だった。焼きなましはそれっぽく書いてもまあまあ動くのに対し、ビームサーチはうまく行った試しがない。そもそも自分のマラソンマッチ経験が少ないからというのもあるだろう。今日は基本的なこと、どのような実装上の工夫があるかなどに焦点を絞って聞いていた。

終えてからもずっと日記を書いていた。午後11時半になって一通り文章が出来上がったので投稿、即座にCF #820 div.3に出た。

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

Aはa-1|b-c|+c-1を比較。b=1のときの注意書きを誤読し、最初は場合分けしていた。サンプルで落ちたので改めてしっかり読むと真逆で、特別扱いしなくてよいと書かれていたのでびっくり。Bは後ろから復元すると簡単。Cは先頭から末尾に一気に飛ぶのがコスト最小の経路の一つ。文字コードに関してその間にあるマスを全部踏んでもコストは変わらないから、それを出力する。

Dはy_i-x_iを見て、最大と最小をペアにできるならするのが最適。ペアにできない場合、最小のほうをグループに含めようとするとそこにy_i-x_i\gt 0なる人を二人以上使う必要があるが、それをするくらいならその二人だけでグループを作っても変わらない。つまり最小のものを無視してよい。dequeで実装した。

Eは微妙に二分探索できない制約なので乱択しろと言っている。3頂点の間で計3回聞いてループを作ることにした。パス2本のうちどちらが答えとして返ってくるかは2^3通りあって、そのうち5通りではそれぞれ答えが一意に確定するようだ。つまりそれらを候補とし、今度こそ二分探索することで正しい答えが求まりそう。

二分探索にかかるクエリ回数を適当に見積もった結果、9頂点の完全グラフを聞いてそこから\binom 9 3個のループを取り出し候補を作ることにした。辺がたくさん重複しているので、1ループあたり候補に答えが含まれる確率が先ほど求めた5/8になっているかは不明。信じて投げたらWAが出てしまった。

今度はループに含まれる辺に重複がないようにしてみた。ループの数は13個になってしまうが、これでも失敗する確率がケース当たり(3/8)^{13}で、50ケースあるのだから全体の成功確率は(1-(3/8)^{13})^{50}\approx 0.9999。この計算でかなりの自信を持ちつつ提出。しかしこれもWAだった。

流石に何かおかしいと思ってコードをチェックすると、クエリを投げる関数の引数がint型になっていた。ここをlong longに修正したら上の二つの方法はどちらも通った。つまらないミスで2ペナと+10分、残念。

Fは\bmod 9が聞かれているので桁和に言い換え。あらかじめv(l,r)\bmod 9kのすべての組み合わせを試しておき、クエリに答えた。しかしこの前計算も定数時間で行えているので、素直にその場で求めてもよかったかもしれない。

Gはdp。sを先頭から見て、tの出現があったらそれと被るような区間をドットに置き換える。どこを置き換えるかは全探索し、置き換えた先の文字に飛ぶ。最初にsのどこにtが出現するか列挙しておいたら計算量がO(|s||t|)になった。制約は3乗を許すくらい小さいので謎。

全完23位。Eは2頂点を(a,b)(b,a)の形で聞くのでも良かったらしい。1\le a\lt b\le 6の範囲で15セット聞くだけでも、それぞれ1/2の確率で失敗するので全体の成功確率は(1-(1/2)^{15})^{50}\approx 0.9985で、通った。クエリ回数は33回程度なので、この確率はまだいくらか上げることができる。

先週の週記の校閲に入り、午前4時完了。しばらくコードゴルフしてから布団に入り、ラノベを1冊読んだ。「D級冒険者の俺、なぜか勇者パーティーに勧誘されたあげく、王女につきまとわれてる」4巻。

この巻はシリアス+バトル。3巻までの内容をあまり覚えておらず、伏線に言及されてもピンとこなかったり、前の巻で取り扱われたキャラを新キャラだと思い込んでしまったりしたが、メインの1巻からずっと出ているヒロインに関してはいくらか覚えていたのでついていけた。終盤は主人公の無双シーン。日記での言及を読み返す限り、3巻はそういう描写がなくて消化不良気味だったらしい。今回は読めて嬉しい。相変わらずの理不尽な強さは、これからだんだん背景が明らかになっていきそうな予感。

ハーメルンを開いて最近のランキングをチェックし、1作読んだ。「依存症な彼女たち」。まだ2話しか連載されていないが、今のところ非常に面白い。なんとなく淫靡な雰囲気が気に入った。主人公の動じなさも好み。

syosetu.org

午前8時半就寝。

09/13(火)

午後4時起床。1時間くらいスマホを触ってから身を起こした。準備を整えて外出。ゲーセンに向かう。

油そばで腹ごしらえをして、午後6時半から5時間くらい遊んだ。今日はひたすら新曲。それなりの難易度の譜面がいくつも追加されて、それぞれ粘着してAJを捻り出そうとしていた。

端に接するように配置されたフリックは、その端の1マスともう一箇所を含むように触れるだけでJC判定が出る。これを利用して手をあまり動かさずにフリックを拾う、いわゆる端フリックと呼ばれるテクニックがあるが、これを嫌ったのかこの譜面ではひたすら内側にフリックがあって大変やりにくかった。

普通の譜面と同じ感覚でやると外側に弾くように手を動かしたくなるのに、それだとアタックが出てしまうので、意識して内側に向ける羽目になり、プレイしていて気持ちよくない。そもそも端フリック判定というのは、多少のアバウトさを許し爽快にプレイさせるためのものであるからして、これを回避されては苦しい。

中盤も終盤も難しい。ホールドをある程度無視することで中盤の勝率が上がったと思ったら、無事終盤で癖が付いて大変だった。ちょっと運指を組んで解決。

プレイ真っ最中の午後7時過ぎ、TLでPAST11に関する言及を見たので、さてはと思ってAtCoderを確認したら過去問が公開されていた。出先にいてコードゴルフできない。慌てて最初数問を見たが、そんな一瞬で最適っぽいコードが出そうなものはなかったので、とりあえず安心。

帰宅してから数時間ほどコードゴルフしていた。

第11回 アルゴリズム実技検定 過去問 - AtCoder

とりあえずHまでとJを解いた。DFHは特に縮みそうな気配がない。

AはX/A+C-X/Bの符号を見る。符号を見るときはdcでRコマンドを使うのが定番で、このとき適当に掛け算して非ゼロの場合の絶対値が3以上になっている必要がある。ところがこの式にBを掛けたものがすでにその条件を満たすらしい。すると式自体もかなり書きやすくなって、いい感じに縮んでくれた。

BはRakuのマッチングでExhaustiveオプションを使うのが強い。取り出す区間に重なりがあっても構わず、あり得るすべてのマッチを取り出してくれる。実行時間だけが心配だったが、かなり余裕を持って間に合ったのも嬉しい。

Cは整数と浮動小数点数にあまり区別のない言語だと単にべき乗を計算するだけで十分である。なぜなら109くらいなら精度を落とさず表現できるから。試した中ではPerlで書くのが短い。

Eはi=\lfloor\sqrt{N-1}\rfloorとして|N-i^2-i-1|+1が答えとなる。これはすでにdcで隙のないコードが提出されていた。Gは過去の問題を漁って、グラフを連結にするためにはあと何辺必要かという問題を探し、それの最短コードを少し弄って提出した。ただの判定ならもうちょっとなんとかなりそうではある。

C - Connect Cities

JはRaku。普通に日付のRangeでループしようとしたら、最大で300万回弱回すことになって流石に間に合わなかった。日付から、暦の起算日から数えて週末が何回あったか求め、差を取る方針に。daycountメソッドで得られる日数のカウントが1858年11月17日水曜日を0として数えたものであることに注意しつつ、頑張って式を作った。

明日帰省する予定。その前にやっておくこと、クラウドに上げておいたほうが良さそうなデータなどを確認していた。途中TLを見たらProject Eulerを埋めていた人がいて、つられて自分も1問挑戦してみたが、結局解けなかった。

午前6時に布団に入った。1時間ほどハーメルンを読んで寝落ち。

09/14(水)

午後1時起床。昨日に続いてハーメルンを少し読んでいたが、帰省のためにはそう悠長にしている時間はなかった。布団から脱出して準備開始。

仙台にいる間にやっておきたいこととして、月曜日読んだラノベの感想を日記に書くことと、前期の単位の取得状況をツイートすることがあった。それぞれパパっとこなした。以下のツイートの画像には含まれていないが、5月下旬頃に一週間グラフ理論の集中講義を受けていて、これは2単位分。無事AAだった。

いよいよ集中講義一日目である。

週記(2022/05/23-2022/05/29) - kotatsugameの日記

今回の帰省では「虚構推理」シリーズの既刊5冊を一気に持ち帰ることにした。以下に引用したような経緯があって、今がちょうど良い機会だと思う。

漫画を読んでいた。虚構推理の1巻と、転スラの10巻から15巻あたり。前者は小説版を積んでおり、序盤を漫画で確認することで読む意欲を高めようとした。

週記(2022/09/05-2022/09/11) - kotatsugameの日記

午後3時を回ってから出発。仙台駅に向かい、まずみどりの窓口で切符を購入した。9月のド平日なのに大量に人が並んでいて、30分くらいかかった。券売機の方も大混雑で一体何があったのか謎である。

それから一旦ゲーセンに向かって2クレだけプレイした。明日のアップデートで終わってしまうイベント、チュウニズムデュエルがあって、まだ走りきれていなかったのだ。昨日しこたま進めただけあって無事完了。

今日は昨年11月の超大型アップデート以来始めての旧筐体でのプレイで、その60fpsと新筐体の120fpsが思ったより激しく違うことを体感できた。早い話、感覚が全然合わずひたすら下手くそだったのだ。

仙台駅に戻って新幹線の時刻を調べたが、ちょうど良い接続のものはつい10分ほど前に出てしまったらしい。そもそも大宮から黒部までは1時間おきにしかなく、今からだと指定席に課金しても見当をつけていたものには間に合わないようだ。到着時刻がその分遅くなってしまうが、まあ仕方ない。

1時間遅い列車に乗るとすると、仙台から大宮までは自由度が2だけあって、仙台でたっぷり待つか仙台と大宮で半分ずつ待つかということになりそう。もう一度ゲーセンに行く元気もないのでとっとと移動を開始することにし、後者を選択した。

新幹線の中ではずっと、昨日寝る前に読み始めたハーメルンを読んでいた。到着ギリギリまでかかって1作読了。「女王の女王」。

syosetu.org

面白かった。男女ペアの主人公はかなり好みの要素である。片方が原作キャラというのは、そもそも原作を読んでいなければ全く気にならない。主人公が常に混ぜっ返すような態度なのは少し気に入らないが、それ以外は堂々たる最強格として君臨しており、良い。原作の展開と合わせるためか序盤はあまり主人公ペアが主導権を握らなかったので、そこで焦らされた分その後の展開がまさに満を持してという感じで爽快だった。

駅から実家までは父の迎えの車。午後10時を過ぎてから帰り着いた。夕食・入浴を済ませ、布団に転がって本を読んでいたら日付が変わるくらいに寝落ちした。

09/15(木)

午前4時前に目を覚まし、また変わらず本を読んだり、ハーメルンを読んだりしていた。両親の起床に合わせて朝食を摂り、布団に戻ってまた午前8時頃に寝た。

午後3時半起床。寝ている間にDMが届いていた。見ると明日発売予定の「競技プログラミングの鉄則」という本に付属する演習問題のジャッジURLだった。正式な発売前に手に入れた方のブログ記事に載っていたらしい。コードゴルフの時間だ!

競技プログラミングの鉄則 演習問題集 - AtCoder

とりあえず最初の数問を見ると、すでに自明な最短コードが提出されていた。これは同じようにやっていては一つも取れないぞと思って問題をつらつら眺めていたら、B01も同じくらい自明なことに気づいた。よって問題番号がBから始まるものから埋めていくことにした。

ちょっと複雑な問題、簡単に縮みそうにない問題は容赦なく飛ばしていって、3時間くらいでBとCを一通り確認した。Aのほうは流石にもう目ぼしいものは残っていないだろうと思えたので、とりあえず一息ついて夕食を摂った。

夕食後、両親に「笑わない数学」というテレビ番組をおすすめされたので、録画が残っていた暗号理論の回とABC予想の回を視聴した。

暗号理論の方は手を動かしやすい話題ということもあって面白かった。暗号の歴史や素因数分解の困難性というアイディアを紹介したあと、実際にRSA暗号を計算するところまでやっていてびっくり。

ABC予想の回は微妙。そもそも{\rm rad}の定義を一切説明してくれなかったので以降の話も全部あやふやだった。この回でも頑張って手を動かせる話題を探したらしく、a=2^nb=3^nとしたときa+b素因数分解するとp^1または5^2しか現れないことを計算で確かめていて、この事実はなかなか強いことを言っているなあと思ったが、式変形が追えないのは残念だった。

後から{\rm rad}の定義を調べて納得。これは正整数に対し、それの互いに異なる素因数の総積を表す。このもとで、先ほどのa,bを用いてABC予想ステートメントa+b\lt K(\varepsilon){\rm rad}(ab(a+b))^{1+\varepsilon}から上の主張を導こう。ただしこのa,b\varepsilon\rightarrow 0のときK(\varepsilon)\rightarrow 1としたのは番組でも画面下に注釈があった。

a+b23を素因数に持たないため、abとは互いに素。よって{\rm rad}(ab(a+b))={\rm rad}(ab){\rm rad}(a+b)である。{\rm rad}(a+b)を移項することで(a+b)/{\rm rad}(a+b)\lt{\rm rad}(ab)={\rm rad}\left(2^n\cdot 3^n\right)=2\cdot 3=6。つまりa+b=\prod_i p_i^{e_i}素因数分解したとき\prod_i p_i^{e_i-1}\lt 6であり、p_i\ne 2,3なので、e_i-1\gt 0なるiが存在すればそれは(p_i,e_i)=(5,2)に限られるということがわかる。

部屋に戻ってまたコードゴルフ。すぐに眠気が来て、布団に転がって2時間ほど寝たあと、今度は午前7時までずっとコードを縮めていた。

途中C++のコードを書こうとしてファイルを開いたら、ABC266-Exを3D BITで解こうとしたときのコードが残っていたので、完成させて提出しておいた。座圧用のインデックスをBITにおける上位のノードに伝播させておらずバグっており、それを直したら無事4sec弱で通った。3Dセグ木は確か手元のランダムケースでも16secかかっていたはず。定数倍の差はそれほどまでにあったらしい。

atcoder.jp

朝食を摂り、少し日記を書いた後外出。地元で済ませる必要のあった用事を二つばかり片付けた。本来は木曜午後に行う予定だったが、思いがけず大量の問題が公開されたので今日に延期してもらったのだった。

正午前に帰宅。昼食を摂ってしばらく本を読み、午後2時前に就寝。

09/16(金)

午後10時を過ぎてから起床。夕食を摂って、TAの書類作成に取り掛かった。今日が期限である。印刷→押印→スキャンの作業に思ったより手間取ったが、なんとか日付が変わるギリギリに完了することができた。仙台にいる間にできれば良かったのだが、そもそもこの書類の提出を求められたのが火曜日で、気づいたときにはもう帰省秒読みに入っていたのだ。

少しコードゴルフしたりハーメルンを読んだりしてから読書に入った。午前4時頃になって本を1冊読了。「虚構推理」。

面白かった。ちょくちょく叙述トリックみたいなものが挟まれてその度にびっくりする。少なくとも序盤のそれの種明かしについては、漫画版だと大ゴマで強調されていたのでわかりやすかったが、小説版だと特に前後に空行があるわけでもなかったので、そういう演出を必要としないのは潔いなと思った。

解決編は100ページばかりを一気読みした。もともとどういうスタイルのミステリかはタイトルやあらすじにあるし、それがこの作品のポイントになっているのだが、実際に虚構の推理を実現されると、真実を知る自分でもそうかと思えるような納得の行く論理展開で、まさに狐につままれたようだった。期待以上。

次の巻である短編集を読み進めつつ、朝まで日記を書いていた。朝食を摂り、また読書に戻る。午前11時半就寝。

09/17(土)

午後2時45分の目覚ましで起床。午後3時からのAHC014に合わせたものである。開始と同時に問題文を読み、提出してまた就寝。

estie Programming Contest 2022(AtCoder Heuristic Contest 014) - AtCoder

今日は外食に行くと聞いていたので午後4時過ぎに起床する予定だったが、実際に起こされてみると午後8時でびっくりした。どうやら僕の睡眠時間が短く細切れだったのでなしになり、僕も目覚ましを掛けなかったのでこうなったらしい。かなり申し訳ない。

最近の自分の感覚ではこのくらいの睡眠時間でも頑張って起きて活動するのは珍しくなかったので、遠慮なく起こしてもらって構わなかったのだが、高校生の頃は非常に寝起きが悪かったのでその頃と同じ対応をされたんだなあと思った。

夕食を摂り、午後9時からABC269に出た。

UNICORN Programming Contest 2022(AtCoder Beginner Contest 269) - AtCoder

Aはdcで書いたら入力に負号が含まれていてWA。AWKで書き直した。そこからは特に工夫なくC++。Bはよい。CはいつものO(3^N)bitDPで使うループ。

Dは問題ページを開いた瞬間六角座標が見えてげんなりしたが、隣接マスへの差分がiまたはjの偶奇によらず決まる形だったのでかなり書きやすかった。AOJ-ICPCなどでは、そうでない面倒な座標の取り方をされた問題ばかりだったように記憶している。

Eは縦横それぞれ二分探索。[1,(l+r)/2]を聞いたのに[l,(l+r)/2]で判定してしまい1WA。Fは二次元累積和と同様マス(1,1)を左上とするようなクエリ四つに分解し、それぞれ気合いで計算する。最初は書かれている値の偶奇で0に書き換えられるか決まると思っていたので、M\bmod 2を見る場合分けをしてしまった。

Gは最初全部表向きにした状態からB_i-A_iを何個使うかという問題だと捉えた。この値はO(\sqrt M)種類しかないので、それぞれO(M)でdp遷移ができれば嬉しい。実際、|B_i-A_i|本のdequeを用意してそれぞれスライド最小値を行うことで、不可能な遷移を削除しつつ計算できることに気づいた。ちょっと割ったり余りを取ったりの操作が重いかなと思いつつ提出したら2973msで冷や汗を垂らした。

Exは2乗の木DPを畳み込みで高速化したら当然のようにTLE。結局解けず、7完25位。

コードゴルフ。AはAWK。最初に提出したのが31Bで、その後Bashからdcを呼び出す方法でも31Bを達成し満足していたが、30分くらい後になって改行を空白にしてもACできることを思い出した。これによりAWKのコードが1B縮んで最短となっている。Bは適当にRaku。[Z]で転置を再現するのは何回か使ったテク。

Cは普通にループするとNから減らしていくことになるので、その値をNから引いて出力することで昇順にした。また無限ループしないように条件を定めようとすると出力が1行足りなくなるのは、判定と同時に出力を行うことで解決。EはRubybsearch。他は手つかずである。

日付が変わったあたりからはずっと本を読んでいた。2冊読了。

「虚構推理短編集 岩永琴子の出現」。虚構推理シリーズの2巻として位置づけられているが、講談社タイガにおける発売日は最も早いのでちょっと分かりづらい。収録されている短編のうち第二話「うなぎ屋の幸運日」は他とは毛色が違い、岩永琴子以外の推理がメインとなっており印象的だった。

「虚構推理 スリーピング・マーダー」。シリーズ3巻となる長編、と言っても短編三つと中編が緩やかに連携する感じだった。この中編は主人公ペアの異質さ悪辣さが前面に押し出されていて非常に楽しく読めた。と言ってもただ職務に忠実なだけだったと説明はあるが。虚構の推理を単純にラストに持ってくるのではなく、そこからもう一捻りあったのには驚かされた。

朝食を摂り、布団に入ってしばらくハーメルンを眺め、午前9時就寝。

09/18(日)

午後4時半に起こされた。今日こそ外食、焼き鳥屋に行く。

開店から数分後には店に着いたものの、その時点で待ちが数組いて、当然今いる客も食事を始めたばかりなのでテーブルに案内されるまで1時間半ほどの待ち時間があった。その間にハーメルンを1作読了。「真の実力はギリギリまで隠しているべきだったかもしれない」。

syosetu.org

全体的にギャグ風味。こういうのはサッと完結するのが一番好みで、これも11話で一応の完結を見た。そこまでは面白かった。しかしその後も連載は続いている。蛇足とは思わないが、相変わらずギャグ展開を多めに混ぜ込むので風呂敷が広がり続け、だんだんよくわからなくなってきた。さらにエタっているのでちょっと印象は悪くなった。

1時間弱食事して帰宅。

帰ってきて、今日はコンテストが何もないので寝っ転がってハーメルンを読んでいた。また1作読了。「女王様と犬」。

syosetu.org

雪ノ下陽乃の高校時代をメインに据えるにあたって関係者の学年が色々ずらされており、特に城廻めぐりと同級生になるというのはかなり目新しかった。内容も非常に面白い。雪ノ下陽乃の印象は原作のような悪いものではなく、ただ万能なサディストという描かれ方をしていて、ヒロインとして違和感がない。まさかくっつくとは、というのは原作を読んでいるときも違う相手に対して思ったことか。エピローグとして未来の風景が描かれるのも大好物だった。

入浴後はハーメルンをチラチラ読みつつずっと日記を書いていた。完成しないまま午前5時過ぎ就寝。

今週は帰省にお誂え向きでコンテストが全然なかった週だった。特に日曜日が丸々空くというのは何時ぶりだろうか。その時間で参加記を完成させるでもなく、相変わらずハーメルンに費やしてしまったのは残念だが止めようがない。そうやってずっと実家でグダグダしていたこともあり、この週記は12000文字弱と普段に比べ量が控えめになった。

週記(2022/09/05-2022/09/11)

09/05(月)

午後4時過ぎ起床。布団から何とか這い出して、半からインターン先の定例会へ。

進捗報告は先週とほぼ同じで、試したことがダメだったのでまた新しい方針を実装しますというだけ。勉強会はPythonについて、3.6以降のバージョンアップに伴う新機能を紹介するものだった。このあたりでコードゴルフ的に一番インパクトがあったのは代入式、いわゆるセイウチ演算子だろう。それに関しても面白い話が聞けた。

Pythonに変数のスコープなどあってないようなものだが、リスト内包表記だけは特別で、ちゃんとスコープを作るらしい。このことはこれまでは、ループ用の変数が外の変数と被っていても外のものを書き換えないということを意味していた。ところが今、リスト内包表記で実行するループ内で新しく変数に代入する場合、それはループを抜けても保たれる。つまりスコープはもはや正しく動作していない、という話があるそうだ。

これに関係するのかどうか知らないが、リスト内包表記のリスト部分で代入式を使おうとすると文法エラーとなる。よく引っかかってしまい、おかしな制限だと思っていた。裏にこういう背景があったのかもしれないと思えば納得もできそう。

終えてからはずっと先週の日記を書いていた。ARCの残りと5hについてを書き上げればとりあえずは完成なので、これまでに比べると完成までは非常に近かった。ちゃんとそこから校閲まで済ませて、午後11時過ぎに投稿。

しばらくコードゴルフをした後、午前1時くらいに布団に入ってハーメルンを読み始めた。午前3時過ぎ寝落ち。

09/06(火)

午前8時過ぎに目を覚ました。昨夜読み始めたハーメルンを読了。「知識も無いのにポケモン世界にチート転生したが何も面白くない」。

syosetu.org

主人公にはポケモンバトルの才能という転生チートがある。しかしそれの実現方法があまり好きではなかった。ネタバレになってしまうが、主人公がチートに操られる感じだったのだ。能力に振り回されるのともまた違うとは言え、やはり基本は主人公が能力の手綱を握っていてほしかった。そういう能力を持っているが故の性格で主人公がポケモンのことをあまり顧みていないのも辛い。

眠気を待ちながら別のハーメルンを読んでいたが一向に眠れなかったので起き上がった。ゴミを出してからしばらくコードゴルフして、午後1時過ぎに学食へ。昼食を摂り、予約していたラノベを受け取って帰ってきた。

DMOJのコンテストが終わっていた。先週土曜日深夜の3時間で参加したもの。ここに感想を書いておこう。

An Animal Contest 7 - DMOJ: Modern Online Judge

P1はConnect 4を知らず問題文が読めなかった。w\times hの盤面にトークンを「落とす」というのだから実質3次元の盤面なのかと思ってしまった。張られていたWikipediaへのリンクから実際の画像を見て理解。それからもコーナーケースにはまり込んで2WAした。h=1なら先手四つ後手三つのトークンのためw\ge 7が必要。w=1なら交互に積み重なるだけなのでダメ。残りは自明な条件のh\ge 4\lor w\ge 4をチェックすればよい。

P2は出力する木の根を指定していないのにジャッジで先祖・子孫の関係を使うらしく、パッと見意味不明でclarでも投げようかと思った。しかしよく考えると、元の木における関係を見ることで出力の条件からどの頂点が根であるべきかは高々一意に定まる。そこまでジャッジで面倒を見てくれるのだろうと判断して解いた。

解法は深さの偶奇で木を分けるというもの。これでK=2が達成できて最適、と思って書き始めたが、根と隣接している頂点を一つの木にまとめられず、もう少し考えることになった。考えた結果、根と隣接している頂点はすべて出力した木のどれかの根である必要があるということが分かったので、K=2とは限らないもののK最小は達成できている。出したら通った。

P3はiを固定してi\lt j\le Nに対する和を一度に求める。一番近いポータルからの距離はまとめて線形時間で計算できるので、最初に求めておく。これを使うとある地点からある地点までポータルを経由して移動するための時間が計算できる。

さて、よく見ると、直接向かうよりポータルを使うほうが早く着ける地点は右端からの区間になっているため、その端点を見つければ適当な前計算で一気に和が求まる。この端点のインデックスは、直接向かうときの時間を考えることで、iが増えるにつれ単調に増加するとわかる。よって尺取り法の要領でこれまた線形で求まる。N\le 10^6でTL 1secと\logを付けた解法を落としに来ている制約。最初は遅延セグメント木と二分探索を使っていたが、\log二つで当然のようにTLEしたため書き換えた。

P4は大変。一か所にしか出現できないものと端に出現するものは確定し、それ以外は出現できる範囲が区間になる。また答えとなる数列において、注目している数より大きいか小さいかだけ考えると、最初にあったところから左右それぞれ出現範囲より一つ広い位置まで、これが交互に現れなければならない。以上の条件を実装したら通った。これ以上詳しい解説を書きたくない。assertを大量に入れつつ実装し、ランダムケースでチェックすることで何とか解けた。

P5は典型。木においてすべての頂点を通る最短パスは、直径の端点を結び、直径上の辺を1回、それ以外の辺を2回通るようなものである。今回は特に、通る頂点を順に並べたものが辞書順最小となるパスを聞かれているので、まず直径の端点となれる最もインデックスが小さい頂点を求めなければならない。全方位木dpで最も遠い頂点までの距離を管理したが、よく考えると1本直径を見つけてその端点から直径と同じだけ離れた点を列挙するほうが簡単だった。

あとはdfsっぽく計算。直径上にないため後から親まで戻ることが確定しているような頂点は、記録するタイミングをある程度自由にずらしてよいので、もっと小さい番号の頂点が下にあればまずそちらに降りて行く必要がある。これを忘れて3WAした。

P6はbitsetを使った愚直を書いて終了間際に最初の部分点だけ取った。合計510点で2位、レートは2475→2666(+191)でhighest。今回は何とかなったが、やはり中盤の重実装がつらい。後ろのほうにド典型が置かれていることが多いので、詰まったときもちゃんと先の問題を確認するよう心掛けたい。しかし実際のところP4の公式解説はかなり頭が良かったので、作問者から見れば別に重実装でもなんでもなかったようだ。

しばらくインターンに関するコードを書いて、午後6時から1on1に臨んだ。今回試した方針は非常によさそう。まだ試し切れていない細部の実装について画面共有しながら少しずつ手を加えてみて、平均的にかなりうまくいっている出力が得られた。これ以上はハイパラ調整に足を踏み入れることになるが、今は出力の評価を目で見るだけで行っているし、手持ちのデータも少ないので、それは今するべきことではないという結論になった。

ということでタスクが一つ完了。次は何をすればよいかと聞いて一つ紹介され、関係するコードの在処を含めてしばらく説明を受けた。以上2時間くらいのミーティング。終盤眠くなってまたしても意識を飛ばしてしまったタイミングがあり、かなり申し訳ない。今日急に新しいタスクをくださいと言ったのがミーティングを長引かせてしまった要因。眠気に耐えられないならちゃんとそう白状するべきだった。

布団に滑り込み、午後8時半から午後11時まで仮眠を取った。起きて食事し、午後11時半からCF #819 combined。

Dashboard - Codeforces Round #819 (Div. 1 + Div. 2) and Grimoire of Code Annual Contest 2022 - Codeforces

Aは(l,r)として(1,n-1),(2,n),(1,n)のどれかしか考えなくてよい。2乗が通る制約だが、それぞれ線形時間で計算できる。Bは最大の要素以外は同じ数を偶数個ずつ用意する必要がある。ほとんどを1で埋め、nの偶奇に応じて残り一つか二つを調整する。Cは開きかっこの深さを見て、同じ深さのペアで間により浅いかっこがないものを繋ぐことになる。stackで管理。

Dは辺の数が(n-1)+3以下なので、全域木に高々3辺追加したようなグラフ。とりあえず全域木を一つ取って赤で塗り、残りの辺を青で塗ることを考える。青い辺がループになっていなければよい。ループだった場合は、青い辺uvを適当に取り赤い辺でu-vパスを作ると、そのパスは必ず長さ2以上だから、パスの適当な1辺と色を交換することでループを解消できる。3辺を乱択してループができていないかチェックする解法もあるらしい。

Eはp_i-(p^{-1})_iにおいてi\leftarrow p_iとすることで(p^2)_i-iが得られる。これは逆順列の定義から導けるし、pからn頂点n辺の有向グラフを作って(p^{-1})_i\rightarrow i\rightarrow p_iというパスを観察することでも言える。今pは順列だから、条件を\forall i.\;|(p^2)_i-i|\le 1と書き換えることができ、ここからp^2の形を観察すると各ループがi\leftrightarrow iまたはi\leftrightarrow i+1となることがわかる。

p^2がそのようなループからなるpとはどのようなものか。pにおける長さLのループはp^2において、Lが偶数の時長さL/2のループ2本に、奇数のとき長さLのループ1本になる。よってp^2における長さ1のループはもともと長さ1だったか長さ2が分裂したものであり、長さ2のループは長さ4が分裂したものである。ここまでわかれば、あとはp^2における長さ2のループの個数を全探索して組み合わせ計算を行うことで答えが求まる。

このようなp^2に関する考察は何回か見たことがあるし、特につい最近もTLで流れてきた。その時改めて自分の中で解決しておいたので内容を完璧に覚えており、今回スムーズに考察を進められた。

Fは面倒。c_i\leftarrow c_i+\sum_{j=1}^{i-1}d_jと定めることで信号間の移動時間を0にしておく。実家dpを考えると、区間[L,R)で青になる信号に突入した時、点Lにおける値は新たに計算、区間[L+1,R)の値はそのまま、残りは\inftyという更新ができればよい。同じ値を持つ区間をまとめれば、信号ごとに区間をいくつか削除して定数個足すことで表現できるため、更新が十分高速。点Lにおける値はそれ以前の\inftyでない最も近い点を選んで遷移するだけでよい。

Gは面白い。まず最初にaがすべて等しい場合を取り除いておく。これはどのような順序で操作しても条件を満たす。さて、最終的に揃える先をAとする。これはA\ge \max aを満たす。a_i\lt Aなものを抜き出して同じ値をまとめると、そのうちでb_i=1となるものは高々一つしかない。なぜなら、二つ以上ある場合、それらの間で操作後の値が食い違ってしまうから。

ここでa_i=\min aを調べると、実はAが決まる。まずb_i=0がある場合、対応するa_iは操作しても絶対に変わらないので、a_i\lt\max a\le Aより不適。よってb_i=1である必要があり、先ほど見たようにそのような要素は高々一つ。特に今回はちょうど一つであり、A=n-1+\min aとなる。あとはa_iが同じ要素をまとめ昇順に見て、操作列に挿入することを考えればよい。挿入箇所が一意に定まるのでうまくいく。A=a_iのときだけ少し式が変わる。

Hを見て諦め、残り時間はABをlockしてHackを試みていた。結局何も落とせなかったのだが、システスでRoomのAが二つ落ちていた。n=2で壊れるコードと配列外参照。後者はともかく前者はちゃんと見つけられるべきだった。

コンテスト終了直前にGの\min aに対する式が間違っているように見えて冷や汗を垂らしたが、上に書いたように答えが0にならない条件がかなり厳しいので、結果的には合っていた。

システス前6位でpredictorがすごい値を出しており、心臓に悪い。ジャッジが走っている間は他のことに手を付ける余裕もなく、YouTubeを眺めたりしてただ時が過ぎるのを待っていた。結果は全問通って7完、順位が一つ上がって5位、2954→3111(+157)。レートの更新を待ってツイートした。

2998を踏んでからほぼ一年となる。感慨深いタイミングだ。

4完15位で2952→2998(+46)。

週記(2021/09/27-2021/10/03) - kotatsugameの日記

しばらくリプライの返信をしつつ噛みしめていた。午前4時半に布団に倒れ込み、少しハーメルンを読んだところで寝落ちした。午前5時だった。

09/07(水)

午前8時半起床。昨日のCFで問題の剽窃が発覚し、Unratedになっていた。

Round #819 Unrated due to Problem Theft - Codeforces

良いタイミングだったんだけどな、とか、サークルSlackやインターン先Slackで報告したのを取り消しておかないとな、とか考えていたはず。以下に引用したツイートで述べているように、自分ではそれほど気にしているつもりもなかったが、しかしこの日は一日なんだか調子が悪かった。

剽窃があったのはF問題。両隣のEとGに比べると実装が面倒で面白くないと感じる。わざわざこの問題を選んで引っ張ってきたというのは意味不明。犯人はWriter三人のうちただ一人だけ紫だった奴で、この一問しか担当していないようだ。橙二人が用意したコンテストに質の悪い一問を追加してUnratedにするのって本当に余計なことしかしていない。確か#810で剽窃した奴も紫だったな。そもそもその程度のレートで問題を提案できるシステム自体に納得いっていない。5桁に易々届く参加者数には見合っていないだろう。

しばらくハーメルンを読んで午前11時半ごろまた寝落ちした。午後10時半起床。ずっと布団でハーメルンを読んでいて、3作読了。

syosetu.org

「真顔のシングル厨がアローラ入りするお話」。原作のアローラ地方の設定が重くてびっくりした。主人公の手持ちポケモンがどれも珍しく強力で、それらが注目を集めたりするシーンは良かった。ただヒロイン二人がどちらもヤンデレなのが好きではない。そもそもヤンデレを受け付けないから。

syosetu.org

ゲームで使っていたパーティーがたまたま手に入るところから始まる。この導入時点ではポケモンたちが主人公に対してどういうスタンスなのか、同じ主人だと認識しているのかなどわからず不穏だったが、以降は面白い。パーティーに振り回されまいとちゃんと努力してはいるものの、結局勝敗についてはポケモンが強いというのが大きいし、言動も人を煽るようなものなのでSNSが炎上気味ということで刺激的だった。

syosetu.org

多分途中まで読んだ記憶がある。少なくとも最初の2話3話には見覚えがあった。最近読んでいるポケモン二次創作とは毛色が違い、バトルシーンはあまりなくほのぼのと進む。たまにはこういうのも良い。

しばらく日記を書き、朝方になってからTCO Finalsのための提出物を作り始めた。今日は自己紹介動画の撮影。わざわざこのためにスマホアームを買ったり床屋に行ったりしたのがもう2週間も前のこと。ちゃんと原稿も用意した上で、面倒すぎて放置してしまっていた。撮影の前に英語の発音やアクセントの修正を試みたもののよくわからなかったので、諦めて日本語英語で押し通すことに。

1時間程度かけて何度か撮り直しを行い、ついに完成。ちゃんと音が入るよう大きな声で話したり、頑張って口角を上げようとしてみたり、いろいろ考えることがあってそこそこ大変だった。原稿は動画時間のことを何も考えずに作ったので、実際に撮ってから制限の15秒に見事に収まっていることに気づきびっくりした。

午前8時に布団に入った。明日のセミナーが午後1時からなので、移動時間も考えて睡眠時間4時間ちょっとの予定。ここでなぜかハーメルンを開いてしまい、気づいた時には午前10時になっていたので、今日は寝ずに大学に向かうことにした。幸い起きたのが午後10時半だったから耐えられるだろうとの見込み。

正午くらいに布団から出て準備を始めた。外は雨が降っており、川内の生協に寄るのが面倒だったので、とっとと山に登ってしまって山の上の生協で昼食を調達したい。そこは今12時45分までしか開いていないので、いつもより早めに家を出る必要があった。何とか間に合って無事総菜パンなどを購入。教室で食べた。

午後1時からセミナー。まず最初の2時間は同級生の発表だった。前回のことを比較的覚えていたので、今日はかなり集中して聞けたと思う。変数や関数の型を丁寧に確認することで添え字でもあまり混乱しない、が、その代わり本当に丁寧に見ないと厳しい。今はD_{i+1}=(D_i\rightarrow D_i)と定められた型の話が続いている。D_{i+2}=(D_{i+1}\rightarrow D_{i+1})=(D_{i+1}\rightarrow(D_i\rightarrow D_i))くらいまで展開されると勘違いしやすく、2重になったラムダ式の型で今日も引っかかってしまった。

続いて博士課程の方のセミナー。もう何度か同じ内容の説明を受けているが、今日はぐんと理解が進んだと感じる。話されていることに対する知識がついたので英語もより聞き取れるし、何より対面+黒板発表というのがいい。板書の最中に疑問が生じたらすぐさま質問できて、そのとき英語だけでなく身振り手振りでコミュニケーションが取れる。これまではスライドとオンラインが多かった。

午後6時帰宅。疲れ果てているがしばらくコードゴルフをして、午後9時くらいに仮眠に入った。ここで日記の日付も変えておこう。

09/08(木)

午後11時半起床。すぐECR135に出た。

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

Aの題意が把握できず少し迷走した。最大値を取るインデックスを出力すればよい。

Bは最後の操作でx\lt p_n\le nのもとx+p_nを最大化するのが最適。これはx=n-1p_n=nで達成できる。さらにp_{n-1}=n-1とすると、p_{n-2}まででx=0とするだけで条件を満たせる。残りはn-2,n-1,\dots,1と並べればよいと思った。しかしサンプルでWA。よく見るとx\ne 0x=0が交互に現れるため、nが奇数の時は少し変える必要がある。単に先頭に1を持ってくればよい。

Cはabをそれぞれpriority_queueに入れ、大きいものから比較していく。ダメだったらfを適用して戻す。fは値を急激に小さくするので十分高速、くらいの考察はしたが、fを2回適用すると1になるというところまでは考えなかった。Dは区間dp。Aliceの操作とBobの操作を一組にして遷移を計算した。かなり面倒。prependではなくappendだと思ってしまい1WA。

Eは難しい。最初にすべて赤のほうに揃えておき、いくつ黒にするかを考えることにする。Y個だったならb_i-a_iの大きいほうからY個選んで赤から黒に切り替えるのが最適。このYをうまく全探索する問題だと思って、x_j\mid(n-Y)y_j\mid Yから考えていたが、結局別のところから解いた。

x\cdot x_j+y\cdot y_j=nの解となる整数x,yを拡張ユークリッドの互除法によって一つ求める。なければ-1。求めた解を(x_0,y_0)とすれば、すべての解はg=\gcd(x_j,y_j)として(x_0+ky_j/g,y_0-kx_j/g)と書ける。今、Yの変化に対する答えの値の変化は上に凸であるため、Y=y\cdot y_jとしては頂点に近い位置を探索すれば十分。x_jy_j/gずつしか変化しないのに注意して、定数時間で頂点の左右の点を取得することができる。

Fが全く分からなかったのでGに進んだ。mが小さいのでO(2^m)くらいかける方向で考えてみる。最初からあるランタンのpowerの決め方であって、地点の特定の部分集合のみを照らせるようなものが数え上げられると嬉しいだろうか。結局答えを求めるときにもう一度O(2^m)かける必要がありそうに見えるが、あらかじめゼータ変換か何かしておけばO(m)にできる。新しいランタンのpowerを適当に決めた時、それによって照らせる地点の集合がO(m)通りしか存在せず、それぞれに対応する場合の数がこの前計算で求まっているから。

あとは最初の決め方の計算。条件を緩めて数え上げた後、包除原理でピッタリの値を求めることにする。「この地点は絶対に照らさない」という集合を決め打って数え上げることができた。照らさないと決めた地点であって隣接するものを取ると、その間にある各ランタンのpowerの上限が決まる。よってそれらを掛け合わせればよい。地点のペアすべてについてその間のランタンの分だけあらかじめ計算しておくと、この部分はO(m2^m)で計算できる。包除原理についてもメビウス変換で書けた。ゼータ変換かもしれないが、とにかくその類の計算が適用できることだけが重要。

Fに戻った。結局最小重み二部マッチングになりそう。マッチング先の頂点は必要になったら生成することにすればよい。しかし頑張って実装したものの合わず、コンテスト終了。方針としては合っているようだったので、マッチングをずらすときマッチ先の頂点の値がずらす前より増える一方だと思い込んだのが間違っていたのだろう。結果はF以外の6完で9位。

DはBobが絶対に勝てないらしい。正直これも証明がつけられていないが、さらに解説のコメント欄ではDrawとなる文字列がA+B+{\rm rev}(A)、ただしBは先頭から2文字ずつ同じ文字が現れる、という形に限ることまで議論されていた。

Eはx_jy_jのうち大きいほうで探索することで通せるらしい。このときクエリごとにO(n/\max(x_j,y_j))かかる。\max(x_j,y_j)=kとなるペアがc_k個あるとすれば、重複を取り除いてc_k\le 2k-1が言えて、さらに\sum_k c_k=mでもある。この元でkが小さいものをたくさん集めると\sum_k n/k\times c_kが最大化され、最悪ケースになる。そのときk\le\sqrt mではc_k=2k-1、以降はc_k=0となるから、計算量はO\left(\sum_k n/k\times c_k\right)=O\left(\sum_{k=1}^{\sqrt m}n/k\times k\right)=O(n\sqrt m)で確かに間に合っている。

TCO Finalsに向けた提出物は、最後にアンケートが残っている。09/09締め切り。とりあえず質問をザッと確認してみて、回答必須のものが思ったより少ないことに安堵した。しかし最後に自分の写真を添付する必要があってびっくり。明日ホスフィンと旅行に行く予定なので、旅先で撮ってくることにしよう。

旅行のために今日は早く寝なければならないと思い、午前3時頃には布団に入った。しかしそこから読み始めたハーメルンが章のクライマックスで非常に面白く、結局就寝は午前5時過ぎになった。

09/09(金)

午前7時、執念の起床。軽く持ち物を用意して出発。

今日は青春18切符で平泉に行く。仙台で暮らして5年目になるが、いつも新幹線と地下鉄にしか乗らないので、初めて仙台駅の在来線ホームに立ち入り感動した。途中の駅で宮沢賢治作品モチーフのステンドしおり2種類を購入しつつ、午前10時半ごろに平泉駅に到着した。

すぐ横のレンタサイクルで電動自転車を借り、今日は一日これで動き回る。初めて電動自転車に乗ったがかなり快適だった。金鶏山周辺の道は坂ばかりだったし、達谷窟毘沙門堂はそれなりに遠かったので、たった100円をケチって普通の自転車を選ぶようなことはしなくて大正解。

まず中尊寺に向かった。参道が急でかなり恐怖感があった。ここでは本堂や金色堂の他にもありとあらゆるお堂を練り歩き、昼過ぎまで過ごした。本堂本尊の写真を貼っておこう。金色堂をはじめ結構な数のお堂は撮影禁止だったが、これは特に何も書かれていなかった。調べた感じ、最近作られた仏像だからという理由がありそう。

あとは、お堂にペタペタ貼られているお札が千社札と呼ばれることを知り、それにも注目していた。これまたほとんどのお堂では貼り付け禁止になっている中、特に書かれていないお堂もあって、そこの柱にはお札だけでなく筆やペンによるサインもたくさんあった。平成終わりごろの日付のものがいくつもあったが、令和に入ってからのものは見つけられなかった。

金色堂覆堂の前でホスフィンに写真を撮ってもらった。アングルも含め昔よく読んでいた本に描かれていた景色で、非常に既視感がある。ただ絵面がパッとしない。そもそも中尊寺は撮影可能な場所も少ないし、写真映えを求めるスポットではなかった。

日本にのこるなぞのミイラ | 株式会社 理論社 | おとながこどもにかえる本、こどもがおとなにそだつ本

下山して駐車場の周りの食事処で昼食。次は毛越寺に行く予定で、途中に金鶏山があるので寄ってみた。しかしここはシンボルとして有名なだけで、登っても何も面白いものはない。麓に廃寺があったらしいが見逃し、急な山道を必死に歩いて山頂に着いてみたら、ただ塚があるだけで周りは鬱蒼としており見通しもよくない。意気消沈して下りた。足を滑らせたらそのまま転がっていきそうなほどの勾配で、登るより下りるほうが格段に怖かった。

毛越寺。「夏草や 兵どもが 夢の跡」という有名な句の、新渡戸稲造による英訳の碑があった。「The summer grass / 'Tis all that's left / Of ancient warriors' dreams.」。'Tisという単語を知らず、調べてIt isの省略形であることを知った。庭園の池をぐるっと一回りして、甘味処でかき氷を食べて出た。

次は20分ちょっと自転車を漕ぎ、達谷窟毘沙門堂へ。ここはフォトジェニックでよかったので、またホスフィンに写真を撮ってもらった。自分でも撮ったので一枚貼っておこう。サムネ用。全体を収めるためには横向きで撮りたくなるが、これだと画面の上まで崖で覆われて窮屈さを強く感じる。そこで縦向きで撮ると、せり出した崖の上の部分まで見えて、圧迫感が自然の雄大さにすり替わってくれる、気がする。

本当は温泉に入る予定だったが、レンタサイクルの閉店時間に追われながらは嬉しくないので、いっそ帰ってから銭湯に行こうということになった。電車に乗って仙台へ。乗り換えで立ち寄った一ノ関駅ピカチュウポケモントレインの顔出し看板があって、そこでもホスフィンに写真を撮ってもらった。以上3種類のどれかを選んでアンケートに添付しよう。

今日の行き帰りの電車では昨日のハーメルンを続けて読んでいた。1作読了。「自分はかつて主人公だった」。

syosetu.org

主人公自身が強いし、手持ちポケモンが伝説ばっかりで最高。かつての力やパーティーを取り戻すという展開で、序盤の少し弱くなった主人公描写に耐えたぶんクライマックスは非常に興奮した。ストーリーとしても面白い。人間的成長という一見ふわふわした話が主人公の実力とダイレクトに連動している。だから昨日睡眠時間を削ってでも一気読みしたし、今日も電車の中で寝るつもりがずっと読んでしまったのだ。

午後6時半ごろ仙台駅に到着。たいぺーとも合流して地下鉄に乗り、サンピアの湯というスーパー銭湯に向かった。久しぶりの大きな風呂で非常に良い。サウナに入った後水風呂に浸かったら、今日一日ずっとあった眠気が一瞬だけ完全に吹き飛んで非常に爽快だった。その分風呂から出て併設のレストランで食事しているときには一気に眠気が来て大変だった。

その後寝転べる場所に移動して2時間ほど漫画を読んでいた。虚構推理の1巻と、転スラの10巻から15巻あたり。前者は小説版を積んでおり、序盤を漫画で確認することで読む意欲を高めようとした。無事高まったものの本当に小説版を読むかは不明。後者については、神之怒のシーンが大好きなので探していた。無事見つかってよかった。

午後11時過ぎに銭湯を出て、日付が変わったあたりで帰宅した。また少し汗をかいてしまったのでシャワーを浴び、布団へ。旅行で撮ってきた写真を一度にツイートした。

鐘楼の床に穴を開けるのは何故だろうか。音の響きをよくするためという理由が思いつくが、調べてもヒットせずよくわからないままである。

午前1時就寝。

09/10(土)

午前7時半起床。ABC264の賞金が届いていた。

少しハーメルンを読んで午前9時過ぎに布団を脱出。睡眠時間が足りていないので、夕方また仮眠するつもりである。

しばらくコードゴルフした後、昼頃にTCO Finalsのアンケートを書いた。写真は一ノ関駅で撮ったものを使った。提出時刻はアメリカのタイムゾーンではギリギリ09/09なので、締め切りに間に合ったと言えるだろう。このためにわざわざ朝から起きていたのだ。

布団に戻って仮眠の体勢に。しかしダラダラハーメルンを読んでしまって、結局寝入ったのは午後4時前だった。次に午後8時起床。あと30分くらい眠れるかなと思ったのにTLを見ていたら寝損ねた。

最初から午後8時半に目覚ましを設定するのは怖いのに、午後8時からもう30分寝るのが怖くないのは一体なぜだろうか。恐らく後者は、その時の眠気が強すぎてとにかく寝たいという気持ちでいっぱいなのだろう。実際このせいで寝過ごしたことが何度かある。

食事して午後9時からABC268に出た。

UNIQUE VISION Programming Contest 2022 Summer (AtCoder Beginner Contest 268) - AtCoder

AはRaku。Bはsed。Cは少し難しい。テーブルがk/N周回っているとき喜ぶのは(p_i-i-k)\bmod N-1,0,+1であるような人iだから、(p_i-i)\bmod Nをカウントしておくことでkごとに人数が定数時間で求まる。

Dはdfsで全探索。計算量を考えずに提出したら、そもそもNMを取り違えていてTLEやREを出してしまい、もしかして間に合わないのかと震え上がった。バグに気づいて提出しなおし、WA。|X|\ge 3をチェックし忘れていた。この条件いる?

Eは気合いで差分更新。Fは各Sについてそれだけ考えた時のスコア、数字の和、Xの個数の三つを計算すると、これらの組み合わせで全体のスコアが計算できる。式を見ることで、二つのSの結合順序を入れ替えたときにスコアが上がる条件が求まる。ちゃんと順序になっているので、それを比較関数にしてSをソートすればよい。

Gは各Sに対する答えが、i=1\dots NについてS_iが辞書順でS以下となる確率を足し合わせたものになる。S_iSのどちらかがもう一方の接頭辞となる場合は関係が確定するので、それ以外を考えたい。これは先頭から見て初めて食い違う位置の文字の順序における大小関係から定まって、冷静になると大小どちらも26!/2通りずつである。なので最初に弾いた接頭辞の部分だけ真面目に計算すれば十分で、Trie木で求まる。

Exはよくわからない。そのまま残してはいけない区間を列挙できれば、貪欲法で答えが求まる。その区間自体もSTたちを連結した文字列のSuffix ArrayとLCP Arrayを使うことで計算できそうだが、自分が考えた方法では各Tに対してSの位置を見ていたので、STも全部同じ文字というような最悪ケースでは間に合わなさそうだった。そこでGのコードを流用して、別のTが接頭辞となっているものを無視することにした。これだととりあえず先ほどのケースはうまくいくし、考えてもそうひどいケースが見つからない。信じて提出したら1100msくらいで通った。

全完18位。AのFAだった。Dの計算時間は、そもそもM+1個候補を生成すれば必ず見つかるし、全通り生成しても十分高速らしい。GはPとしてa-zz-aの二通りのみを考え、その平均を取ったものが答えになるようだ。言われてみればそう。ExはSの位置に対してT、特に|T|が最短のものを探すと全体で線形時間になるため、接頭辞云々で枝刈りする必要はなかった。

コードゴルフについて。これは以降二つのコンテストの前後でやっていた結果も含む。AはFAだったRakuのコードがそのまま最短。BはsedよりVimのほうが4Bも短くてひっくり返ってしまった。CはPerl。Fは数字の和とXの個数を複素数の形で持つと偏角ソートしたものが求める順序になって、かなり縮んでくれた。Gは上で触れた、二通りのPに対して計算する方法。他は手付かず。

午前0時からSRM837。

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

最初15分くらいエラーで提出できず、Unratedになった。普段と違う時間にコンテストを開催してエラーが起こるというのは昔AtCoderでもあった記憶がある。その時はジャッジサーバが起動しておらず、序盤の提出を捌けていなかったはず。同じ原因かはともかく、これは同情できる。ただしUnratedの理由が「As the disruption is taking longer than we hoped」だったのは信じられない。もしかして数分で復旧したら続行するつもりだったのか?

そういうことがありながらもちゃんと全問解いておいた。EasyはHの昇順にソートして使う。W_i\times H_i\gt 1という制約が何なのか不安になったが、通常のcubeと同じサイズのブロックがあると、それを他のブロックの上に置けないかどうかはどう決めたってややこしいので、避けた形だろうか。

Medはdp。バケットごとに使うバックアップの個数を決め打つと、できるだけ偏らないように分割するべきなので、かかるコストが閉じた式で計算できる。状態数O(HT)、遷移がO(T)なので十分間に合う。バックアップは使い切るべきだと思っていたが、念のため何個使うか全探索して答えとした。実はバックアップを一切使わないケースというのもあるらしく、それで落ちていた人がいた。

Hardは気合い。文字列のインデックスと、そこまでに使ったupperBoundsの集合を持ってdpする。遷移は特に工夫せず丁寧にチェックするだけでよい。問題はgoodとbadの区別。ある分割がgoodであるとは、分割後に隣り合う二つの文字列a,ba+b\ge b+aを満たすことである。なので、dpするとともにgoodに対してそれを達成するaを列挙しておき、新しくbを足したときgoodのままかbadになるかチェックするという方法を考えた。特に上の比較はちゃんと順序になっているので、aとしては最小と最大しか保存しなくてよい。

チャレンジフェーズは何もせず。システスは無事全部通って全完5位となった。

午前2時からMHC R1が始まったので出た。24時間で終了するのでここに感想を書く。

Meta Hacker Cup - 2022 - Round 1

A1は簡単、どれくらいrotateしなければならないか決まるのでK=0に気を付けつつチェック……と思ったらvalidationで落ちた。冷静になるといろいろコーナーケースがある。まずK=0の場合rotateできないのはサンプルにもある。次にK=1のとき、これは逆に必ずrotateしなければならないので、最初からA=Bだった場合はダメ。

以降K\ge 2として、rotateできる範囲が[K,(N-1)K]なので、(N-1)K-K+1\ge Nならどんな状態も達成できる。式変形するとN\ge\frac{2K-1}{K-1}=2+\frac 1{K-1}\gt 2、つまりN\ge 3ならOKだがN=2はコーナーとなっている。実際このとき、rotateする幅とKの偶奇が等しい必要がある。以上を実装して提出。A2はB+A+Aに対してZ-algorithmを適用することでrotate幅を全探索できる。

Bはいつもの。縦横分割し適当にソートすれば求まる。B1とB2で同じコードを出した。Cはしばらく考えても糸口がつかめなかったので諦めた。

ハーメルンを1作読了。「東方神殺伝~八雲紫の師~【リメイク】」。

syosetu.org

「俺の家が幻想郷」の作者の別作品。中二臭さがかなり好みだったのでこちらも好きだろうと思って読み始めたが、実際かなり良かった。原作キャラより圧倒的に強いオリキャラたち、オリジナル能力、二つ名……。一方、せっかく幻想郷にいるのにオリキャラばかり出てきて原作キャラの出番がどんどん減ってしまったので、それはちょっと好みから外れていた。リメイク前はオリキャラたちのインフレがもっと激しかったらしいのでそちらも少し気になる。

朝からは日記を書いていた。午後2時くらいに切り上げて布団に入り、1時間ちょっとラノベを読んでから寝た。

09/11(日)

午後8時半起床。食事して午後9時からARC148に出た。

AtCoder Regular Contest 148 - AtCoder

AはM=2で多くとも2通りが達成できるので、1通りが達成できるか調べる問題になる。つまりA_i\bmod Mがすべて同じ値になればよく、ここからM\mid(A_i-A_j)が出る。よってM\mid\gcd(A_2-A_1,A_3-A_2,\dots,A_N-A_{N-1})で、\gcd\pm 1かどうかを調べればよい。0になりうることを見落として1WA。

BはSにおける最初のpの出現位置からスタートする部分文字列をひっくり返すのが最適なので、候補がO(N)通りになって全探索できる。そもそもpが出現しないならひっくり返さなくてよい。

Cは最初、クエリごとに必要な頂点だけ取り出して圧縮した木を作ることを考えたが、あまりに面倒だったのでもうちょっと考察してみたらスマートに解けた。ある頂点のコインをひっくり返すときは、まずその頂点のボタンを押す必要がある。するとその子以下もすべてひっくり返ってしまうので、特にひっくり返したくない子があった場合はそれらのボタンも押す必要がある。逆にひっくり返したかった子のボタンを押す手間を省いたとも見なせる。

これをまとめると、クエリiの答えは、まずv\in S_iに対してvvの子の個数を求めて和を取り、そこからv\in S_iであってその親uu\in S_iを満たすようなvごとに2だけ引いたものとなる。

Dは、まずAに同じ値が二つ含まれていた場合、それらを取り除いてよいことがわかる。この操作をした後にAの要素が残るか残らないか見れば答えになると思い、提出。WA。もうちょっと真面目に考える。二人の和がそれぞれX,Yで、黒板に書かれた数の残りがx,yであるとする。この下でBobが勝つ場合、X+x\equiv Y+y\pmod MかつX+y\equiv Y+x\pmod Mである。式変形することで2(x-y)\equiv 0\pmod Mがわかるため、Mが偶数の時はM\leftarrow M/2として上で述べたことをチェックするのがよいと思った。またWA。

よく考えると、2(x-y)\equiv 0\pmod Mかつx-y\not\equiv 0\pmod Mなる(x,y)は偶数個使わないと和が一致してくれない。よって、最初に同じ値二つを削除するのを繰り返した後、残った個数が4の倍数で、かつ\bmod{M/2}で一致する値のペアを消していくと全部消えるというのが条件だと考えた。出したら通った。

Eは難しかった。Aの要素は最初全部区別しておいて、後から適当に割ることにする。列にどんどん挿入していくことを考える。Aの要素を昇順に見るのも降順に見るのもうまくいかなかったが、K/2で分割するとうまくいった。

列の両端にKが置かれているとみなして、新たに要素を配置できる隙間を管理しつつ、K/2未満の数を昇順に見る。a\lt K/2を見ている時点でa未満とK-a以上の要素がすべて配置済みとなるようにしておく。隙間を一か所選んでaを配置すると、その両隣には残ったK-a未満の要素が配置できないから、単に隙間を一つ減らすという効果になる。aを配置する前にK-a以上の要素を使い切るときは、隙間を一か所選んで挿入すると、その両隣は構成から必ずK-a以上となっているため、新たに隙間が二か所できる。

aを次の数に進めても、挿入できる位置は増えも減りもしない。こうやって隙間の数を簡単に管理できることが重要で、これを満たすためにK/2で分割して昇順と降順を分けている。あとは毎回の挿入位置を考えて組み合わせ計算するだけ。ところが2REしてしまった。combinationのライブラリは引数に符号なし整数を取るように作ったので、隙間の数がうっかり負になったとき、バカデカい値を計算しようとしてしまう。

1時間残してFへ。得意そうな見た目をしていたが、結局解けなかった。モンゴメリ乗算にはたどり着いたものの、リダクションの最後、if文による調整の部分が書けない。結果は5完5ペナで13位。ペナルティが多すぎる。Eは冷静になると隙間の数を答えに掛けながらインクリメント・デクリメントするだけでよく、わざわざライブラリを持ち出す必要がなかった。

コードゴルフ。AはRakuが間に合う。ずらして隣接項の差を取るのではなく全部の項からA_1を引くと高速になったし、[gcd]というreduce用メタ演算子の性質が効いて縮んだ。

もともとgcd演算子は正の数を返すようなので、これが1であるか判定するだけでよいと思っていた。$a gcd $b gcd $cという式が[gcd] $a,$b,$cと書けることを利用して全体の\gcdを求め、判定。ところが[gcd] $aと1要素しかない場合、メタ演算子の仕様上$aがそのまま返ってきてしまう。$aがちょうど-1だった場合にはうまく判定できないのだ。全部の項からA_1を引く方法だと必ず2要素以上になるので、正しく正の数が返ってくる。

BはPerl。ひっくり返す部分文字列が先頭のpの後に何文字続いているかを全探索し、正規表現で検出した。最も先頭の出現にマッチするので正しく動く。最初はわざわざpのインデックスを求めてsubstrで切り出していたが、この方法でかなり短くなった。以降は手付かず。

午前2時にMHC R1が終了した。提出したA1A2B1B2は全部通って76位、スコアが十分あるので当然通過。Cは座標の範囲が[0,a)\times[0,a)に制限されていると格子点からなる凸包にはO(a^{2/3})点しか乗らないらしい。言われてみれば昔聞いたことがあるかもしれないが、すっかり忘れていた。それでもV=35000頂点のdijkstraを解くことになる。これはpriority_queueを使わない方法でO(V^2)が達成できるので、確かに間に合いそう。

朝まで日記を書いていたが、急激に眠くなったので布団に移動。午前7時就寝。