08/01(月)

午後0時半起床。

7月の読書記録のツイートをした。先月も全然読めていない。なろうを合わせても少なめ。数日ほど睡眠時間を削って読みふけっていた日があったが、途中でそんなことをやっている暇はないということに気づいて、300話ほど読んだところで止まっている。

7月の集計
買った：18冊
読んだ：8冊
積読：+10冊
積読（累積）：+76冊
— こたつがめ (@kotatsugame_t) 2022年8月1日

午後1時から今日も元気にMulti-Universities Camp 5回目。

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

お誕生日コンテスト。とにかく酷いセットだった。このCampは本来有料だと以前に言ったが、お金を取っておいてこのセットを出すのはさすがにヤバい。writerに「そういう問題」を用意するという悪意がないのがまた悪い。

普段よりかなり簡単な問題ばかりが並んでいるうえに、基本的にすべての問題文が難読で、解釈をサンプルから補うしかない。しかもそのサンプルが間違っていてコンテスト中に置き換えられたり、ジャッジ解が間違っていたり。

チームでBGKFDHCIAEの10完、5位。なぜか上2チームも同じ日本チーム。ワクワクコンテストに強すぎるだろ。僕はGFDAを解いた。

Gは担当した問題では唯一特に壊れていなかった問題。ただし制約にマルチテストケースだと書いてあって、しかもケース数が与えられないので、わざわざwhile(cin>>N)として読んだ。ちなみにマルチテストケースだというのは大嘘だったようで、今見たら修正されていた。他の問題にはまだその記述が残っているものもあって、それも当然のようにマルチテストケースではない。

Fは難読気味だった。円が積み重なっているので、見える縁の長さを求めよというもの。各円について、その上にあるとされている円で覆われていない部分の円弧の長さを足し合わせたら通った。日本語で整理して書くとあまり変な問題には見えない。コンテスト中は円の和集合の境界の長さを求めるのと解釈を迷ったのだ。

Dはサンプルが間違っている問題。問題文は「木があって、葉に1羽ずつオスまたはメスの鳥がいる。部分木であって、そこにいる鳥がすべて同じ性別であるようなものを数え上げよ」というものだった。ただし鳥の性別は各頂点に対して与えられているのが不穏。サンプルを見ると、ちゃんと元の木における葉にだけ鳥がいるとして計算した値になっているから、安心して木dpを書いた。WA。

しばらく唸ってふと問題ページをリロードしたら、サンプル出力が変わっていた。馬鹿がよ……。もともと出力の欄では「部分木であって、その部分木の葉がすべて同じ色（色とは？）であるようなもの」を数え上げよと指定されていたから、その解釈に合わせた形になる。ちょっと面倒になったがこれも木dpで解ける。出したら通った。

ちなみにこの後いろんな問題ページを開いてリロードしていたら、Hのサンプルが更新されたのを見つけた。この問題はさらにひどく、ジャッジすら間違っていたようで、以前に出したコードをもう一度出したら通ったらしい。パラメータ $n$ で定まる図形の面積を求める問題だが、図形は $n$ を変化させても相似なので面積は $An^2$ という形になって、サンプルから $A$ を求めれば通るはず。なのに以前の答えは $An^2+Bn$ という形をしていたようだ。

Aは担当した問題の中で最悪。平面上に $N$ 点与えられるので、原点スタートで移動距離が狭義単調減少となるように何個点を辿れるかという問題。同じ点を通ってはいけないと思ってしばらく考えてみるも全く手掛かりがつかめない。そこで問題文をよくよく確認すると、なんと同じ点を通ってもよいとも書かれていることが判明した。問題設定で各点にfoodが置かれていたのだが、「at each point, there is only one unit of food」と言ったすぐ後に「each point has an infinite number of food items」と言っている。どっちだよ。

何度も通っていいなら簡単、と思って出すとWA。何もかもを疑って、例えば座標が同じ点を特別扱いしたり、直線移動の最中に別の点を通るとダメとしてみたりしたがどれもWA。1時間ほど苦しんでいたところでワクワク要素のネタバレが共有されてきて、それを読んで通した。どうやら距離の計算をジャッジと同じようにオーバーフローさせると通るらしい。馬鹿じゃないの？

