工事中です。

08/22(月)

午後4時過ぎ起床。Multi-Universities Campが終了したため思う存分眠れるというわけではなく、もともと月曜日はインターン先定例会でこのくらいの時間には起きなければならなかった。

メールが2通届いていた。1通目はABC264の賞金について。総合順位3位と学生順位2位のダブル受賞で合わせて45000円のアマゾンギフト券が貰えるらしい。もちろん嬉しさはあるが、本当に1WAで25000円減っていたので少しショックを受けた。

Eの1WAが響いて2位から3位に転落し、賞金額も25000円くらい減ったように見える。
週記（2022/08/08-2022/08/14） - kotatsugameの日記

2通目は日本最強プログラマー学生選手権本選について。無事現地で開催されることになったようだ。一泊するのも含めてかなり楽しみである。

【学生選手権決勝について】現地で開催予定ですので、決勝に参加されるみなさまは安全に気をつけてお越し下さい。なお、情勢を鑑みてスポンサー以外の決勝に参加しない方の会場への来場はご遠慮ください。
— AtCoder (@atcoder) 2022年8月22日

午後4時半から定例会。先週の進捗はなし。実は今振られているタスクの重要度が思ったより高そうで、結構まずいように見える。今週こそは頑張りたい。勉強会はKaggleコンペの参加記で、非常に面白かった。もちろん2か月以上コンペに参加されていたのだから、今日の発表の裏にはそれに何倍もする試行錯誤があったのだろうが、正解のルートだけ再現してもらって眺めるのは手軽で分かりやすい。ただ自分でやるのは……。一時期触っていたものの、結局すぐにフェードアウトしてしまった。やっぱり今は競プロのほうに力を入れたい。

終わってからはずっと先週の週記を書いていた。まず文章チェックをした後、5hについて三つ書く。ただそれだけのはずだったのにやたら時間がかかり、微妙に未完成のままいったん投稿する羽目になった。

午後11時半からはCodechef、August Lunchtime 2022 div.1。UIがいろいろ変わっていて少し戸惑った。特にコンテストページにLive Ratings Graphというpredictorの高機能版みたいなものが表示されていたのが目に付いた。気が散るので今のところはとりあえず非表示にしておきたい。

https://www.codechef.com/LTIME111A

TREECLRはよくわからない。木dpをしようとしてもうまくいかなかったので、dfs順に適当に決めていくことにした。結局距離 $2$ 以内にある頂点と色が異なればよいため、すでに色を塗った頂点であって距離が近いものを数えながらdfsした。飛び飛びに塗ると壊れるが、わざわざそのようなことはしないのでOK。ちなみにこれはABCで既出だったらしい。

E - Virus Tree 2

SUB12OPは謎。 $A_{i+1}\ge 2$ であれば $A_i$ が何であっても操作するだけ得になる。よってまずは後ろから順に貪欲に操作してみた。これを終えるとすべての $i$ で $A_i\le 1$ となるが、特に $A_i=A_{i+1}=1$ の場合のみ、ここで操作すると得する。これも貪欲に対処して、結果を答えとした。恐る恐る投げたら通った。

SORTARRAYは簡単。操作する区間が重なることはないので、先頭から順にその位置までソートできた段階での操作回数の最小を持てばよい。 $A_i\le A_{i+1}$ のとき $i\rightarrow i+1$ という操作回数を変えない遷移があり、また $i\lt j$ かつ $A_i=A_j$ なる $j$ について $i\rightarrow j$ という操作回数を $1$ 増やす遷移がある。後者は $A_i$ ごとに値を持っておく。

MEXPERMDIFは大変だった。 $P$ 全体のMEXは必ず $N+1$ になるので $A-B$ では打ち消しあう。ここを無視すると、なんと $B=\sum_{i=0}^N\min(P_0,\dots,P_i)$ と書けた。 $A$ も $P$ を反転すると同様。 $B$ が最大となるのは明らかに $P=N,N-1,\dots,0$ の時であり、このとき $A=0$ より $K=N(N+1)/2$ 。これが $K$ として達成できる最大になりそう。

