08/15(月)

正午起床。もう30分くらい眠るつもりだったがTLを見ているうちに残念ながらそのような余裕はなくなってしまった。食事し、午後1時からMulti-Universities Camp 9回目。

"蔚来杯"2022牛客暑期多校训练营9_ACM/NOIP/NOI/CCPC/ICPC算法编程基础集训_牛客竞赛OJ

チームでAKEBGFCIDの9完、3位。自分はEFCを解いた。

Eはちょっとした構築。次にGがかなり解かれていたので読み、わからなかったのでHELPを投げた。少し相談して文字列の回文列挙をする問題になったが、ローリングハッシュが必要そうで、フルスクラッチする自信がなかったので実装をチームメイトに押し付けた。

Fは $n\times m$ 行列が与えられ、連続な部分行列について要素の $\gcd$ を考えたとき、その総和を求める問題。ただし元の行列の要素には $1\dots nm$ が一つずつ現れる。 $O(n^2 m)$ がギリギリ通りそうな制約に見えたが、よく考えると $\gcd$ を求めるのに $\log$ がついて厳しそう。より高速な方法を考えた。 $1\le g\le nm$ について、 $g$ で割り切れるような要素のみからなる部分行列を数え上げられればよい。このとき見るべきマスの総数が調和級数で $O(nm\log nm)$ になる。

見るべきマスを左上から順にソートして、各マスについてそこを右下とするような部分行列を数える。まず左に連続する $g$ で割り切れる要素の数が求まり、これを $L_{i,j}$ とすると、求める部分行列の数は $\sum_{k\le i}\min_{k\le i'\le i}L_{i',j}$ となる。すると列ごとにstackで管理するような形で差分更新ができて解ける。ソート以外は見るべきマスの総数に対して線形になって、 $\gcd$ も使わないので $O(n^2 m)$ よりは高速。出したらWAで何事かと思ったが、なんと $n$ と $m$ を取り違えていた部分があった。

Cは重み付きの単純グラフに関する問題。ただしこの重みは、辺 $e$ について順方向に通れば $+P_e$ 、逆方向に通れば $-P_e$ となる。この $P$ は3次元だが面倒なだけであまり関係ない。すべてのループについて重みの和がちょうど $\vec 0$ になるはずという状況下で、 $P_e$ が一つだけ間違っている場合、間違っているものとしてあり得る $e$ を列挙せよというもの。

サイクル基底を考えると、dfs木を取って後退辺を1本だけ含むようなループをチェックすればよい。最初から矛盾がないなら、逆にループに含まれる重みを変更すると矛盾してしまうので、ループに含まれない辺が答えとなる。矛盾しているループがあるならそれらのループにすべて共通する辺が答え。どちらも適切な後退辺を選び、端点に $\pm 1$ した後木上のimos法を行うことで判定できる。矛盾しているループが一つのみなら、それを作った後退辺も答えに含めることに注意。

Dは $n\times m$ の盤面を、ちょうど $nm/2$ 回曲がるような縦横のみの折れ線で一筆書きせよという構築問題。ただし $n,m$ は偶数。片方が4の倍数である場合の構築を自分が考え、それをチームメイトが拡張して両方4の倍数でない場合にも対応させた。このあたりで自分が抜ける時間になったので実装を託したが、その後気合いで200行くらい実装して無事通ったらしい。

午後4時半からインターン先定例会。先週は結局帰省しなかったものの、稼働してもいない。よって報告すべき進捗がない。紙幅を埋めるため、または単純に成果を誇るという気持ちで、AtCoderで冠が付いたという話をした。少し反応があって満足。勉強会は……よくわからない。今週の内容もまたあまり興味を持てなかった。感想すら言えなかったのは集中していなかったということで、興味を持てないからと他のことに意識を向けているのはダメだろう。気を付けたい。

先週の週記は土曜日のCF以降と校閲を残すのみで、ここ最近では最も余裕のある月曜日。TLを見たりYouTubeを見たりと盛大に集中を切らしながら、何とか日付が変わる前に読み返しまで済ませた状態の週記を投稿できた。

腹が減ったのでコンビニに行く。部屋の外に出るのは先週火曜日以来らしい。最寄りの店舗は午前0時で閉まっていたので、原付を飛ばして普段行かない方面に向かい、無事開いているコンビニを見つけて食欲の赴くままにパンやおにぎりを買ってきた。

最前線飛ばせ僕たちは
白みだした星空　胸を鳴らしている
眠らないよう上がるミュージックと
ぬるくなった水だけ持っていく
無駄なものは何もないさ　前を向け
その方がきっと笑えるさって pic.twitter.com/B1WPBbqmMh
— こたつがめ (@kotatsugame_t) 2022年8月15日

深夜なのでほとんど車がいないとはいえ、それを補って余りあるほど、あまり知らない道というのは非常に怖い。本当はゆっくり周囲を確認しながら走りたいのに、原付のスピードではままならないのだ。今日使ったコンビニは交差点のすぐそばにあって、発見したときはスピードを落としていた状態だったし、大きな駐車場が併設されていたため入りやすくて助かった。

少しTCO Finalsの書類作成を進め、疑問点をメールした後、朝までAHC013に取り組んでいた。この日記が公開される頃にはコンテストは終了しているから、少しばかり書き記しておこう。

RECRUIT Nihonbashi Half Marathon 2022 Summer（AHC013） - AtCoder

できるだけ大きなクラスタを作りたい気持ちになるので、ある一種類のコンピュータに注目して、それを頑張って繋げることにした。まだ繋げていない二つのコンピュータを全探索し、それを繋げるための手数を計算する。これは、最初の実装では直線移動で $X$ 座標または $Y$ 座標を揃え、後から4回まで移動するBFSに書き換えた。4回という制限は探索時間の制約によるものである。

その後ケーブルを張るマスを見て、邪魔なコンピュータがあれば1マスどかしてみる。これで接続できた操作のうち、移動回数が最小のものを採用する。実際に繋げるのは最後で、今度は接続できるペアのうちスコアの増分が最も大きいものを優先して繋いでいくことにした。ケーブルのためのマスはマークしておいて、以降に採用した操作で邪魔されないようにする。

ところがまあ全然ダメ。クラスタのサイズを思うように大きくできなかった。代わりに操作回数も余っているので、注目するコンピュータを変えて何度もやってみることにした。まだ操作していないコンピュータの種類を全探索し、それぞれ新たに上のアルゴリズムを走らせてみて、最もスコアが大きくなったものを採用するというのを $K$ 回繰り返した。他のコンピュータを接続しているケーブルのマスは、BFSにおける移動の時だけは通過することができる。

これで93699点、1965ms。BFSの移動回数を5回にするとTLEが怖いので、このくらいが限界。10万点に届かなかったことはそれなりにショックだった。

実装中、先ほどのメールに返信が来たので、書類作成を少し進めたり詰まったところをメールしたりというやり取りを数回行った。