座標の制約が $-20000\le x,y\le 20000$ になっていて、このとき距離の2乗が最大で $2\times (20000-(-20000))^2=3.2\times 10^9$ となるためギリギリint型に収まらない。unsigned intを使って計算していたところをint型にしたら通ってさすがに笑ってしまった。

このあたりでインターン先定例会のため離脱したが、残りEとJのうちJはほぼAC不可能なため、Eが通った後はチーム内でも特にやり取りしていなかったようだ。

ちなみにJはこの日記を書いている今もAC者がいない。この問題の壊れ方はシンプルにして究極。小数を出力させる問題なのに完全一致ジャッジらしい。もしかしてAC者がいないから直すの後回しにしたのかな？AC者がいないのは難しいからじゃなくてジャッジが壊れているからなんですよ。

定例会は特に何もなし。勉強会はUnityの話で、最近触り始めましたと聞いてふーんと思っていたら、終盤で普通のCG画像に見劣りしないようなものが出来上がっていてびっくりした。いくらアセットを使ったとはいえ上達が速すぎる。

それが終わった後はずっと日記を書いていた。とりあえずいったん文章を書きあげて、読み返している最中に午後11時半になったので投稿、CF #811 div.3に出た。

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

ABはよい。Cは貪欲でも良さそうだが前計算した。Dは特に何も考えずdp＋復元。Eはちょっと難しい。数回操作すると $a\bmod 10$ を $0$ または $2$ にできて、そうしてよい。 $0$ の場合はもう変化しないので、その状態で一致しているか見る。 $2$ の場合は、手でやってみると $\lfloor a/10\rfloor$ を $2$ ずつ増やせるようだったので、この偶奇が一致しているか見た。

Fは面倒。とりあえず $1-2-3$ 、 $1-3-2$ 、 $2-1-3$ の順番でパス状に並んでいる場合だけ考えたが、サンプルを見て三叉路みたいになっている場合があると気付いた。ただこれも、三叉路の中心からの距離を決めて構築できる。GはLCAをダブリング＋二分探索で求めるのとほとんど一緒。

全完7位。EFで少しずつ詰まった以外はペナもなくて良かった。

日記を完成させる。このあたりから眠気がひどく、うつらうつらしながら読み返していた。何とか最後まで文章を整えて午前2時に確定。疲れ果ててしばらくぼんやりYouTubeを眺めた後、午前4時過ぎに就寝した。

08/02(火)

午後1時起床。まだ眠気が残っていたがスマホを触り始めてしまったので、これはしばらく眠れないやつだなとわかる。どうせ眠れないなら起きようかと考え、午後2時に布団から出た。

購買でパン類と予約していたラノベを購入し、帰宅。昨日の日記を書き始めたが、そのうち急激に眠くなったので布団に倒れこんだ。午後5時から午後7時まで寝ていた。

目を覚ましたものの、今日はこのままベッドで一日を終えようかなという気分になっていた。しかしDMを確認するとyukicoderのTester依頼が届いていて、考えているうちに微妙にやる気が出てきたので気合いを入れて起き上がった。作業を一段落させた後はまた日記を書くのに戻った。このあたりの時系列を詳しく説明すると、経過時間から問題の難易度がバレそうだと思ったが、まあそのくらいはレベル設定からもわかるか。

ひとまず最新の時点まで日記を書き終えたのが午後11時前。食事してスマホを見ると、GCJ World Finalsの参加可否を問うメールが届いていた。欠員が複数出たのか、30位だった自分のところまで降りてきたらしい。文面を見る感じ自分より上の人も回答待ち状態ではあるようだ。ただ出られるのなら参加したいので、そう返信しておいた。

Hi,

We are reaching out because it is possible that a spot may open in the 2022 Code Jam World Finals (currently we are awaiting responses from higher ranks in the next ~24 hours). Please reply ASAP if you would be able to join us for the Finals in the event
— こたつがめ (@kotatsugame_t) 2022年8月2日

今日は比較的暇である。セミナー準備からは目をそらしつつ何をするか考えて、先週書くと宣言したMulti-Universities Camp 3回目のI問題の解説記事を書くことにした。これについては現在進行形でブラウザのタブが10個程度開いてあって、それが保存されておりかつ読解した先週の記憶が定かであるうちに書き上げてしまわなければならなかった。