ここから $1$ ずつ減らしていくことを考えていたら、 $P_N=0$ のとき $P$ の転倒数を減らしていくような感じで $B=K$ を $1$ ずつデクリメントしていけることに気づき、 $N\le K\le N(N+1)/2$ の構築ができた。ここから $A$ も非ゼロにしてみようと考え、試しに $P_{N-1}=0$ 、 $P_N=N$ としたところ、同様の議論で $N-1-N\le B-A\le N(N-1)/2-N$ が得られた。よって $K\le N(N-1)/2-N$ の場合の構築もできた。

この二つでカバーできず、かつ $K\le N(N+1)/2$ となるような $(N,K)$ がどれくらいあるのか求めてみる。そもそも $N(N-1)/2-N\lt N$ を式変形すると $N\lt 5$ となるし、実際全探索してみるとたったの6通りしかなかった。これらは埋め込んでAC。

MEXSUBTRは通せなかった。まず $B_{P_i}\ge B_i$ が必要。また各頂点に割り振る値の条件として、その頂点自身または祖先の $B$ であってはいけないという条件がある。この元で、各頂点 $u$ について子の $B$ の最大値 $B'_u$ 、ただし子が存在しなければ $0$ とする、を求め、 $u$ 以下の部分木に $B'_u\dots B_u-1$ がすべて出現するようにできればOKである。

根からdfsして必要な値を管理し、葉から順にそこに割り振れる最小の値をどんどん入れていくコードをまず書いた。WA。 $B=0$ なる頂点では割り振る値がある程度大きい必要があるため、大きな値はできるだけそういう頂点に割り振るべきである。よって今度は逆に必要な値を大きいほうから見てどんどん割り振っていくコードを書いた。これもWA。

デバッグを進めるうちに、2種類のコードで落ちるケースがdisjointになったことに気づいた。しかしマージしてみたところ、WAのケースが二つの和集合になってしまいどうにもならない。結局修正できず終わった。4完15位でレートは2773→2799(+26)、highest。

MEXSUBTRについて、どうやら後者のコードで不可能かの判定が間違っていたらしい。先に葉のほうに大きな値を割り振った結果、部分木内で必要な値を入れる頂点が確保できなくなってしまうケースがある。つまり、二つのコードをマージするときは答えの $\min$ や $\max$ を取るのではなく、判定が食い違ったときに割り振りが成功したほうの答えを出力するようにすべきだったらしい。別に正当でも何でもないが、先ほども述べたように落ちるケースがdisjointなので、これで通った。

その後ちゃんとupsolveした。下の部分木から順に決めていくのと、割り振れる値の最小値が大きい頂点から使うのを両方正しく実装すればよい。multisetで管理してギリギリの頂点を使うようにし、まだ使っていない頂点集合をマージテクで取り回したら通った。

先週の週記を改めて完成させた後、今日の日記を書いていた。午前7時半ごろ終えて布団に入り、眠気の限界までハーメルンを読んで午前10時就寝。

08/23(火)

午後6時起床。外出しようかななどと考えていたものの、もはやそのような時間ではなかった。意気消沈し、しばらくハーメルンを読んで午後8時半頃に寝落ちした。

08/24(水)

午前0時起床。ずっとハーメルンを読み続けていたが、さすがに積読が気になる。少し主人公が苦しむ展開となったあたりで離脱し、今度はラノベを読み始めた。昼間までに2冊読了。

1冊目、「ひきこもりの俺がかわいいギルドマスターに世話を焼かれまくったって別にいいだろう？」2巻。感想が何も出てこない。ストーリー的な面白さは皆無だったが、キャラがコミカルでかわいいし苦しい展開が存在しないため、読んでいて全く苦にはならなかった。そういうのもラノベとしての面白さの一種だろうか。コミカライズが開始するくらい売れているというのは自分の感覚とは全く合わないが、好みとはもともとそういうものである。