gmailで英文メール書くと冠詞死ぬほど修正されて「バカな俺を──それでも愛そう…」みたいな気持ちになる
— こたつがめ (@kotatsugame_t) 2022年8月15日

午前9時半に布団に入り、しばらくハーメルンを読んで午前11時就寝。

08/16(火)

午後6時半起床。ぼんやりTLを眺めていたら、周央サンゴさんによる志摩スペイン村の案件動画がプレミア公開されるのを知り、午後7時からはそれを見ていた。

実写！？と思っていたら貸し切りですごい。声も別録りではなさそう。バーチャルとは何だったのかという気持ちにもなるが、僕はこういうの大好きなタイプなので問題なし。

志摩スペイン村様から案件をもらって、行ったよ(勝利確定BGM)(勝利確定BGM)

ガチで行ってるから実写動画だよ😮
編集がテレビみたいだよ！

近鉄、最高！
見て！

#PR

【#志摩スペイン村】来て！【周央サンゴ】 https://t.co/Ncwuh8ZbHg pic.twitter.com/9hHfviTG64
— 🧭周央サンゴ💞🦩 (@Suo_Sango) 2022年8月16日

見ている途中にスマホに通知が来て、何かと思ったら午後7時半からミーティングがあるらしかった。一応任意参加と書いてあるが、せっかく起きているのだしと出席を決定。起き上がってPCの前に座り、1時間ほど話し合いを聞いていた。少しモチベが出たのでさらに1時間ほどインターン関連のコーディングを進めたが、先ほどのミーティングの内容を鑑みて今やるべきことが明確になっていないということに気づき、急遽明日1on1をお願いすることにした。

しばらくハーメルンを読み、午後11時半からCF #814 div.1。

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

Aから難しい。操作のコストをばらすことを考えると、操作の幅は $2$ 以下に限定してよいとわかる。この時操作回数がそのままコストとなる。さらに、左端から順に操作して $0$ に揃えていくことにする。左端が同じ区間を使って2回以上操作することはないから、操作の列は「幅 $2$ の操作を一つずつずらしながら何度か行い、最後の要素が非ゼロなら幅 $1$ の操作で $0$ にする」ものいくつかに分割できる。特に、幅 $2$ の操作によって最後の要素は全体のXORに等しくなる。この時点で $O(n^2)$ のdpが書け、通った。

さて、遷移コストをよく見ると、基本的には分割後の幅と一致し、全体のXORがゼロの場合のみ $1$ 減っていることがわかる。あらかじめ答えに $n$ 足しておくと、この $1$ 減らす回数を最大化すればよいから、数列からdisjointな区間であってXORがゼロのものをできるだけたくさん取り出す問題になる。これは累積XORでZero-Sum Rangesっぽく解ける。ある位置以前から取り出した個数としてはこれまでの $\max$ を見ないとダメなのを忘れており、1WA。

Bも難しい。まず、連続する二つのフィボナッチ数を両方使わないようにしてある数をフィボナッチ数の和で表すためには、大きい値から貪欲に使っていけばよいということを確かめた。このような事実あったよなと思いながら計算していたが、ゼッケンドルフの定理というらしい。何回か見覚えがあって、フィボナッチ数の和と言ったら貪欲、みたいな繋がりだけ覚えていた。あとはフィボナッチ数列を降順に見て貪欲に当てはめていく。適当にやったらサンプルで落ちたものの、その時最大の値に当てはめるようにしたら通った。あまり自信はなかった。

Cは $d=\gcd(n,k)$ のみが問題で、逆に $d\mid n$ なる $d$ を全探索できる。長さ $d$ の配列について値の書き換え・全体MAXの取得を高速に処理したいので、1点更新区間MAXのセグメント木を使った。2000ms弱。MAXを取得するとき、最初はpriority_queueを使っていちいち値がvalidか確かめるコードを書いていたが、MLEしてしまったため慌ててこちらに書き換えた。

この時点で20位ちょっととかなり良い位置にいたが、崖の先のDが解けなかった。Cartesian Treeを見て各位置に当てはめられる値の区間を求めるのはよいとして、その後どうすればいいのかわからない。左に寄せた場合と右に寄せた場合を考えてマージする方針が思いついたものの、左から貪欲する場合と右から貪欲する場合で区間の並べ方が異なってしまうためうまくいかなかった。最後にHallの結婚定理を考え、端を含む区間だけチェックしたら十分じゃないかと勘で提出した。これは当然のように落ちてしまった。

システスは全部通って33位、2943→2954(+11)。この辺りで安定しているのは正直かなり偉い。また致命的に失敗して2900台から落ちてしまう前にラッキーパンチが打てればよいのだが、なかなかうまくいかないものだ。Cは素数 $p$ について $d=n/p$ となる場合のみチェックすればよかったらしい。 $O\left(q\sum_{d\mid n}\log d\right)$ が通るものと信じて、そこから先を全く考えなかった。

AHC013のシステスが終わっていた。実行時間の欄に2984msと書かれていてびっくりしたが、一応ギリギリ全ケースAC判定が出ている。順位は358位と少し落ちたようだ。パフォーマンス1302、レートは1910→1911(+1)。まあそんなものかという感想。そういえばコンテスト終了後のTLで感想戦を少し眺めていたのだった。サイズ100のクラスタを一つどころか二つ作れるケースもあったらしくてかなり驚き。

ほかのコンピュータに埋もれているものをちゃんと掘り起こしていないのが問題だろうか。seed 0のケースがまさに密だったので、そういうことをするべきだとわかってはいたものの、実装する気力がなかった。また気付いたこととして、すでに繋ぐケーブルを決定したコンピュータもそのケーブルに沿って動かせるというのを見落としていた。一度繋ぐと決めたものは二度と動かしていなかったのだ。

ハーメルンに戻り、最後の数話を読んで1作読了。「私は誰でしょう？」。

syosetu.org

非常に面白かった。タイトルやあらすじでは伏せられているが、主人公がギルデロイ・ロックハートであることはすぐ明らかになる。このキャラクターは原作において、死喰い人陣営でもないし敵でもないはずなのに余計なことばかりしてハリーたちの邪魔をするという、とんでもないストレス要因で、数多の二次創作でもいつも厄介者扱いされている。例えば僕が大好きなハリポタ二次創作「Game of Vampire」では、2年次の闇の魔術に対する防衛術の教授はアリス・マーガトロイドが担当し、ロックハートはそもそも作中に登場すらしていなかった。

この作品は、そんなキャラを再構成するというかなり変わった趣向。扱うキャラがキャラなので正直敬遠していたのだが、読み始めてみるとこれがかなり面白く、2年次終了時点の14話という短い話数でまとまってしまっているのが残念になるくらいだった。原作のようなあくどいことをすることもなく、誠実で、紳士的で、万能。原作と同じシーンをなぞりつつ、取る行動はどれもハリーたちを教授として教え導くようなものになっていて、気持ちよく読めた。

C++には以下のような罠がある。まだ眠る気にならなかったので、しばらくこれについてgccの実装を調べていた。