12時間かけて一気に完成させた。

kotatsugame.hatenablog.com

全編通して組み合わせ的な解釈のみでゴリ押している。具体的には $\sum_P c(P)^k$ 、Touchard's congruence、 $|P_{k,n}|=S(n+k,n)$ がそういう解釈を頑張ったところ。一つ目は先週の時点で分かっていたためすぐ書けたものの、残り二つには多くの時間を費やすことになった。二つ目は記事を書いている途中で読んでいた論文から思いつき、説明をまとめるのに苦労した。三つ目は論文を写してきただけだが、読解しながら書いたためこれも大変だった。何とか完成してくれてうれしい。

午後0時半就寝。

08/03(水)

午後7時くらいに目を覚まして1時間くらい教科書を読んでいた記憶がある。また寝て、次に午後10時起床。

布団の中で教科書を読み進めていたが、ちゃんと前のページを読み返したりしないと意味の取れない記述が出てきたので起き上がった。これが日付が変わる前のこと。そこからハーメルンに意識を奪われたりYouTubeを見たりしつつじりじり教科書を読み進めた。

午前4時までかけて一段落するところまで読み終えた後、それを発表資料にまとめることは諦めて、先週の資料を読み返して記憶を復元する作業を行った。明日は午前中にもセミナーがあるので早く寝なければならない。午前中は先週の資料を発表して、間の時間で教科書の先ほど読んだところをまとめ午後からのセミナーに備えようという心積もりだ。

読み返し終わったのが午前5時過ぎで、その後すぐ就寝。

今日見ていた動画はこれ↓。やはり社築さんは見ていて安心感がある。ずっとレバガチャを擦られ続けていて面白かった。十数年前にやったきりと言っておきながらちゃんと上手いのはすごい。いくら相手が初見だといってもこんなに差がつくのだなとびっくりした。

www.youtube.com

08/04(木)

午前8時半起床。TCO Finals進出決定のメールが届いていた。

Hello,

Congratulations! You are a TCO22 Algorithm Finalist! 🎉
— こたつがめ (@kotatsugame_t) 2022年8月3日

今のところオンサイトで開催予定らしい。アメリカ旅行である。こうなってみると、今年度の初めに身分証明書としてしか使う予定のないパスポートを頑張って更新しておいたのはかなり偉かった。ただ、英会話が怖い。一応海外に行った経験が2回あるのだが、それぞれ同じ日本人旅行者と常に一緒に行動したり、日本語を話せる通訳の方がついてくれたりしたので、自分から英語を話す機会というのはほとんどなかったのだ。

そろそろ期限が切れるパスポートを更新しなければならない。
週記（2022/03/07-2022/03/13） - kotatsugameの日記

食事してセミナーに向け出発。ちゃんと時間通り二人揃ったのだが、肝心の先生が来ない。うっすら忘れておられるんだろうなということはわかっていたが、昨日やり残した発表資料のまとめが終わっていないため何食わぬ顔でしばらく準備を続けていた。1時間程度したところで、確認のメールも送らないのはさすがにまずいということに気づき、送信。ちょっと遅すぎた気もする。

すぐ返信が来て、しばらくしてご本人も無事到着され、1時間程度セミナーをした。前回ちょっとした課題が出されていたのでまずそれの解答を確認。関連する話題でひとしきり話していたら、結局午前中は発表せずに終了した。

昼食を摂り、午後はまず講義から。木曜3限、数理論理学特論はこれが初めての出席となる。そして最終回。なのに眠気に負け、中盤は結構大胆に目を閉じていた。最後にレポート課題の説明がされたのだが、これは今日初めて顔を見せた僕も提出してよいのだろうか。ちなみに内容は、この講義に関係する論文を1本以上読んでサーベイせよというものなので、最悪講義の中身を知らなくても書けないことはないはず。

本当は数理論理学特論という僕の指導教員の先生が担当されている講義も取っていたのだが、これは一度も出席できていないためほぼ放棄している。
週記（2022/07/11-2022/07/17） - kotatsugameの日記