2冊目、「ログアウトしたのはVRMMOじゃなく本物の異世界でした」2巻。主人公が異世界でもう一度VRMMOを始めたため、ゲーム内と現実世界でイベントが交互に進行して行った。今のところゲーム内で何か活躍したわけではないためそちらは微妙。一方現実世界のほうはこの巻でも無双しっぱなしでよい。ただし、周囲の人が主人公に教えを乞い、また主人公のほうもそれに応えて指導するような立ち位置に回りがちだったのが読んでいて少し不満だった。他の人との関係にどれも上下の差があるように見えてどことなく不安な気持ちになるし、教えてばかりでは見せ場を失っているようで残念。活動場所が主人公のレベルに合っていないのもモヤモヤした。

その間にやっていたことを二つばかり。まず、TCO Finalsの旅程が提案された。見ると山形空港から朝9時に出発することになっていてひっくり返ってしまった。場所も時間も伝えた要望と全く異なっている。慌てて、そういう理由だからこのスケジュールでは全く受け入れられないということを伝え、旅行代理店にもう一度確認してもらった。

次に、TLにURLが流れてきたため、午前7時半からあさかつというバーチャルコンテストに出た。20分弱で全完。たまに出てるよなと思って日記を検索したら、前回出たのが1年以上前だった。

https://kenkoooo.com/atcoder/#/contest/show/725415d4-0843-48f6-97cb-2ed7026be7f9

あさかつの並走者を募集するツイートを見かけたので、yukicoderを途中で切り上げて参加してみた。
週記（2021/06/28-2021/07/04） - kotatsugameの日記

正午くらいに学食に向かって昼食。今日も納豆2個をミールカードで会計する件で店員に止められたので、以下のような決まりになっていると指摘した。すると別の店員に確認しに行ったのだが、そこにたまたま当時担当した人がいたため説明が伝わって、無事同様の対応をしてもらうことに成功した。

レジを2周せずとも一旦お盆から出すなりすればその場で2回会計を行ってもらえることになった。今回以降ずっとこれで良いという確認は取っている。
週記（2022/06/27-2022/07/03） - kotatsugameの日記

しかし確認を待つ間に後ろに行列ができてストレスになったし、会計を終えてその場を離れたときに後ろから「言ってくれないとわかんないよ～」など聞こえてきて大変腹が立った。最初は聞こえよがしに言っているのかと思って腹を立てていたが、これはただの被害妄想である可能性が高い。そもそも、このような対応の存在を店員に周知していない学食側に非があるため、その辺りを理由に腹を立てるべきだった。もしかして1か月近く間が空いたから僕がもう来ないと思ったのか？絶対卒業するまで定期的にバトルしてやるからな。

散髪し、購買で予約していたラノベを購入した後、バイク屋に向かった。原付の保険更新。しかし今年は自賠責保険と任意保険が同時に切れるようで、任意保険分の金額しか用意してこなかったので、改めて耳を揃え近くまた来なければならない。

午後2時過ぎに帰宅。しばらくYouTubeを見てから週末のオンサイト用の切符を購入するために家を出た。出がけにAtCoder Problemsを確認したら、最短コード保持数がついに2000の大台に乗っていた。

Shortest 2000 pic.twitter.com/7V68ELZGlU
— こたつがめ (@kotatsugame_t) 2022年8月24日

みどりの窓口に並んで無事購入。今回は学割ではなく週末パスを利用することにした。一応領収書も貰っておいたものの、必要ないはず。思ったより安く切符を購入できたため伝えていた交通費と差が出てしまったが、この差額はそのまま僕の懐に入ることになる。以前も学割の割引分がそうなったのを覚えている。本当にいいのだろうか。

午後4時から4時間ほどゲーセンで遊んだ。イヤホンを変えたら音の聞こえ方がだいぶ変わって、LATEが多く出るようになったため少し判定をずらした。今日は新曲を埋めた後、スマホアームを設置して手元を撮っていた。スコア的な成果は14のAJ+1、14+のSSS+が+1。

撮った手元は以下のリプライツリーにまとめている。Ascension to Heavenは今日3回目で、なぜか上手かった。後半は1回目のほうが上手かったのだが、譜面を少し忘れていて途中の5鍵に対応し損ねたためスコアは低くなってしまった。Vallistaも今日3回目。以前のAJがまぐれで出たものではないということが確認できて嬉しい。