queueがデフォルトで512要素分のメモリを確保することを考えるとさすがにまずい。
週記（2022/07/25-2022/07/31） - kotatsugameの日記

queueはdequeによって実装されている。dequeのほうに問題があるようだ。以下のヘッダファイルがdequeを実装している部分である。2時間ほど格闘して何とか必要な部分が読み解けた。

github.com

まず、C++におけるdequeの実装はリングバッファではない。詳しい事情は忘れたが、イテレータが何らかの要件を満たすためだったはず。ではどうしているのかというと、要素をブロックに分け、ブロックの列を持っている。このことをすっかり忘れていたせいで読む苦労がかなり増してしまった。思い出して拍子抜け。

ただ、ブロックに分けた後の詳しい実装を知らなかったので、そこを知れたのはよかった。ブロックは型Tの要素512/sizeof(T)個、つまり512バイトの列である。この列は型TへのポインタT*という型を持ち、さらにdequeはブロックの列を持つのだからT**を管理している。まあここは今の本題ではない。

さて、dequeをデフォルトで構築した際の挙動を知りたい。このとき親クラス_Deque_baseのデフォルトコンストラクタが呼び出され、そこでは_M_initialize_map(0)が実行されていた。この0というのは当然最初の要素数だ。_M_initialize_map(n)では、nを1ブロック当たりの要素数で割って切り捨てた値に1足した分のブロックを生成する。なぜ切り上げではないのかというと、endを表現するためだろう。

列の終わりがブロックの終わりとちょうど一致した場合、endはそのブロックの末尾を指しそうなものだが、通常それは次のブロックの先頭と同じ意味であり、かつブロックが空間的に隣接しているとは限らないためメモリ上の位置としては一致しない。同じ位置を表現するイテレータが2種類あってはまずいため、ブロックの末尾へのイテレータは徹底的に避けられている。よって次のブロックの先頭を指す必要が生じるため、余計に一つブロックを作る必要があったということ。

これが要素数0の場合にも効いてきて、空のdequeであっても1ブロック生成されてしまい、先ほど述べたように512バイト分のメモリを消費する。上で引用したように512要素分のメモリを確保すると思い込んでいたのは間違いだったが、ただし512バイトであってもint型に直せば128要素分だから、大量にdequeを作るとまずいのは変わらない。

思ったより時間がかかって、睡眠時間がかなり削れてしまった。明日は朝からSRMがある。午前6時過ぎ就寝。

08/17(水)

午前9時半起床。SRMなんて寝てたほうがマシ説はあるが、ここは敢えて強い意志で参加……ということで気合いで布団から這い出て、午前10時からSRM835。

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

Easyは列が2本あるのはフェイクで1本ずつ揃えられる。どの要素がどの位置にいて欲しいか決めて辺だと思うと、ループがいくつか作れる。このループに沿ってもう一方の列の適当な位置と交換し続けることで、ループの長さ $+1$ 手で揃えることができるため、全体では $N$ にループの個数を足した回数の操作が必要。ところが長さ $1$ のループは無視してよいため、ループの個数は高々 $N/2$ となる。片方の列が $3N/2$ 手で揃えられたため、両方の列に対して行って終わり。

Medは周期 $P$ を小さいほうから全探索。同じ文字だとわかる箇所をグループに分けると、文字数を $N$ としてサイズ $\lfloor N/P\rfloor$ のグループとサイズ $\lceil N/P\rceil$ のグループがそれぞれいくつかずつできるため、dpで割り当てを決めて復元。高速化というよりは実装の短さを求め、このdpはbitsetで行った。

Hardは間に合わず。普通に考えると状態は「重い可能性のあるもの」「軽い可能性のあるもの」「どちらかわからないもの」「本物」がそれぞれいくつあるかという組で表現できる。これを丁寧に確認すると、実は前半分が0の場合と3番目が0の場合しかないことがわかるため、それぞれメモ化再帰できる。まず前半分が0の場合、これは $O(N)$ 通りしかないから、毎回左右の皿にどちらかわからないものをいくつ乗せるか全探索できる。3番目が0の場合にどうすればいいのかわからず、時間に追われて適当に書いて提出したものの、コンテスト終了直後にダメなケースを見つけて終わり。

チャレンジフェーズは何もせず。なぜか自分のHardも落とされなかった。システスは阿鼻叫喚で、自分のHardが落ちるどころかそもそもHardのAC数が1だったほか、EasyもMedも大量に落ちており、結果的にそれらを両方通しただけで6位まで浮上できた。2934→2977(+43)でhighest。いよいよTargetが見えてきて震える。

しばらく日記を書いて午後1時からMulti-Universities Camp。当初は予定されていなかったコンテストで、いつの間にか生えていた。加赛（プレーオフ）と書いてあるが5回目のお誕生日コンテストの詫びコンテストという認識でよいだろうか。

お誕生日コンテスト。とにかく酷いセットだった。このCampは本来有料だと以前に言ったが、お金を取っておいてこのセットを出すのはさすがにヤバい。
週記（2022/08/01-2022/08/07） - kotatsugameの日記

"蔚来杯"2022牛客暑期多校训练营（加赛）_ACM/NOIP/NOI/CCPC/ICPC算法编程基础集训_牛客竞赛OJ

普段と違う曜日なのでチームメイトはあまり参加できなさそうな雰囲気を出していたものの、蓋を開けてみればほぼずっと3人揃っていた。偉い。ただし結果は全く偉くなく、チームでHMLEJKの6完。自分はHMEを解いたが、全部簡単枠。その後3時間ほどCと格闘して解けず、残り時間はGを見て解けず。ダメダメ。

一応Eについて言及しておこう。 $n$ 人がゲームを行う。人 $1$ から順番にゲームを抜けるかパスするかを選んで進んでいく。人 $i$ が $j$ 人目にゲームから抜けたとき、その人はスコア $a_{i,j}\gt 0$ が得られる。最後の人まで回ったらまた先頭に戻って、一周全員がパスする（元の問題ではラウンドという概念が使われていたが、こう書いても結論は変わらない）か全員が抜けたら終了。このとき最後から $p\le n$ 番目に抜けた人がいればその人のスコアは負になる。それぞれの人が最後に得られるスコアを最大化しようとした場合、いったいどうなるかという問題。

まず、残り $p$ 人になった段階で全員がパスをする。残り $p$ 人を下回った段階で、パスするよりどのタイミングであっても抜けたほうが明確に得になるからだ。同様のことが残り $2p$ 人、 $3p$ 人、……と続いて、結局ゲームから抜けるのは $n\bmod p$ 人だけだとわかる。

特に $n\bmod p$ 人目に抜けるチャンスが来た人は必ず抜ける。このことは、例えばパスが何回も行われた場合を考えるとわかりやすい。自分がパスしたらゲームが終了するとなると絶対にパスをしないので、そこから逆に考えていくと、常に「自分がパスしたら次の人が抜けてしまう」ことが言える。この「次の人」の存在はゲームから抜けられない人が $n-(n\bmod p)\ge 1$ 人いることから従う。