そしてセミナーの午後の部へ。先週用意した分のみで終わるかなと思っていたら、準備の時に行間を丁寧に書きすぎたらしくA4 6ページ分を1時間で発表し終えてしまった。今後はこれを参考に時間配分を考えて資料を用意するようにしたい。では今日用意した分まで踏み込んだかというとそうでもなくて、残り1時間は先生の指摘により、今日話した内容の具体例をいろいろ確認していた。一般マッチングに関する強めの主張（Diestel、Theorem 2.2.3）を示したのだが、実際のグラフでどんな風に実現されるか見たいとのこと。簡単なグラフをいろいろ書いて確かめていた。

夕食を摂り午後7時前に帰宅。山道を原付で走っていたところ、ガードレールの外側を歩いている歩行者がいて心底びっくりした。ちょうど道路も混雑しているからあまり大きく避けることもできない。どうやら二人連れらしく、ガードレールを挟んで会話しながら歩いていたようだ。歩道が狭いのはわかるが、ちょうど急カーブの内側なんだから轢かれても文句は言えないぞと思った。

疲れからかなりの時間TLを眺めて過ごした。三項演算子が話題になっていたので、ちょっとした言語仕様クイズを行った。どんな言語でも〇〇、ということを示すのは悪魔の証明なので、AtCoderで使える言語のみと絞り込んだとしてもとても言い切れるものではないから、メタ読みで「どちらでもない」が答えだとわかりそう。

a?b:c?d:eは（AtCoderで使える言語のみを考えたとき）
— こたつがめ (@kotatsugame_t) 2022年8月4日

(a?b:c)?d:e：PHP
a?b:(c?d:e)：C++などほとんどの言語
ということで正解は「どちらでもない」です
— こたつがめ (@kotatsugame_t) 2022年8月4日

PHPのこの仕様はかなり特徴的なので、最後にPHPを書いてから数年経った今も覚えていた。誰も得しない。後日引用RTで指摘されたことだが、PHP8.0からはこのような書き方のとき括弧を入れないとエラーになるらしい。ちゃんと「AtCoderで使える言語のみ」という注意書きを書いておいて助かった。

a?b:c?d:e は今のPHPではエラーになるはず……と思ったけど、AtCoderに入っているPHPは7.4.4だった😇
【PHP8.0】PHPの三項演算子が他言語の実装に一歩近付く - Qiitahttps://t.co/3dg8clBlBJ https://t.co/4zBGINAsyC
— kusanoさん@がんばらない (@kusano_k) 2022年8月5日

しばらくTCO Finalsのための書類を作成していた。一つ二つ完成したところで午後11時半からECR133に出た。

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

Aは $n\bmod 3$ で分類。 $n=1$ だけ2手かかることに注意。Bはfixednessを毎回1以上減らさなければならず、特に最初はちょうど2減らすことになる。逆に、 $i\rightarrow i+1$ において $i$ 番目と $i+1$ 番目をswapすることでこれが達成できるため、最適。

Cはかなり時間がかかった。しばらくジグザグ上下しながら進んだ後、右にまっすぐ行って行を変え左にまっすぐ帰ってくるという方法しかないことはすぐわかる。しかしこれを計算するのが難しい。途中で足止めされる場合はその分最初に待っておけばよいので、最後から $k$ 番目にマス $(i,j)$ を通るとすれば、だいたい $a_{i,j}+k-1$ の $\max$ を求めることになる。まっすぐ行く部分を行き帰りに分解し、右から累積的に前計算しておいて、ジグザグの部分を愚直にシミュレートした。

サンプルを試すとちょっとずれていた。 $a_{i,j}$ というのはそこに入れるようになる時刻であって、実際に入った状態になれるのは $a_{i,j}+1$ からだった。これも正確には正しくなく、 $a_{i,j}=0$ の場合は時刻 $0$ から入った状態になれる。このことを $a_{i,j}+k-1$ という式に反映すると何とかサンプルが合い、通った。