きゅうりバーにダイブはお題を募集したときにリプライされたもの。中盤の1分の1ノーツ3連打を片手トリルで取る運指はお気に入り。しかし今日は全然うまくいかず、AJまで20回以上プレイする羽目になった。変なところでアタックがたくさん出るのに悩まされていたが、後から、指一本でもスライダーの上下で判定が分かれて巻き込むため、上か下の半分だけ押さえるようにするべきとの指摘を受けた。

ところで、後ろに並んでいるmaimaiのボタンの音がかなり大きく入り込んでいてびっくりした。実際にプレイしている身としてはイヤホンをつけているためかそこまでうるさい印象はない。

月詠に鳴る 13-0-0 手元 pic.twitter.com/qEBtFyh7lp
— こたつがめ (@kotatsugame_t) 2022年8月24日

油そばを食べ、帰宅。手元動画をツイートした。眠気の限界で動画を確認しつつ何度も意識を飛ばしそうになっていた。リプライツリーにまとめ一気に送信し、シャワーを浴びて戻ってきたらすでにツイートが完了していた。改めてチェックしてすぐ就寝。午後10時半だった。

08/25(木)

午前7時起床。正午くらいまで布団に横たわったままグラフ理論の教科書を読んでいた。

布団から出たら昨日のTCO Finalsの旅程についてメールが来ていた。仙台空港から出発したいと言っていたのだが、そこから東京や大阪に飛ぶ国内線がなく、フライトを組み立てられなかったらしい。仕方ないので羽田空港を指定して、そこまでの行き帰りは自費で賄うことにした。もともと自宅と空港の間の交通費は出してくれないのだ。まあそれくらいならいいかという気持ち。

シャワーを浴びて午後1時過ぎに大学に向け出発。途中購買でお菓子類を買い込みつつ、以前伝えられていた時刻である午後1時半に普段セミナーで使っていた教室に着いた。しかし誰もいない。なぜかZoomリンクがメールされていたので、今日はオンラインになったのかな？と思い接続。チャットでどこにいるか聞いてみたら、一つ下の階の教室だった。急いで向かい、無事合流した後は、今日は指導教員の先生と博士課程の人の発表を聞くだけで終わった。

終わってからしばらく、なぜか同じ教室にいたB2の人たちを交えて話していた。今日は通常のセミナーではなく、指導教員の先生が前期に行った講義の一部みたいな扱いだったらしい。なのでB2の人もいたというわけ。では時間と場所はいつ知らされたのか、といつもセミナーをしているもう一人に聞いてみたら、1週間前にメールが来たとのこと。自分のメールボックスを調べると、あった。しかも「承知しました」と返信すらしている。なぜこのようなやらかしをしてしまったのか……。

午後6時に帰宅。しばらくYouTubeを見ていたら、先生からR言語に関する頼み事のメールが来て、それで日付が変わるくらいまではずっと調べ物をしていた。

ハーメルンを読み返したり、インターン関連のコードを書いたりして午前4時。ラノベを読んで午前5時半に寝た。

08/26(金)

正午起床。布団に転がったままYouTubeを眺めて1時間くらいドブに捨てた。起きて外出。

まず学食。今日も納豆を2パック購入したが、特に何も言われず一度に2パック会計してもらえた。なにも指摘せずに利用している僕も僕であるとはいえ、このように店員によって対応に差があるのもモヤモヤポイント。最近YouTubeで納豆のシートをパックの口を閉めて引き抜くように外しているのを見たので、試してみたところ、シートについた納豆をチマチマ外す手間がなくなり非常に簡単でよかった。

この後の行動は水曜日とほぼ同じだった。ラノベを受け取り、バイク屋に向かって今度は自賠責保険の更新をして帰宅。

少しコードを書き進め、午後3時から1on1。昨日今日で産んだ進捗を報告した。自分でそれなりに形になってきたと思っていたのに、かなりまずいケースが見つかって、その場でなんとか修正しようとするうち至る所が崩壊。試した方法ではうまくいかないというのが分かったので、別の方法が提案され、それを実装して動作させるのが来週までの課題となった。今日は1時間で終了。