なんと同様のことが $(n\bmod p)-1,(n\bmod p)-2,\dots,1$ 人目のすべてについて言える。考え方も同様で、先ほどと同じく $n-(n\bmod p)\ge 1$ から「自分がパスしたら自分の次の人から連続で抜けて行ってしまう」ことが「自分が抜けるタイミングが失われる」のと等しくなり、パスするだけ損だとわかる。

TLでしばらく感想戦を眺めた後、午後7時から1on1。昨日お願いしていたもので、2時間ほどミーティングしていた。内容はともかくとして、今日の自分の態度はかなりひどかった。眠すぎて一瞬意識を飛ばしたタイミングが数回あったのだ。弛んでいる。眠気に耐えられないのなら睡眠時間を確保するよう努力しなければならない。

疲れ果てているのに眠りたくなく、しばらくYouTubeを眺めていた。その後日記を少し書き進めてみたものの、いよいよ眠気に耐えられなくなってすぐ切り上げた。午前0時半就寝。

08/18(木)

午前6時起床。夢を見た。

夢：モンハンとポケモンが合体したアニメ。自分のモンスターと野良モンスターが戦っている間に後ろから近づき、強力な溜め切りを当て、できたキズにハイパーボールを触れさせるとゲット成功。ボールを強く握りしめて頷き、今捕まえたモンスターを出して頭に飛び乗り悠々と去っていったのが格好良かった
— こたつがめ (@kotatsugame_t) 2022年8月17日

ハーメルンの更新をチェックして、流れで1作読み始め、そのまま読了。「Vtuber界を駆け上がりたい」。

syosetu.org

「輝きたくて」の作者の別作品で、そちらの世界設定を引き継いでいるようだ。登場人物も一部共通している。こういうの、スター・システムと言うんだったか。図らずも後日譚のようなものに触れることになって思いがけない驚きと嬉しさがあった。逆に、もっぱらそのような見方で読んでしまい、独立した作品とは思わなかった。

それを取り除いて考えると、内容は正直微妙。主人公の最初の印象がマイナスで、そこから話が進むにつれ改善しては行ったものの、プラスに転じる前に完結してしまった。完結というより作者が放棄したという印象だが、それでも最終話が投稿され内容に決着がついているのはすごい。そこで明かされた事実により主人公に対するモヤモヤが解消されたので、読後感は良かった。

もう1作手を出してしばらく読み進めた後、正午前に寝落ちして二度寝に入った。次は午後6時起床。

布団に横たわったままハーメルンを読み続けていたが、今日のCFが普段より1時間早いことを知り、うっかり出遅れないよう起きておくことにした。午後9時頃に布団を脱出。

昨日のSRMのHardを通した。コンテスト中に何が最適かわからなくなってしまった部分だが、実はこれも全探索できるらしい。重い・軽いそれぞれ何個左右の皿に乗せるか、で4重ループ。ただでさえ定数倍が良いうえ、そもそも重い・軽いは最大で $N/2$ 個しか存在しないため、計算回数は見た目より大幅に少ない。

ところで、Easyで大量に落ちていたのは出題側のミスかもしれないという話が出ていた。最大で長さ6000程度のvectorが答えになるが、ジャッジがそのような長さのvectorに対応していないのではとのこと。実際、ACコードに適当な操作を付け加えると落ちてしまったらしく、暗雲が漂う。

なんか答えの vector が最大で長さ 6000 くらいになるけど TopCoder のシステムが 5060 くらいまでしか対応してなくないですか？（勘違いだったらごめん......）
— 和解 (@rsat__m) 2022年8月18日

食事してシャワーを浴び、午後10時半からCF #815 div.2。

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

Aは多くても2手で達成でき、0手の判定は自明だから、1手でできるかの判定が問題となる。一方の分母に掛けるのともう一方の分子に掛けるのは同じ意味なので、分子に掛けると固定してよく、式変形すれば掛ける数が整数になる条件が出る。つまり、 $ad$ と $bc$ の間に約数・倍数関係があればよい。この関係は、どちらかが $0$ の場合は必ず成立。

Bは難しかった。 $l$ と $r$ のどちらかを全探索する方針を考えたが上手くいかない。しばらく考えて、 $\max(a_1,\dots,a_{l-1},a_{r+1},\dots,a_n)$ と $\max(a_l,\dots,a_r)$ のどちらかは必ず $\max a$ に等しいということに気づく。もう片方が2番目の最大値になって、同様のことが $\min$ でも成り立てば明らかに最適だな、と考えて、実際に達成できることに気づいた。 $a$ の要素のうち大きいほうから二つ、小さいほうから二つに注目すると、それらをちょうど一つずつ含むような区間 $[l,r]$ が必ず取れるのだ。このことに気づいて、してやられたなと感じた。

Cは初手以外 $1$ を一つずつ $0$ にしていくことができる。初手を全探索。

Dも難しかった。インデックス $i$ の次に $j$ が来られる条件を考える。これは $a_i\oplus j\lt a_j\oplus i$ である。二つの数の大小関係がどのbitで決まるか固定すると、その桁だけ見たとき $(a_i,i)=(0,0),(0,1),(1,0),(1,1)$ から $(a_j,j)$ が一意に定まる。またそれより上のbitは $a_i\oplus i$ と $a_j\oplus j$ で一致するから、これらの情報をキーにして値のセット・取得を行うことでdpができる。情報が各 $i$ に対し決め打つbitで30種類、またセット・取得に $O(\log n)$ かかる。

解けたと信じて投げたらD1は500msだったがD2でTLEした。冷静になると $n\le 3\times 10^5$ で $\log$ と定数倍 $30$ が付くのはヤバい。しばらく考えてもどうにもならなかったので、2¹⁹の位より上で $i$ や $j$ が必ず $0$ になることを利用し、絶対に利用されない・存在しないキーを見ないという定数倍高速化を入れて投げてみると、1950msでギリギリ通った。

Eは解けず、34位。Dはbinary trieで情報を持てばbitを決め打ちつつキーによる値へのアクセスができるので $\log$ が落ちるらしい。なぜ気づかなかったのか。ちなみに自分の解法は、システス後は1996msになっていた。

Eはなんと、種類数を減らす場合が必ず2手で達成可能のようだ。鍵アカウントのツイートを参考に詳しい証明を書く。まず一番左上のマスを覆う同じ値の正方形を用意し、種類数が足りなくなるギリギリまでサイズを大きくしていく。これで $k$ にできなかった場合、今作った正方形のサイズを $x$ とすると $x\lt n$ なので、 $(x+1,x+1)$ のマスを覆う先ほどと同じ値の正方形が用意できる。ここで種類数が $k$ になる可能性はあるが、それより小さくなることはない。