Dはdp。 $k,k+1,\dots$ と順に試すと、 $k+O(\sqrt n)$ くらいでゴールに到達していない点が存在しなくなる。よってその間を毎回 $O(n)$ かけてdpし、 $O(n\sqrt n)$ 。余りを取るのではなく $\bmod$ を引き算したりして高速化しておいたら200ms程度で通った。最初はdp配列をin-placeに書き換えるだけで答えが求まると思っていたのに、後からちゃんと答えの配列に退避しておかなければならないことに気づいたため、コードへの反映が足りず1WA。

Eはセグメント木を考えるとそれぞれの深さで子をswapするかどうかの違いになる。深さ $0\le k\le n$ のノードは $2^k$ 個あり、それぞれそのノードより下のswap方法が $2^{n-k}$ 通りあるため、合わせると各深さで $2^n$ 種類の状態がある。これらをあらかじめ計算しておけばよい。ノードにいつもの部分列の和を最大化するモノイドを乗せる。

Fはつい先日解説記事を書いたのと同様のテクニックで解ける。取り出したボールたちから奇数が書かれたボールを選ぶのを $k$ 回行うとして、その時選んだボールの種類数を $l$ とすると、場合の数は $S(k,l){}_n\mathrm{P}_l\lfloor m/2\rfloor^l m^{n-l}$ となる。これの和を $1\le l\le \min(n,k)$ で求めればよい。 $n$ が大きいので ${}_n\mathrm{P}_l$ はその場で計算しなければならず、またこの時点ですでに $O(tk)$ なのでうっかりループ内で割り算をしないように気を付ける。焦ってcombinationライブラリを貼ったりと実装に手間取るも無事AC。

1時間弱で全完して8位。Fでは考察がすぐ終わったのに実装で時間を溶かしてしまい、残念。

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

08/05(金)

午前10時くらいに起きていた記憶がある。しばらくTLを見てからまた寝たはず。

午後2時起床。1時間ほどインターン関連の作業をし、その成果を持って午後3時からミーティングを行った。今日も2時間弱。作業時間の倍も何をミーティングしていたのかというと、今日はコードを少し書き換えてプルリクを出す流れを画面共有しつつ行った。

この長期インターンを始めて早一年、ここに来て初めていかにもインターンらしいことをした。しかしこちらも素人ではないのだから、手取り足取り教えて頂くのは申し訳ない。進捗を産むことで一人でも大丈夫であると表明したい。

日曜日のDDCC本戦とその直後の帰省のため、新幹線の切符を買っておく必要がある。特に前者は交通費が出るため指定席で行くつもりだ。どの列車に乗るのかも含め、しっかり調べて紙にまとめてからみどりの窓口に向かうため家を出発した。

ちょうど花火大会直前らしく、川内キャンパス周辺は大混雑していた。駅から出る人並みに逆らって歩くのは仄暗い気持ちよさがある。つまり、逆張り精神のことだ。

みどりの窓口は外に列が少しはみ出すくらいの混雑で、30分程度並んで購入に成功した。DDCCの分は普通の切符に学割を効かせるより週末パスというものを買うほうが安くなるらしいが、もし何かの間違いで終電に間に合わなかった場合使えなくなるとのこと、どうせ交通費が出るのだからと安全側に倒して学割で購入した。

少し本屋に寄った後つけ麺を食べてゲーセンへ。今日は14+で新規AJを二つ出した。

folern AJ pic.twitter.com/6tz99jt4He
— こたつがめ (@kotatsugame_t) 2022年8月5日

folern。フリック周辺で抜けまくって大変だった。フリック階段には速度が2種類あるので速い方は思い切り速く擦るというのと、その近辺の分割タップがどこで分かれているのかしっかり見ることを意識したら多少改善したように思う。

Evans ULT AJ！！！ラスクレで決めた！ pic.twitter.com/8W9mMm1hz1
— こたつがめ (@kotatsugame_t) 2022年8月5日

追加されたときにラストがどうしても通らないので諦めたのだった。今日プレイしてみると、序盤のホールドで1アタ出したものの以降AJで通ったため、狙うことに。それも含め1アタを4回出したが、なんとか閉店直前のクレで出た。ただ99AJ精度が出ていたのにこの回だけやたら赤が出て残念。

帰宅してしばらくハーメルンを読んでいた。「アラサーがVTuberになった話。」の書籍化についての情報が出ていた。9月末発売らしい。楽しみ。