しばらくYouTubeに意識を吸い取られていたが、サークルのバーチャルコンテストがもうすぐの午後4時40分から始まるということを知り、参加を決めた。

https://kenkoooo.com/atcoder/?user=kotatsugame&rivals=&kind=category#/contest/show/4dd18aab-6fc0-4698-938e-2127ea28d7a0

全問解いたことがあるのに詳細を忘れているものが多く、特に5問目は考察に苦労。7問目は逆につい最近の問題で考察をほとんど覚えていたが、これは実装が辛いタイプの問題で、今日も苦しんで通した。何とか1時間で全完。

残り時間で各問題の解説を確認し、さらに1問目の最短コードを縮めることに成功した。元のコードはdcで、特に言語アップデートが全体に入る前、テクニックがまだ熟成されていないころのもの。もしかしたらこういう見落としがまだいくつも残っているのかもしれない。

atcoder.jp

バーチャルコンテスト終了後、1時間ほど通話をつないで解説会が行われた。いろいろ話した後、参加者が全員日曜日のオンサイトに参加する人だったため、当日はよろしくお願いしますと言いつつ終了した。

しばらく日記を書いて午後9時20分からyukicoder。

yukicoder contest 358 - yukicoder

Aはよい。Bは $-1$ の個数を $N/2$ 以下で決め打って、 $1$ と交互に並べたときに $f(S)$ がどのような値になるか紙で計算。個数がちょうど $N/2$ のときとそうでないときで微妙に違う式が出たので、それぞれで最小値を求め、 $\min$ を取った。

Cは「良い数列」の先頭から累積XORを取ると末尾が $0$ の $01$ 列が得られ、これの逆変換を考えることで末尾が $0$ の $01$ 列と「良い数列」が一対一対応することがわかる。変換後に $1$ になった箇所で順に操作するのが最適だから、 $f(S)$ の値が出現する $1$ の個数と一致する。よってこれを固定し、変換後の列として数え上げればよい。

Dは $N\le 3$ で実験し、 $N=4$ を考えているうちに、偶数番目の山だけ見てNimをすればよいのではないかと感づいた。山 $1$ 以外に移す操作に対してはほぼキャンセルのような操作ができるし、奇数番目の山からは山 $1$ に移せないため。出したら通った。

Eは上のbitからどこかで立てるか立てないかを決めていく。Fも上のbitから見て、大小関係がそのbitまでで定まらないグループに分けていく。

Gは $\bmod{998244353\times 999630629}$ を考えてみたりするもうまくいかない。しばらくして、 $\sum_{i\in S}A_i$ がそれほど大きくならないことに気づき、これが $999630629$ 以上となるような $S$ の数が数えられれば十分であることが分かった。逆に $S^c=\{1,2,\dots,N\}\setminus S$ を考えてもよくて、 $\sum_{i\in S^c}A_i\le \sum A-999630629\lt 4\times 10^5$ が条件となる。単に部分和dpでは間に合いそうにないが、 $A_i$ の値が同じ $i$ を数えて一気に遷移するようにしたら通った。

Gの解説を読むととんでもないことが書いてあってびっくり。これが想定解で星3.5というのはさすがにヤバいだろう。ただ、そもそも $\sum A\ge 999630629$ という条件が強いので、自分のような解法を落とせるケースがあるとも思えない。詳しい解析をしようと思ったものの $A$ の分布を調べる必要があって断念。TLで、その条件が成り立つとき $A$ の種類数が $\sqrt{4\times 10^5}$ 以下であるという事実が流れてきたが、解析に使えるかはわからない。

それから深夜までまた日記を書いていた。そろそろ寝ようかと思った頃合いでMeta Hacker Cupの今年の予選が始まったので、参加。B2を提出したときにエラーが出てしまったが、それ以外は問題なく進んで、順位表からわかるように1時間ちょっとでD問題の提出を終えた。コンテスト終了が月曜深夜なので、内容に対する感想は来週の週記に書こう。

Meta Hacker Cup - 2022 - Qualification Round

明日の準備としてノートPCのUbuntuのアップデートをしていたら、バージョンを上げられるらしかったので、上げておいた。Dockに表示したくないアイコンが生えていたので、いろいろ調べてgsettingsを弄り、消すことに成功した。