またサイズを大きくしていくが、今度は左上の方向に伸ばす。ここでもピッタリにできなかった場合を考えよう。サイズ $1$ のときは種類数が $k$ より大きく、サイズ $x+1$ まで伸ばし切ったときは $x$ の決め方から $k$ より小さくなる。さらに、サイズを $1$ 伸ばす度にたった2マスだけ新たに覆われることになるから、種類数の変化は毎回 $-0,-1,-2$ のどれかである。つまりどこかのタイミングで種類数が $k+1$ から $k-1$ に変化したことになる。

$k-1$ のときのサイズで操作する。もし今の二つの正方形が完全には被っていなかったら、片方の値を変えることで種類数 $k$ が達成される。後者の正方形が前者の正方形を覆ってしまった場合、前者の正方形で操作するのを止め、代わりに後者の正方形のうちどこか $1\times 1$ マスを別の値にすればよい。以上で2手での操作が構築できた。

つまり1手で達成できるか判定すれば十分。コンテスト中はここすら思いつかなかったのだが、正方形のサイズを決めた後、どこで操作すればどれだけ種類数を減らせるかを2次元imosで計算すると $O(n^3)$ で行える。

さらにハーメルンを読み進めて1作読了。「マエリベリー・ハーンと賢者の石」。

syosetu.org

非常に面白かった。クロスオーバーで、腹に一物抱えてホグワーツに入学したマエリベリー・ハーンが1年で才能をどんどん開花させつつ、賢者の石を巡る攻防に巻き込まれたりする話。原作の展開をなぞりつつ、それを一段上から観測する感じがワクワクして楽しい。そうやって原作の間に明確に力の差があるような描き方は好きだ。

1年次終了時点でひとまずまとまってはいるものの、その後も投稿される予定ではあるらしい。しかし3年以上も間が空くと厳しそうだな、と思って作者の別作品を調べると、「雛森「シロちゃんに『雛森ィィィィ！』と叫ばせたいだけの人生だった…」」が見つかった。実はこれも80話ほど読んでいて、本編が完結しおまけに入ったところで止まっている。そういう状態だから日記では言及していなかったのだ。ずっと活動を続けていらっしゃるのなら、気長に待てば本当にそのうち更新されそうだなと考えた。

syosetu.org

TCB50に出た。日曜日終了なのでここに感想を書く。

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

5問目まではよい。6問目はかなり難しかった。2番目のサンプルを手で試し、どうやら数回操作した後は周期2になるらしいと気づいた。一回の操作は $O(N^2\log N)$ でシミュレートできる。2回の操作で周期に入ると思ってコードを書いたが、正当性が示せておらず怖かったので、念のため $N$ 回は操作することにした。出してからやっぱり計算量がまずいかと思ったものの、最大でも1.5secで通った。この問題で理論値を取るためには12分以内に提出しなければならない。自分は10分半かかったので、かなり危なかった。

7問目は何も考えず $O(NA^2B^2)$ のdpを書いたら手元で3secちょっとかかってしまった。そのまま提出してしまうことも考えたが、少し睨みつけると遷移が区間加算だと分かり、計算量から $B$ を一つ落とすことができた。

8問目は、すべての $K$ に対する答えを計算しておいて、更新の度に差分更新することを考えた。書き上げて一度は提出しそうになったが、よく見ると $1$ と $2$ で交互に更新された場合まずいことに気づき、直前で踏みとどまった。冷静になると、 $10^5/K$ 回の計算で答えを直接求めることもできる。よって $K\ge 10^2$ の場合はそちらを使い、 $K\lt 10^2$ の場合は差分更新することにした。これだと更新の度に見るべきペアが高々 $2\times 10^2$ 個になるため、間に合う。

9問目は今度こそすべての $M$ に対して答えを計算しておく。適当に見積もると、 $M\ge 2\times 10^5$ の場合は $\sum A(A+1)/2$ が答えになるようだ。それ以外の $M$ については、 $kM\lt A\lt(k+1)M$ なる $A$ がどちらに寄せるべきなのかは閾値が式変形で出せるし、かかるコストも適当に累積和を取ったりして計算できる。見るべき $(M,k)$ の個数は調和級数になるので、十分少ない。

10問目も難しかった。今の $K$ がいくつで、操作は $i$ 回目、という状態を考えるとdpはできる。これまで $P=1\dots K$ では操作したことがないので、それらで操作して $K$ を小さくするか、あるいは $K+1\dots N$ のうちこれまでの $i$ 回で使用しなかったものを $P$ に選び $K$ を据え置くか。これは当然 $O(N^3)$ である。 $P=1\dots K$ で操作した場合の次の $K$ をあらかじめ求め、重複を取り除いて $K=1\dots 3000$ に対してどれくらいの遷移回数になるか計算してみると、 $2\times 10^6$ を超えていた。これではお話にならない。

しばらく考えていると、最初の1手で $K\lt N/2$ になることに気づいた。再度先ほどの同じものをまとめた場合の遷移回数を計算すると、今度は $K=1\dots 1499$ で $6\times 10^5$ 弱まで減ることが分かった。ここに $N=3000$ を掛けても間に合うのではないか。 $\bmod$ が変数なので、余りを取る操作を引き算で丁寧に実装し、手元で実行してみると1secを切った。提出すると2sec程度で通った。この問題も理論値ボーダー24分のところ22分半だったのでギリギリ。

久しぶりの理論値だった。時間は75分弱か。6問目をエスパーで通したのと10問目が非想定っぽいので少し釈然としない。終わった後しばらくこれらについて考えていた。

6問目は2回目以降が周期2になるらしい。これを示す。まず問題を、行列 $a$ を行ごとに降順ソートするのと列ごとに降順ソートするのを繰り返していると見なす。このもとで、2回操作を行うと任意の要素 $a_{i,j}$ について $a_{[1,i],[1,j]}\ge a_{i,j}$ が成り立つことが示せる。これより以降どの向きにソートしても変化しなくなるというわけ。

証明しよう。以下、 $a$ は2回操作した後の行列である。まず、 $a_{i,j}$ は1回目のソートによって $j$ 列目に動いた。つまりこのとき、同じ行の $[1,j]$ 列目の値は $a_{i,j}$ 以上だったことになる。まったく同様のことが $a_{[1,i),j}$ の各要素に対しても言えて、2回目のソートの結果 $a_{[1,i),j}\gt a_{i,j}$ なので、結局、1回目のソート後に $[1,j]$ 列目の値が $a_{i,j}$ 以上だった行は $i$ 個（以上）存在したのだ。これを列ごとに見ると、 $[1,j]$ 列目に $a_{i,j}$ 以上の要素が $i$ 個以上ずつ存在すると言えて、それらを列ごとに降順ソートするのだから当然 $a_{[1,i],[1,j]}\ge a_{i,j}$ となる、というわけ。

10問目は $P$ に何を選んだかが場合の数に関係ないのを見落としていて、さらに遷移の係数も掛け忘れていたため、奇跡的に答えが合っていたらしい。その係数を求める必要がないのなら、 $K$ を $1\dots K$ で割ったあまりとしてあり得る数を考えれば一瞬だった。実は $0\dots\lfloor(K-1)/2\rfloor$ になるので、これまた遷移が区間加算で書ける。