【お知らせ】
ファミ通文庫様(B6判)より拙作『アラサーがVtuberになった話。』が『アラサーがVTuberになった話。』と改題し9月30日発売予定です。
イラスト担当はカラスBTK先生（@BTKcyber）です。
旧題『アラサーがVtuberになった話。』
↓
新題『アラサーがVTuberになった話。』#アラサーV
— とくめい@アラサーV9月30日発売予定 (@hameln_tokumei) 2022年8月5日

チュウニズムの「やってやろうじゃねえかよ　この野郎！」という称号について調べていて、元ネタとなった動画を見た。念のため、この元ネタにもさらにテレビ番組由来の元ネタがあるということに触れておく。動画は面白かった。この方が作曲された他の曲のPVと同じノリの中に混ぜられた、綺麗な例のアレという感じがする。

www.nicovideo.jp

午前1時から3時間でDMOJのYet Another Contest 4に参加した。これについては終了が火曜日なので、詳細な内容は来週の週記に書く。コンテスト終了後しばらく復習して、午前6時半に就寝。

Yet Another Contest 4 - DMOJ: Modern Online Judge

08/06(土)

午後0時半起床。食事して午後1時からMulti-Universities Camp 6回目に出た。

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

チームとしてMBJGAHICの8完、8位。自分はJGHCを解いた。うちJGは簡単枠。

H。FAだった。 $0$ 段目から $n$ 段目（ $n\le 10^9$ ）まで階段を上る問題。一気に $k$ 段上るとスコアが $k^2$ 得られるが、壊れている段が $m$ 段（ $m\le 2\times 10^6$ ）あってそこには立ち入れない上、壊れている段を一度に $S$ 段より多く飛び越えるような上り方ではスコアが得られない。すべての上り方について得られるスコアの総和を求める。

壊れている段を抜いた時の連結成分に分け、 $x\in I$ から $y\in J$ に一気に上がるときのスコア $(y-x)^2$ がどれくらい加算されるか見る。 $0$ 段目から $x$ 段目に行く場合の数は、 $x=0$ の場合を除いて $2^{x-1-c_I}$ と書ける。ここで $c_I$ は $x\in I$ より下にある壊れた段の数。 $I$ 全体で共通なのでこう表記している。逆も同様で、 $y$ 段目から $n$ 段目に行く場合の数は $y=n$ の場合を除いて $2^{n-y-1-(m-c_J)}$ である。まとめると $(y-x)^2 2^{x-1-c_I}2^{n-y-1-(m-c_J)}$ 。

展開すると、 $c_I$ 、 $c_J$ に関する定数を除いて $x^i 2^x$ 、 $y^i 2^{-y}$ （ $i=0,1,2$ ）を掛け合わせた式になる。あとは線形性により、 $I$ 全体どころか様々な連結成分について同時に足せる。それぞれが和を閉じた形で表せるので、Wolfram|Alphaに投げて式を写してきた。 $0$ 段目や $n$ 段目も少しずらして同様に扱える。また同じ連結成分内で移動するケースは別に足す。実装して出すとTLEしたが、写してきた式で $2$ のべき乗やその逆元を何度も計算していたので、少しまとめたら通った。

Cは、 $n$ 頂点 $m$ 辺（ $n\le 16$ 、 $m\le 100$ ）の重み付きグラフが与えられるので、辺の部分集合すべてについて最小重み全域森を考え、重みの和を出力せよというもの。辺をソートすれば、各辺 $uv$ についてそれより前の辺だけ見たとき $u$ と $v$ が連結にならないような部分集合の数を求める問題になる。包除原理などで頑張ろうとしたが式が生えず、チームメイトにHELPを求めたら、ABC213-Gの逆だと言われた。公式解説にある $O(3^n)$ では $m$ 回やると間に合わないものの、別解の $O(n^2 2^n)$ なら間に合いそう。速い提出を拾ってきて通した。

G - Connectivity 2

日記を書いて午後9時からABC263。

LINE Verda Programming Contest（AtCoder Beginner Contest 263） - AtCoder