荷造りは明日することにして何が必要かだけリストアップし、午前4時半就寝。

08/27(土)

午前8時半ごろに目が覚めてしまい、二度寝できなかった。1時間ほどスマホを触った後布団から脱出。

昨日のMHCのB2について、エラーが出た後ソースコードと、出力ファイルをzip圧縮したものをclarに送り付けておいたのだが、今見ると提出が行われたことになっていた。送ったファイルから作ったとのこと。これで無事全問に対し提出できたことになって、今のところの順位は17位。これならちゃんと午前2時を待って真面目に参加すればよかった。そもそも昨日はそのくらいの時間には寝ている予定だったのだ。

ここに参加記が入る

地下鉄に乗るため歩いているとき、国際センター駅の前の道路が渋滞していてびっくりした。駐車場に入るための車列だったようだ。何が行われるのだろうか。

ホテルのチェックインについて。プール利用の説明が始まってびっくりした。ちゃんと安いプランを選んだはずなので、このために宿泊費が高くなっているということはないはず。水着を用意していないため適当に聞き流した。また、宿泊費を現金で支払ったらお釣りを1800円多く渡されてびっくりした。あまり頭が回っておらず一度財布に入れてから気付いたため、向こうから渡されたピン札に癖を付けて返してしまいちょっと申し訳ない気持ちがある。そう、ちゃんと全部ピン札でお釣りが来たのだ。やはり丁寧だなあとの感想を抱いた。

昼食について。まだ開いている店でちゃんと食事できるところもあったが、中国料理でランチのコースですら6000円弱とさすがに厳しい。そもそも中国料理にあまり興味がない。しかしディナーがその倍以上することを知った今は、せっかくなら挑戦してみてもよかったかもしれないと思う。いや、その場合は夕食をあまり食べられなかっただろうし、難しいところ。

ちなみに選んだ店は、最初喫茶メニューだけということを知らずに入って、やっぱりいいですと出て行った経緯がある。それでもう一回来たのだから店員さんに覚えられていて、上の中国料理の店なら今も食べられますよと言われたのだった。今たくさん食べると夜つらいなどモゴモゴ言ってその場は流したが、そこを選択しなかった一番大きな理由は金銭的な理由である。そんなことはさすがに言えない。

参加記のほうでは写真を貼ったので、日記ではツイートを貼っておこう。ちなみに1800円だった。これに関しては喫茶店なんてほとんど入ったことがないので、そんなものか、くらいの感覚。

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

ゲーセンについて。GiGO新宿西口店に行った。ここは地下1階に音ゲーコーナーがあり店の外のエレベーターや階段を使って降りる必要があるのになかなか気づけず、しばらくUFOキャッチャーの間を彷徨い歩いていた。手袋を持ってきていないので素手でのプレイになったが、まあまあ上手かった。13+の1落ちは驚き。ただのラッキーに思えるので理論値を狙う気はない。「ぼくらの16bit戦争」99AJは今日一発。上手すぎ。終盤の速いトリルで結構出したのが残念だった。

EXECUTOR 1落ち人はなぜ pic.twitter.com/YLTcLgrR3Q
— こたつがめ (@kotatsugame_t) 2022年8月27日

ぼくらの16bit戦争 99AJ！！！ pic.twitter.com/7WeKntpNkf
— こたつがめ (@kotatsugame_t) 2022年8月27日

夕食について。ゲーセンでお会いした面々との夕食は感染症対策と言って遠慮したのだが、実際は一人で豪遊する予定だったからである。ところが予想以上にディナーが高かった。金銭自体はATMに走れば何とでもなるものの、そもそも服装が見合っていない。Tシャツの上に一枚羽織ってみたのもどのくらい効果があるだろうか、1万円を超えるような店にはさすがに入れない。御膳は5800円だったのでこれなら許されるだろう。

店に入ると昼と同じ店員さんに案内された。まだ僕のことを覚えていたらしく、特にTシャツの柄であった立山とライチョウについて言及された。この店では立山という富山の日本酒を置いているらしいが、コンテストもあるし財布も心もとないので今日は遠慮した。ところでTシャツを覚えられているのは実は良くなかったのではないか？昼もちゃんと上着を着ていけばよかった。背伸びしているなあくらいの寛大さで許してほしい。