ゴミを出した後、昼前まで日記を書いていた。布団に移動して少しラノベを読み、午前11時半就寝。

08/19(金)

午後9時過ぎに目を覚まし、ちょうどyukicoder開始少し前だったので布団から出て参加した。

yukicoder contest 357 - yukicoder

Aはよい。Bはstrictlyである必要がないため色数をできるだけ揃える発想が出て、必ず達成可能だとわかる。先頭から3人ごとにRGBを一つずつ使えばよいのだ。矛盾しない範囲で適当に証言を増やして実装した。Cは枕の横の長さを決めると縦の長さが区間になって、 $\sum$ を閉じた形にすれば置き方を一気に求められる。Dは石の数が無限であるような山が少ないほうから考えてみると規則性が見える。

Eのsolvedが少なかったのでFに進んだ。Fは $A$ を昇順ソートすれば $\sum_{i\lt j}-(A_j\bmod A_i)$ を求める問題になって、BITを使うと $O\left(\frac{\max A}{A_i}\log\max A\right)$ で計算できる。今 $A$ はdistinctなので、調和級数になる。Gは根付き木にして、各部分木の根が「孤立している」「長さ $2$ 以上のパスの端点である」「パスの内部の点である」の3状態を持つ木dpを行えばよい。

Eに戻ってきた。実験すると、最初の順列から操作 $1$ と操作 $2$ を交互に繰り返し、初めの状態に戻ってくるまでにかかる操作回数が答えになるらしい。特にその最後の操作は操作 $2$ になる。操作 $1$ と操作 $2$ を組にすると順列の変化が置換として書けて、グラフだと思ってループの長さを見れば、各位置について何回の操作で元に戻ってくるかがわかる。これの最小公倍数が答え。素因数分解して求めた。

Hは解けず、7完。

Eの解説で集合 $S$ の要素が相異なるというのがよくわからず、日記を書いているときにTLで質問した。 $xyxyx\dots$ や $yxyxy\dots$ という列が、長さ $2m$ 未満で ${\rm id}$ にならないことを示したい。長さが偶数の場合は $m$ の取り方から従う。奇数の場合について、例えば $xyx={\rm id}$ となった場合、両辺に左右から $x$ を掛けることで $y={\rm id}$ となってしまうため矛盾するようだ。

そういうのは両側からxをかけるとy=idになってダメになる
— heno (@heno_code) 2022年8月21日

しばらくハーメルンの更新を読んでから、R言語について少し調べていた。指導教員の先生からの頼まれごと。よく知らない言語のよく知らない型を弄るので大変だった。これには3時間くらいかかっていたらしい。その後TCO Finalsの書類作成を進めて朝方に。

日記を書いて布団に入った。うっかりラノベを少し読み進めてしまい、就寝は午前10時だった。

08/20(土)

午後0時半起床。ありえないくらい眠い。昨日眠気が来ないのをいいことに好き勝手夜更かししたのが馬鹿だった。後悔しても睡眠時間は戻ってこないし、実際起床に成功しているのだから今後も同じことをやってしまうのだろう。人間は愚か。

午後1時からMulti-Universities Camp 10回目、最終回。

"蔚来杯"2022牛客暑期多校训练营10_ACM/NOIP/NOI/CCPC/ICPC算法编程基础集训_牛客竞赛OJ

チームでIHKGDEFJの8完、5位。自分はGFJを解いた。

Gは $n\le 4\times 10^4$ 山のNimで、ただし山の石の数が常に広義単調増加になっていなければならないという制約を足したゲームを考える。一つの山に対する石の数が最大 $m\le 10^{12}$ だとしたとき、後手が勝つ盤面を数え上げよという問題。ほとんど蟻本278pに載っていたゲームと同じであることに気づき、とりあえず勝敗判定ができるようになった。

山の石の数を $0\le a_1\le\dots\le a_n\le m$ とおき、 $a_1-0,a_2-a_1,\dots,m-a_n$ の $n+1$ 個の非負整数に総和が $m$ になるように値を割り当てる問題だと捉える。このうち固定された $\lceil n/2\rceil$ 個の値のXORが $0$ になることが後手勝利の条件。 $k=39\dots 0$ について、 $2^k$ がいくつ余っているかでdpすると、何個使いどこに割り当てるかというのが遷移になる。使ってもなお $n+1$ 個以上余っている場合はもう取り返しがつかないため、無視することができ、dp配列はそれほど長くならない。

$40$ 回の遷移を行うが、それらはまったく同じ多項式を畳み込んでいる。よってこの多項式さえ求められればよい。つまり、 $0\le i\le n+1$ について、 $2^k$ を $i$ 個使ううち偶数個を固定された $\lceil n/2\rceil$ 個に割り当てるような方法を数え上げたい。深く考えずに $O(n^2)$ を書き、ちょっと定数倍高速化したら通った。

Fが100チーム以上に通されているのに全然わからず困っていた。どうしても考察が先に進まず、気分転換しようと問題文を改めて読み直したら、誤読に気づいた。慌ててPCを借りて通した。

Jは長さ $N$ の数列 $A$ と $B$ が与えられて、 $(i,j)$ を選んで $A_i$ と $A_j$ をswapする操作をすべての $1\le i\lt j\le N$ で行った後 $A=B$ となるようにできるか、判定＋構築をする問題。操作の順番は任意。 $A=1\dots N$ 、 $B$ を順列だと思うと、 $B$ の転倒数と $N(N-1)/2$ の偶奇が等しいことが必要条件。実は十分条件でもあるのではないかと考え、実際に構成した。

$A_i\ne B_i$ なる $i$ が存在する場合、この $i$ を含むような操作を全部行った上で $A_i=B_i$ となるようにできるため、それを行う。これで $N\leftarrow N-1$ とできる。残っている $N$ 個の $i$ すべてで $A_i=B_i$ の場合、現在の転倒数とここから $N(N-1)/2$ 回操作したときの転倒数の偶奇が等しいことがわかる。つまり $N(N-1)/2\equiv 0\pmod 2$ より $N\equiv 0,1\pmod 4$ 。

チームメイトが $N=4$ の場合の操作列を一つ構築してくれた。 $(1,2),(3,4),(1,4),(2,3),(1,3),(2,4)$ 。これを適切に拡張すれば $N\leftarrow N-4$ とできるのではないかと考えると、実際に可能だった。

$i=1,2,3,4$ の操作を消費するとして、残り $N-4$ 個の $u$ について $(i,u)$ を全部使い切りたい。 $N-4\ge 2$ のとき、 $u,v$ を取って $(1,u),(2,v),(1,v),(2,u),(3,u),(4,v),(3,v),(4,u)$ とすることで、 $[1,2,3,4]\rightarrow[2,1,4,3]$ としつつ $(i,u),(i,v)$ を使いきれる。今 $N-4\equiv 0,1\pmod 4$ なので、これを偶数回繰り返すことで残りの $u$ が0個または1個になる。0個の場合は先ほど紹介した6回の操作でOK。1個残った場合は、 $(1,2)$ の代わりに $(1,u),(1,2),(2,u)$ を、 $(3,4)$ も同様に展開することで、 $(i,u)$ を使い切りつつ6回の操作と同等のことができる。