Aから少し面倒で、以降もずっとC++で書いていた。Aはいちいちカウントして、ちょうど3回出現した要素とちょうど2回出現した要素の存在を判定。Bは根から各人の深さを求めた。Cはdfs。Dは置き換える区間が被らないとしてよい。prefixとsuffixでそれぞれ最適な値を求めるdpを行い、中間を全探索した。Eは後ろから期待値dp。

Fは、人 $2i-1$ と人 $2i$ が対戦するとき、新しい $C$ を $C_j=\max(C_{2i-1,j}+C_{2i,0},C_{2i-1,0}+C_{2i,j})$ とすることで、この対戦の勝者がこれを含め $j$ 試合勝ったときの最大値を表現できる。ここで $C_{\ast,0}=0$ としておく。例えば人 $2i-1$ が勝ったと決め打ち、 $C_{2i-1,j}\leftarrow C_j$ と書き換えることで、以降同様にすべての場合を考慮しつつ計算できる。

Gはちょっと難しかった。基本的に偶数と奇数をペアにするしかないので、ほとんど二部マッチングだと思えて最大流で解ける。ただし $A=1$ の場合が困る。そこで、 $A=1$ とペアにする場合だけコストが $1$ かかることにして、この最小費用流をACLのslope関数を使って解いた。すると $A=1$ をどれくらい使うかが全探索できる。余った分を $1+1$ でペアにした。

Exは解けず。2直線の交点を式で表してみたものの綺麗な形には全然ならなかった。残り時間はコードゴルフをしていた。7完最速で12位。

コードゴルフ。AはRakuで重複要素をカウントし、その積が $6$ になるか調べた。BはAWKかと思ったがdcで頑張ると縮んだ。Cはcombinationを生成する関数・メソッドがあるならそれを使うのが短い。RubyをVimで書いたものよりRakuのほうが短くなった。DはPerl。以降は手付かず。

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

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

A問題は軸上4方向にそれぞれ行ってそれぞれ帰ってくるのを繰り返せばよい。

Bはソートしたものを $b$ とするのが最適で、 $f(a)\le f(b)$ を判定する。 $f$ の実装はセグメント木など使おうとしたがちょっと実装に詰まった。最終的には、大きい値から順にマークをしていきつつ、その値に $1$ から隣二つのうちマークされているものの個数を引いたものを掛け、答えに加えた。

Cは常に可能。 $n-1$ 以上で最小の平方数を $x$ だとすると、 $x-(n-1)\dots n-1$ に $n-1\dots x-(n-1)$ を加えることで、問題を $n\leftarrow x-(n-1)-1$ に書き換えられる。 $n-1\le x$ なので $x-(n-1)\ge 0$ となり、このような操作がいつでもできる。

Dは4人が1人になる過程を2回のクエリで特定できる。1人目と3人目を聞くことで上手く分離できるようだ。最初ランダムに聞いて平均回数を抑えることを考えており、決定的に解けることに気づくのに時間がかかった。またこれだけの改善でクエリ回数制限を満たせることも計算して初めて気づいた。

Eは面白い。 $A_{i,j}$ と $A_{j,i}$ をswapするかどうかしか決められず、特にswapされることと、 $k=i$ なる操作と $k=j$ なる操作を合わせて奇数回行ったということが同値になる。そこで、 $k=1$ での操作回数を固定し（固定した値の偶奇には興味がないことに注意）、 $k=2\dots n$ について操作回数の偶奇が $k=1$ と一致するかどうかを決めていくことにした。辞書順なので先頭から貪欲でよく、偶奇がこれまでの決定と矛盾するかどうかは二部グラフ判定をUFで行うのと同様にして判定できる。つまり、頂点を倍化し、 $i-i'$ と $j-j'$ を繋ぐか $i-j'$ と $j-i'$ を繋ぐというのを繰り返せばよい。 $i$ と $i'$ や $j$ と $j'$ が連結になってしまうと矛盾するので、その場合は諦める。