最初に一品出てきたので御膳と言いつつ懐石料理っぽく出てくるのかと思ったら、全然そんなことはなかった。ただのお通しだったらしい。普段の食事と同じ感じでガツガツ食べ進めたら15分で完食してしまった。味わおうと努力はしていたもののほとんど何もわからなかった。どれも美味しいのは確かであるが、どう美味しいのかを自分の経験と比較できず、表現できない。普段適当なものしか食べていないのに都合よく舌が鋭敏になったりはしないということ。

ただ、こういう値段がつけられた食事をするという体験ができただけで十分よかった。できるならやっておくべきことの一つだと思う。今必要かはともかく。

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

シャワーを浴びた後少し時間が空いたので、その間は今日の行動記録を書いていた。上のエピソードは大体この時に記録しておいたものから復元している。そういえば、ホテルのエレベーターが高層階と低層階で分かれていたのも面白かったが、言及するタイミングが見当たらなかったのでここに書いておこう。

午後9時からABC266に出た。

AtCoder Beginner Contest 266 - AtCoder

Aは咄嗟に短い書き方が思いつけなかったのでC++で書いた。BはまずRubyで書いて、その後言語を変えつついろいろ試してみた。負の数のせいでdcやAWKが弱く、PerlとRakuの17Bが作れた中では最短。Cは外積で角度を判定。DとEはdp。Eはどちらかといえば漸化式が近いか。Fはなもりグラフの閉路を検出するだけで、いつかライブラリにしないとなと思いつつ今日もフルスクラッチした。

GはRGの個数で包除原理。RGを組にしておいてR、G、Bとともに並べる場合の数を数えるのは、前計算により定数時間で行える。RGを $K$ 個作った場合から $K+1$ 個作った場合を引くだけで答えが出ると思い込み、実際にサンプルもあったので提出。しかしWA。サンプルをよく見ると、そもそも $K+1$ 個作れないケースしかなくてびっくりした。改めて $K$ 以上 $\min(R,G)$ 以下を全探索し、係数を正しく掛けてようやくAC。

Exは解けず。あるすぬけ君を捕まえた時刻・座標からスタートして別のすぬけ君を捕まえられる条件を書き出してみると、 $T$ 、 $Y$ 、 $X$ 、 $T-Y-X$ または $T-Y+X$ それぞれについての大小関係四つの条件で表せることが分かった。うち一つはソートで対応できる。残り三つを3次元セグ木で表現しようとして、残り時間をすべてつぎ込んでフルスクラッチ。50分くらいかけて完成したが当然のようにTLEし、手元で16secくらいかかったままどうしようもできず、コンテスト終了。

7完33位。Exはもうちょっと頭を使うと $T$ に関する条件が削れて、2次元セグ木で解けるようになるらしい。あとはセグメント木ではなくBITを使うと速いとも指摘されたが、改めて書き直すのが面倒で、3次元BITが通るのかはまだ試していない。

しばらくコードゴルフしていた。以降の内容はECR後に少し縮めたものも含む。Aは最初と最後の文字を削除するのを繰り返すというVimの解が上手い。Bはやはりどうしようもなかったようで、コンテスト中の17Bがそのまま最短になっていた。Cは $AC$ と $BD$ が交差するか判定する解法が上手いなと思ったものの、コードとしては普通に偏角を見るほうが短いようだ。Eは答えに $6^N$ を掛けたものをOEISで探したがなく、ループを回して計算。直前の値を整数に切り捨てたものを見れば $1$ から $6$ までのうちどの出目まで振りなおすかがわかるため、漸化式が閉じた形で書ける。他は手付かず。

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

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

Aは何かうまい方法があるのかよくわからない。色の出現回数の列としてあり得るものを全列挙し、それぞれ手で答えを求めた。Bは $x=1$ と $y=m$ を通るか、 $y=1$ と $x=n$ を通るのが最適。それぞれ $(s_x,s_y)$ に最も近づくマスだけ見て判定した。