以上を丁寧に実装してAC。最初に $B$ を順列にするとき、元の列に同じ要素が複数出現するなら、適切にswapすることで転倒数の偶奇を任意に定めることができるため、必ず揃えられるようだ。

これまで特に触れてこなかったが、Multi-Universities Campに参加するとチームに対してレートがつく。1000スタートでそこそこ順調に伸ばしていたものの、水曜日のプレーオフでついに減らしてしまったりとそううまくはいかず、最終的に10回のratedで2774を記録した。赤まであと26だったので残念。別の日本チームはわずか5回で赤に突入しており、あまりにも強い。

japan1000000007的比赛主页

実は午後3時頃に両親が来ていた。僕がコンテストに出ている間はありがたくも部屋の掃除などをしてもらっていた。コンテスト終了後すぐ外出。仙台駅まで出て、駅ナカの飲食店で食事した。今日は牛タンではなく、普通の定食。アルコールも頼んだものの、薄すぎてそれらしい味は全くしなかった。

食事 pic.twitter.com/IbFLpi8byW
— こたつがめ (@kotatsugame_t) 2022年8月20日

ヨドバシカメラやスーパーに寄って少し買い物をし、帰宅。午後9時からARC146に出た。僕の序盤の様子を見たいとのことで、コンテストが始まったタイミングではまだ両親が部屋にいた。

AtCoder Regular Contest 146 - AtCoder

Aはまず桁数が大きい数を使いたくて、タイブレークは辞書順で大きいほうを使うのでよさそう。つまり使う三つの数は確定する。このあたりでコーディングを始めたが、しかしそれを並べるのが思ったより難しいことに気づいた。 $3!$ 全探索するコードを書いて提出。無事ACしたのを見届けて両親は帰っていった。

Bも簡単。上のbitから貪欲に、そこを立てられるなら立てていく。ある数をインクリメントすることでbitを立てなければならなかった場合は、インクリメント回数が少ないものから順に使えばよい。より下のbitが全部 $0$ になるため、どれを選んでも以降に影響しないのだ。ここまで10分足らずで通し3位に浮上した。順位表を見ているだろう両親も喜んでくれるかな？と思いつつ、意気揚々とCに進んだ。

しかし以降110分間何も解けず、結果は2完178位。残り20分を切った段階で諦めてDに移り、こちらはすぐ見えたので書き始めたのだが、さすがに間に合わなかった。600点が解けない自分というのを認めたくなくて、ずっとしがみついていたのだった。

コンテスト終了後3分ほどでDが書きあがり提出するも、WA。これは軽微なミスで、追加15分くらいで今度こそACできた。この15分の間にTLを見たりしていた記憶があるので、字面よりは惜しかったはず。

数列のインデックスごとに条件となる $X$ または $Y$ を集め、それぞれ「（その値より）大」「（その値と）等しい」「（その値より）小」の3種類の状態を持つ。値を昇順にソートすると、この3種類が順番に現れることになる。初期状態はすべて「小」で、そこから値が $1$ であるような条件について「等しい」に切り替えるのがスタート。以降BFSのように連鎖的に状態を切り替えていく。

遷移は、同じ条件から得られた組で状態を揃えるのと、同じインデックスで値のソート後に一つ隣にあるものに状態を伝播するもの。伝播元は必ず「大」または「等しい」なので、値が小さい条件に状態を伝播する場合は常に「大」になる。また、「大」から値が $1$ だけ大きい条件に「等しい」として伝播する必要もある。後者を忘れていたというのが、コンテスト終了後に出したWAの原因だった。

最後にインデックスごとに条件の状態を見て、すべてを満たす中での最小値を取る。等しいものがあればそれ、そうではなく「大」があればその最大値に $+1$ したもの、残りは $1$ 。こうして取った値が $M$ を超えていた場合、答えは $-1$ になる。

Cは解説冒頭を数行読んでupsolveした。XORという文字列を見た瞬間桁ごとに考えて帰ってこられなかったが、個数を見るのが正解とはびっくり。またすべての要素に $+2^N$ することで $S$ が一次独立という条件になるようで、ここからはよりダイレクトに個数しか考えなくてよいことがわかる。パターンマッチングした人間を陥れる上手い問題だった。

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

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

Aはいかにも難しそうだったがサンプルを説明する画像がすべて。Meganに $(1,1)$ を通るようなルートを進んでもらって、Stanleyは $(1,1)$ のポータルから $(n,1)$ または $(1,m)$ に飛ぶのが最適っぽい。パッと思いつかなかったので、証明はせずに進んだ。 $n=1$ または $m=1$ のときは飛ばなくてよいので、そこを丁寧に処理するか、あるいはそれをしなくても $(n,m)=(1,1)$ だけ特別扱いすればよい。このケースがサンプルにあるのは優しさ。

Bは $kb\le s\le kb+n(k-1)$ が必要条件で、 $s-kb$ は $k-1$ ずつ貪欲に割り振ってよい。ただし $kb$ について、うっかり1要素に全部押し付けてしまうと $a\le 10^{18}$ を満たさなくなってしまう可能性があると考え、できるだけ均して割り振ることにして、そういうことができない $n=1$ の場合を特別扱いした。しかし今改めて確認すると $s\le 10^{18}$ だったので、このような面倒なことは考えなくてよかったらしい。

Cは $a_i\ne a_{i+1}$ であるような位置を考えればよい。答えにどれだけ寄与するかが $i$ ごとに計算できて、更新する度両隣について計算しなおす。Dは桁ごとに見る。 $0$ の位置を確定させた後、 $1$ はできるだけ後ろに押し付ければよい。制約で与えられた条件が矛盾しないことが保証されているため、あまり細かいことを考えなくて済んだ。Eは飛行機に乗る回数でループして、地上の移動は多始点dijkstra、飛行機による移動はCHT。直線の傾きが単調なので線形でできるはずだが、面倒だったのでうしさんの動的CHTを拝借し、1200msで通した。

Dynamic-Li-Chao-Tree | Luzhiled’s Library

Fは謎。 $x$ と $y$ をそれぞれ2手で求められる。 $x$ について書く。基本的な方針として、 $y$ に影響しないような図形を考えたい。これは $Y$ 軸方向に周期 $1$ を持つ、つまり $1$ だけずらしても形が変わらないような図形である。それでいてかつ、 $x$ を区別できると嬉しい。ここで、底辺 $m$ 、高さ $1$ の直角三角形を縦に大量に積み重ねることを考えた。直角が左下にあるとすれば、 $x$ が大きくなるにつれて共通部分の面積は小さくなるため、逆に面積から式変形で $x$ が求まる。