Fは難しい。まず $a$ 、 $b=b_{\ast,n}$ を0-indexedにし、さらに $a$ をreverseしておく。この元で $b_j=\bigoplus_{i{\rm AND}j=0}a_i$ と書ける。実はどんな $n$ についても、この情報が $j=0\dots n-1$ についてわかっていれば $a$ を復元できるらしい。 $n=1$ なら自明。 $n\ge 2$ のとき、 $2^t\lt n$ となるような最大の整数 $t$ を取って、 $0\dots 2^t-1$ と $2^t\dots n-1$ に分割する。それぞれ $n\leftarrow 2^t$ 、 $n\leftarrow n-2^t$ として再帰していく。

まず $n\leftarrow n-2^t$ について。ちょうど $t$ 桁目のbitが立っている数だけの影響が知りたいが、これは新しい $b'$ を $b'_j=b_{j+2^t}\oplus b_j$ と定めることで計算できる。その結果を高速ゼータ変換して適切にXORすることで、以前の $b$ 全体から $a_{2^t\dots n-1}$ の影響を取り除くことができ、 $n\leftarrow 2^t$ の場合が計算できるようになる。計算量は $O(n(\log n)^2)$ くらいだろうか。200msちょっとで通った。

午前1時5分からTCO22 Regionals Algorithm Competition。いわゆるWildcard。CFと被っていたので直前まで出るかどうか迷っており、Fを考察している間にとりあえずレジだけ済ませていた。その後Fが通ったのが開始3分前くらいでかなり興奮した。そのままコンテスト突入。

コンテスト参照のためのURLはまだわからないため貼れない。

08/13追記：https://community.topcoder.com/stat?c=round_overview&er=5&rd=19337

combinedだからか4問構成だった。まず150点問題、ONACircle。これは自明。検索する文字列が円環より長いケースに注意するだけか。

次に400点問題、OverlappingRectangles。縦 $1$ 、横 $i$ の長方形を $i=1\dots n$ で重ねることで $n(n-1)/2$ 個のペアが作れる。 $n$ を最大化し、それでも $P$ が残っている場合、 $P'=P-n(n-1)/2\lt n$ だから、横 $P'$ の長方形を配置して残りのペアを作れる。あとは適当にバラバラに配置。この構築自体はすぐ思い浮かんで実装まで終わらせることができた。しかし何を考えたか手元でチェッカーを書いてしまい、それの実装と実行に時間を取られ、提出した時には40位くらいに位置していた。絶望。

700点問題、DominatedSubstrings。セグ木上の二分探索を使うと、各文字から左右にどれだけの長さの範囲でdominateできるか求まる。この情報を使い、左端の文字を全探索しつつその文字までdominateできる右端の文字の集合を管理することで、毎回可能な最も遠い右端の文字が求まる。ここから直接答えを出せる。簡単なのに焦って考察がまとまらず、また実装も少し手間取った。

1000点問題は解けず。memberに含まれる人のみをbitDPし、残りは単に人数で管理することで、計算ステップ数が最大 $((4^{10}-3^{10})\times 41+3^{10}\times 41^2)\times 50$ くらいになるコードを書いた。しかし当然間に合わず、高速化する間もなく時間切れ。

チャレンジフェーズも何もせず、今のところ22位になっている。なんとシステスは来週のイベント中に行われるらしい。なので上でコンテストURLが貼れなかったわけだ。3完のつもりで書いたコメントにも間違いがあるかもしれない。

明日オンサイトがあるのに睡眠時間を削った上でレートを暴落させ、さらにそのわかりきった結果が出るのを待って焦らされているのは無様以外の何物でもない。先ほどのCFがシステスを終え全完3位になったのを確認し、寝た。午前3時半だった。

08/07(日)

午前8時起床。眠すぎる。熱を測ったら平熱だった。ゆったり準備して出発し、仙台駅には午前9時頃到着。立ち食い蕎麦屋でカレーを食べ、新幹線に乗り込んだ。DDCC2022のため東京に向かう。

以降解散するまでのことは参加記に書く予定である。最近日記すら全然間に合っていなくてまだ1文字も書けていないが、無事投稿出来たらリンクを貼ろう。これはつまり、日曜日の日記を丸々後回しにしたのと同じことである。

午後11時過ぎ仙台に到着し、そのまま帰宅。以降しばらく日記を書いていたが、全然集中できず1時間くらいはYouTubeを見ていたはず。

午前3時に布団に入り、しばらくラノベを読んで午前4時就寝。