Cは、 $a_i\le b_j$ となる最小の $j$ について $d_i^{\min}=b_j-a_i$ となる。この $j$ は制約より $j\le i$ を満たすが、特に $j=i$ となる $i$ について、その位置より前にある $i'$ がその位置以降にある $j'$ に対応することはない。逆にそうでなければ対応させられるということから $d^{\max}$ がわかる。

Dは上の桁から見て $0$ と $1$ 、 $1$ と $0$ をペアにする。要素数が食い違ってうまくペアにできない場合はそのbitを立てるのを諦め、ペアにできた場合は列を分割してそれぞれ計算。ペアにできないと分かった桁でうっかり分割してしまわないよう気を付ける。vectorを作ったり消したりするので、代入をいくつかswapで書き換えておこうとしたら、ミスして1WA。

Eは面倒。 $s+t$ におけるprefix functionの最後の要素 $p_{|s|+|t|}$ を $k$ とする。 $k\le|s|$ かつ $|t|\lt k$ の場合、 $s$ の末尾 $k-|t|$ 文字が $s$ の先頭 $k-|t|$ 文字と一致する。これはZ-algorithmで検出することができて、さらに $s$ の $k-|t|+1$ 文字目から $|t|$ 文字に紐づけて答えを保存しておくことで、 $t$ からこの値を検索することも可能。Trie木で持つことで、 $t$ を1文字ずつ伸ばしながら検索するのは非常に高速になる。

$k\le|t|$ の場合は $k$ が小さいのである程度愚直でもOK。あまりに愚直に実装すると $O(|t|^2)$ かかり、 $t$ を1文字伸ばすことも考えると3乗になってしまうが、 $t$ を1文字伸ばした時この $k$ が高々 $1$ しか増えないことに注目すれば、全体で $O(|t|^2)$ に改善することができる。

$|s|,|t|\lt k$ の場合が問題で、このケースにはサンプルを試して気づいた。ただ対処は簡単、直前の答えを $1$ 増やせるか毎回判定するだけでよい。なぜならこのケースは $t$ を縮めていくことでそのうち $|s|=k$ のケースに対応することになって、上の $k\le |s|$ で検出できるから。見落としているケースがないか心配で恐る恐る出したら、通った。

Fは謎。わからなすぎて寝ようとしたが、ふと二部マッチングの構造を調べるのにDM分解という方法があったなと思いだし、検索した。以下のページや検索して出てきたPDFを見つつ考えるうちに、最大マッチングのサイズを減らすには頂点を一つずつ削除するだけで良いのではないかと気づいた。ページの用語を流用すれば、 $W_0^+$ の頂点と、 $W_i^-$ （ただし $1\le i\le K+1$ ）の頂点を順番に削除する。辺の管理も、最初の状態における最大マッチングから1本ずつ減っていくだけなので簡単。試しに出してみたら通った。

Dulmage–Mendelsohn decomposition （DM 分解） | cplib-cpp

全完4位。Fの形式は面白かった。最大マッチングを常に管理させておきたいが、毎回出力させるのは不可能。そこで、いつもは辺番号の和だけ出力させる。そこから最大マッチングを復元するのは不可能なので、ジャッジはこれを無視しているはず。ただし、たまにオンラインクエリでそれを達成する最大マッチング自体を聞かれるので、解答プログラムは常に正しい最大マッチングを管理しておかなければならない。

1時間半で全完できたのでコンテスト終了を待たず寝ようとしていたのに、準備を整えている間に終わってしまった。少しTLの感想戦を眺めて、就寝したのが午前2時前だった。

08/28(日)

午前8時起床。

朝食について。朝食会場は僕らが行った店のほかにもう一つあった。そちらはビュッフェ形式もやっていて、それで朝食の量を気にしていたのだ。ビュッフェで大量に食べるのとお替り自由のご飯を大量に食べるのは違うだろうが。一方その店は僕らがレストランフロアに降りてきたとき非常に混んでいた。僕らが入った店では並ばず食べられた、というのには満足。ちなみにどちらでも普通に食べると3500円らしい。朝食付きプランにして大正解。