ただしこれでは、多角形に自己交差が生まれてしまう。よって左端に縦に長い長方形を作り、三角形たちをくっつけることにした。長方形の中に正方形が被ってしまうと困るが、最初に長方形だけで聞けば対処できる。以上で2手。出したら通った。

一時間弱で全完できて気分が良い。システスも全部通り2位だった。Aの解説にあった証明が結構面倒くさくて、やはり直感で突き進むことが求められていたのだなと思った。Fはジャッジを作るのが大変そう。途中、負号付き $0$ が正しく処理されていなかったとかでリジャッジが入っていた。

ARCのコードゴルフ。Aの現状の最短コードを読み、少し縮めて提出したところ、WAになった。すでにafter_contestが追加されていたようだ。コンテスト中は使う三つの数を辞書順で降順ソートしたら通ったらしく、参考にした最短コードもそれを実装している。正しい解法で短くできる気がせず諦めた。以降の問題は手付かず。

A に after_contest として以下のテストケースを追加しました
input
3
2 21 9
output
9221
— PCT (@PCTprobability) 2022年8月20日

しばらくYouTubeを眺めてから午前3時半に布団に入り、ラノベを読み始めた。

1冊読了。「ありふれた職業で世界最強」12巻。前の巻の内容をあまり覚えていなかったが、この巻はバトル・バトル・またバトルという感じだったので特に問題なし。しかし主人公は早々に別行動に入り、ヒロインたちだけが描かれていたので、それはちょっと物足りなかった。ただ、その分次の巻は主人公とラスボスが思う存分バトルしてくれそう。しかも最終巻らしい。実はこの巻が発売されたのは今年1月で、13巻の発売がすでに9月末と決定している。非常に楽しみである。

もう1冊手を出し、ほんの少し読み進めてから就寝。午前6時前だった。

08/21(日)

午後0時半に目覚ましで起きた。45分からyukicoderでNPCA 合宿コンテスト。

NPCA 合宿コンテスト - yukicoder

ペナルティがないので全問提出欄でコーディングした。10分足らずで全完、ACDEのFAで2位に100点差を付け優勝。感想は特になし。午後1時頃また寝た。

午後6時半に改めて起床。日記を書いて午後9時からABC265に出た。

AtCoder Beginner Contest 265 - AtCoder

Aを読んで意気揚々と言語にdcを選択、 $(N\bmod 3)\times X+\left\lfloor\frac N 3\right\rfloor\times Y$ を提出しWA。なぜWAなのかわからず、手元でサンプルを確かめてようやく気づいた。面倒だったのでC++で改めて実装した。BCはよい。

Dは $x$ を決めるごとに二分探索を3回して $y,z,w$ を決めるのが思い浮かんだが、なぜかこれが $O(N(\log N)^3)$ だと思い込んでいた。少し考え、 $i$ を降順に見てそこが $x$ 、 $y$ 、 $z$ になれるかをそれぞれ求めたものの、これも結局二分探索を3回している。

Eで少し詰まった。ワープを使った回数を考えればよい。 $O(N^3)$ のループの内側でその座標がvalidか調べるために $O(\log M)$ かけている。計算量が想定解より悪いと思って恐る恐る提出したが、100msもかからず通った。定数倍が良いからだろうか。

Fはかなり時間をかけた。最初 $d(p,r)+d(q,r)\le D$ だと思い込んで実装してしまった。これは斜め方向への区間加算になってimos法で解けたので、正しい問題も最初はそのようにして考えてみたが、なんと斜めが2種類も出てきてしまった。そもそも $O(ND^2)$ なうえ場合分けも大変そうであまりに嫌だったので、別の方針を考えた。

三角不等式より $d(p,q)\le d(p,r)+d(q,r)$ であるが、このうち特に等号が成り立つ $r$ のみをまず数える。等号が成り立たない場合というのは $r_i\lt p_i,q_i$ または $r_i\gt p_i,q_i$ となる場合だから、このような $i$ が存在するケースについては、 $r_i=p_i$ または $r_i=q_i$ として数えておいて、後から $r_i$ を遠ざける場合の数を試せばよい。 $p_i=q_i$ の場合はまた特殊なので、このような $i$ はカウントしておく。

まず、 $r_i=p_i$ または $r_i=q_i$ となる $i$ の個数と、 $d(p,r)$ を持ってdp。遷移が単なる横方向の区間加算になるから $O(N^2D)$ で解ける。次に、 $d(q,r)=d(p,q)-d(p,r)$ を求め、余った $\min(D-d(p,r),D-d(q,r))$ を $r_i$ を遠ざけるために使う。ここで $p_i=q_i$ なる $i$ をどれだけ使うかも決めると $O(N^2D)$ 通りあって、それぞれ $O(1)$ で解ける。具体的には、まず $p_i=q_i$ のところで $r_i$ を正と負の方向のどちらかにずらした後、それでも残った距離をどこにどれだけ割り振るかが重複組み合わせになる。

Gは遅延セグメント木。てっきり $(S,T,U)$ が順列をなすと思い込んで実装したら、サンプル2が合わなくてひっくり返ってしまった。区間について、そこにどの作用素が作用したら転倒数はどの値になるかというのを持っていたのだが、書き直している最中に順列でなければこれはうまくいかないと思い、解説にあるような順序付きペアを数えて持っておく方法にした。実は元の方法でもうまくいって、作用素 $f$ を作用させた場合は新しく $g$ に対応する値として元の $g\circ f$ に対応する値を見ればよい。ただ定数倍が悪いので、1500ms程度かかっている。

Exは解けず。パス付きのNimだと思えて、NimのほうはXORが高々 $31$ なのでどうにでもなりそうだったが、パスの回数を数えるのが不可能だった。7完27位。

コードゴルフ。Aはdcで適当に。BはPerl。DもPerlで、これは負け。他は手付かず。

午前0時、TCB50が終了した。単独理論値で見事に優勝。

朝まで日記を書いていた。今週3回あったMulti-Universities Campの部分をすっかり埋め残してしまったが、それ以外は一通り書いた。このあたりで切り上げて、また明日完成させることにする。

途中集中が切れたので寿司打をやっていた。昨日ヨドバシカメラでスマホアームを買ってきたので、手元を撮影してみた。音が小さい。

スマホアーム買ったのでテスト pic.twitter.com/V44RS63WLl
— こたつがめ (@kotatsugame_t) 2022年8月21日

久しぶりに新刊ラノベや文庫本をチェックして19冊購入した。池袋ウエストゲートパークの16巻の文庫が9月初めに出るらしい。何巻まで読んだかなと思って記録を漁ると、なんと15巻を買っていないということが判明した。そういえばラノベだけ見て文庫本をチェックしていなかった時期があった気がするから、そのせいだろうか。それにしても、リアル本屋で棚を眺める機会が極端に減ったとは言え、1年もの間気づかなかったのには驚き。一緒に注文しておいた。

布団に入ってしばらくラノベを読み、午前10時半就寝。