02/27(月)

午後0時半に目覚ましで無理やり起き、大学に向かった。昼食を摂りラノベを受け取って帰宅。

前回受け取ってから10日ほどの間に新しく14冊が入荷していたが、特に今日入荷したMF文庫Jの新刊「Vのガワの裏ガワ」2巻をいち早く手に入れたくて、頑張って営業時間内に起きたのだ。いち早くと言っても発売日は02/25だったからすでに土日を挟んでいる。このタイムラグは購買で受け取る以上仕方のないこと。

└( ＾ω＾ )┘♪ 買った♪└( ＾ω＾ )┘♪ 買った♪ pic.twitter.com/HwouYJuM0r
— こたつがめ (@kotatsugame_t) 2023年2月27日

帰宅したのが午後2時。今日は深夜からCF combinedがあり、明らかに睡眠時間が足りないのでどこかで仮眠を取りたい。さらに先週の週記も書く必要がある。インターン先定例会は動かせないので、その前と後でそれぞれどちらかを行うことになりそうだ。より長い時間を確保できる定例会後に仮眠を取ることにして、今は週記を書き始めた。

午後4時半から定例会。先週の進捗はあんまりない。コードをちょっと書き換えただけ。今週も今のところはそんな感じのタスクしかない。この定例会だったり1on1だったりで会議の時間だけは一丁前に長く、人件費的な意味での申し訳なさというのが少しある。

勉強会は透過型電子顕微鏡の話だった。今日の発表者の専門分野なので導入は知らないことだらけで戸惑ったが、本題はアルゴリズム的な話で結構面白かった。発表自体は結構短めで、そのあと質疑応答が念入りに行われた。スライドが丁寧だったので素人なりに質問の端緒を見つけられ、それを聞くことで理解をある程度深められたと思う。自分だけでなく他の人の質問もかなり参考になった。

午後6時半ごろに終了。それから1時間くらいしてようやく週記が書き上がった。相変わらず校閲はできていないが、ともかく投稿。すぐに布団で仮眠を取った。

午後11時起床。手元を撮る環境を整え、半からCF #845 combinedに出た。

Dashboard - Codeforces Round #854 by cybercats (Div. 1 + Div. 2) - Codeforces

Aは $1\dots n$ のpostは後ろに追いやられる一方なので、新規で何種類のpostにactionがあったかカウントし、増えたタイミングで代わりに押し出されたものをチェックすればよい。TL 1secだが $n$ 、 $m$ も少し小さめなのでsetで十分高速。配列で線形時間になることには気づいていなかった。

B。最初から揃っているケースは先に取り除いておく。もし $a$ に1が含まれる場合全要素を1に揃えることになるが、どこかのタイミングで $n-1$ 要素が1になると以降どうやっても $a$ が変化しなくなるので不可能。逆にそうでない場合、 $a$ の最大値を最小値で割るということを繰り返せばどんどん値が小さくなるのに2未満にはならないのでそのうち揃う。操作回数は高々 $\sum\log_2 a\le 30n$ 回で制約に合う。

Cは難しかったがサンプルが強くて助かった。サンプル出力を眺めると二つ方針があることに気づける。一つはできるだけ左右対称にするもの、もう一つは最小の文字を右端に置いた後残りをソートして左にくっつけるもの。辞書順で小さいほうから何種類かの文字を前者によって並べ、余りを後者で並べたものしか答えにならないようなので、全探索できる。

D1は簡単。二つのCPUでそれぞれ直近に実行したプログラムの番号を持つdpを考えると、 $a_i$ を実行しようとしているとき二つの番号の片方は必ず $a_{i-1}$ なので、見るべき状態数が $O(k)$ 個になって間に合うというもの。2次元配列でdpするコードを書いて出したら800msを超えてびっくりした。シーケンシャルでないアクセスばかりで定数倍が悪いのだと思う。

D1をセグ木に乗せればD2も解ける。1点更新・取得、全体加算・MIN取得しかしないので、遅延セグ木ではなくセグ木で実現できる。D1の実装を愚直に翻訳したため二つのCPUのどちらが $a_{i-1}$ を実行した直後かでセグ木を2本持ったが書きあがってみると全く同じ操作をしていた。「直前に $a_{i-1}$ を実行しなかったCPUの状態」を持っていると考えれば1本にまとめられたようだ。

D2の実行時間が300msを切ったのでD1をリサブするか結構迷ったが、最終的にはそのままにしておいた。900msはかかっていないため大丈夫だろうと判断した。ちなみにこの問題は線形時間で解けるようだ。セグ木に書き込む値が小さくなる一方だから、特に工夫せず全体MINの更新ができる。

Eは結構面白かった。最短距離がマンハッタン距離と等しいという条件から、同じ行または列にある塗られた2マスの間はすべて塗られている必要がある。実はこれで十分だった。ある塗られた2マスが連結ならその間に塗られたマスによるパスがあるが、そのパスでもし遠回りしているところがあれば必ず一直線にショートカットできて、それを繰り返して最終的にマンハッタン距離で移動するパスが得られる。

そのように塗って自然に連結成分が一つになればよい。そうでない場合、連結成分をぴったり含む矩形が左上と右下あるいは右上と左下に分かれて位置している。前者について考えると、二つの連結成分を繋ぐようなパスを作った場合、左上の矩形についてその右下マスから1マス右または下は必ず塗られることになるとわかる。右下の矩形の左上マスについても同様。

逆に、どちらが塗られるかを決め打ちそれを最短距離で繋ぐことで答えの候補が定数個得られる。これを全部試せばよい。盤面を埋める際は変化しなくなるまで愚直にループを回した。1回に $O(nm)$ かかるループが $O(nm)$ 回回るが、 $nm$ の和に上限があるので間に合う。そもそも変化しなくなるまでにそんな多くの回数がかかることはないだろう。

順位表を見てGに進んだ。同じチームの人をあらかじめまとめておくと箱根駅伝dpができる。ただ票や投票先をどのように区別するかが問題。

自分は投票先としてラベル $i$ の箱が $c_i$ 個あると思い、これを並べることでいろいろ区別した。今票を入れようとしている箱とこれまでで保留している箱それぞれでどのように並んでいるか決めておけば、実際に入れるときは先頭からどんどん使っていくことで必要なだけの区別ができる。この場合票についてはどれを使うかは考えてもどの順番で使うかは考えない。

あるチームについて遷移するとき、 $c$ をまとめて前計算しておくことでチーム内での票の割り当ては計算できる。実際にdpを書いてみると状態数 $O(n^2)$ に対してそれぞれチームの人数と $c$ の総和の積だけ遷移先があり全体 $O(n^4)$ になってしまったが、ちゃんと枝刈りして手元で試すと爆速だった。提出したら通った。

Fは面白かった。 $a$ を降順にソートしておくと、ある $d$ について先頭から $d$ 個は両方の操作が行われ、続く $(k_1-d)+(k_2-d)$ 個は片方の操作が行われ、残りはどちらの操作も行われないという状態しか最適にならないとわかる。この $d$ を全探索する。真ん中の部分も貪欲で解こうとして操作1を優先するべき値と操作2を優先するべき値を考えていたが、うまい条件は見つからなかった。

ここで $n\le 5000$ なのに目を向けdpすることにした。普通にやると $d$ を決め打つごとに $O(n^2)$ のdpをすることになるが、 $d$ を降順に探索すれば以前の結果から毎回 $O(n)$ で差分更新できる。なぜかというと、真ん中の部分は $d$ が1減るごとに左右に1ずつ広がるのみだから。以前の結果から抜くことになる要素が存在せず、単に要素を2個追加したものと思えるのだ。

Hには20分ちょっと残せたが解けなかった。最後まで残る頂点を決め打ち、そこから木dpで場合の数を求め、最後に $s_k$ で割れば答えが求まるということを考えていた。しかし木dpで何をすればいいのかがわからなかった。

コンテスト後もしばらく録画を続け、システス結果を確認しながら各問題の振り返りをしていた。無事全部通って25位、レートは2914→2960(+46)。自分ではかなりうまくいったと思っていたが案外渋い上がり幅だった。その後動画を投稿した。

www.youtube.com

明日はセミナーがないから今すぐ準備する必要もない。昼受け取ってきた「Vのガワの裏ガワ」2巻を読み始めた。大切に大切に読み進め7時間くらいかけて読了。この巻も非常に面白かった。1巻が好みだった作品でも2巻を待つ間に期待だけが膨らみすぎて読んでみると思っていたより面白くなかった、という経験が何度かあるが、この作品はその膨らみ切った期待通りの面白さで最高だった。

この面白さがどこから来たかというと、やはり魅力的なキャラたちのワチャワチャした日常描写からだろうと思う。1巻の前半も思い返せばそういう感じだった。2巻では新キャラとの話がメインに据えられつつ1巻からのキャラにもちゃんと出番があって、全体的に日常シーンの量が増えており大満足。ストーリーももちろん良かったがやはり自分から見たメインはこちらかなという感じ。

主人公がセンターパートという髪型から偏見を受けていて笑った。確かにイケイケの大学生というか……自分にもこの髪型に対する偏った見方がある。画像検索すれば同じ感想を抱く人も少なくないのではないか。ラノベ主人公としては珍しいビジュアルだと思うが、超人気イラストレーターという設定を考えればはまり役のうまいデザインに見えてくる。

シャワーを浴びてゴミを出した。AHC018のレート更新が来ていた。493位、パフォーマンス1253、2030→2031(+1)。また次回に期待。

正午から1時間ほどインターンの進捗を産んだ。コードをちょっと書き換えた後、それに合わせてドキュメントを少し整備した。

それから大学に向かった。昼食を摂ってから購買に向かうと閉店していてびっくり。今日は決算業務か何かがあるようで普段より閉店時間が早まっていたらしい。あと10分早ければ間に合っていたので残念。

床屋で散髪した。座っている間ほぼずっと眠っていて申し訳ない。首をガクガクさせたりはしなかったはずだが、気づくと首を深く俯かせていることが多かったので、やりにくかったと思う。

午後3時頃帰宅。2時間後から1on1が予定されているので、仮眠などはせず起きて日記を書いていた。

1on1は先ほどの進捗を報告した後、次やることの導入。これまで書いていたドキュメントはツールの設定を行うプログラムを動かすためのもので、次はツールを使うためのドキュメントを書くらしい。盛り込みたいことはほとんどこの1on1で列挙できたので、清書をするのがタスクになった。1時間半ほどで終了。正直眠気が限界だったので早めに終わってもらえて助かった。

午後7時前就寝。

02/28(火)

午後11時過ぎ起床。食事して半からECR144に出た。

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

Aからちょっと手間取った。先頭の文字に対応する数字を $\bmod{15}$ で全探索すればよい。それが15の倍数の場合は最初のFを含めないケースも忘れず試す。実装上はありうる文字列をすべて前計算してから判定した。配列の長さを間違えていたがサンプルでREが出たのでペナにはならなかった。

Bは先頭または末尾の文字が一致しているか、連続する2文字で共通のものが存在すればよい。逆にそれ以外のケースは答えがない。どんなテンプレートも英子文字の前後は必ず*になるしかないので、必ず*の数が英小文字より多いとわかる。

Cは $S$ に含まれる数を昇順に並べたときどの数も一つ前の数の倍数であることが必要十分条件だから、サイズを最も大きくしようとしたら $l,2l,2^2l,\dots$ を入れるのがよい。つまり $2^kl\le r$ を満たす最大の $k$ について、答えの一つ目は $k+1$ とわかる。

この係数、つまり最大の要素を最小の要素で割ったときの値は、 $2^k$ に限らず素因数を重複を込めて $k$ 個持つ数であればなんでもよい。複数種類の素因数があれば並べ方も区別されることに注意。よって答えの二つ目は、ありうるすべての「最小の要素」 $s$ に対して $r/s$ 以下で使える係数それぞれの並べ方を足し上げると求まる。 $k\lt 20$ なのですべての $k$ に対して前計算ができて、商列挙で $O(\sqrt r)$ 。

以上のことを実装して実際通ったが、コンテスト後にもっと高速になることを知った。そもそも考えるべき係数は $2^k$ または $3\cdot 2^{k-1}$ しかない。それ以外だともっと大きな $2^{k+1}$ が使えるようになるからだ。よってこの二つをそれぞれ試せば答えが求まる。その値は十分小さいので、998244353で割ったあまりを求める必要すらない。

Dはいったんすべての値から $x$ を引いておいて、どこに $2x$ を足すか考える。 $x\ge 0$ なら選んだ区間に含まれるように、 $x\lt 0$ なら含まれないように選びたい。例えば前者のケースだと、長さ $k$ 以上の区間は累積和を見ながら計算し、長さ $k$ 未満の区間 $O(nk)$ 個は全探索すればよい。後者もほぼ同様。配列外参照で1WA。

Eは $r$ を決めれば下から順に子のうち一番同じ色の頂点数が少ないものと同じ色を塗っていくべきだから、これを全方位木dpにすればよい。1WAしたが根を変えてサンプルを試すと答えがずれていて、それを直したら通った。

うっかり答えを二分探索してしまい、木dp中に子をソートしているのも合わせて $\log$ が二つ付き1980msとギリギリだった。1回の全方位木dpで直接答えを求められるし、ソートを使った部分も値の小さいほうから2件を知りたいだけだから、全体で線形時間にすらなる。

Fは解けなかった。 $n$ の桁数と $b$ を全探索すると、 $n$ を $a$ が分母分子に現れる分数で表すことができる。 $n$ の桁数から $a$ の候補が絞れて、あとはその分数が本当に整数になるかチェックすればよいことになった。しかし分子だけならともかく分母にまで変数があってどうにも高速化できない。 $a$ の候補はかなり多く全探索もできなかった。

5完13位。Fはコンテスト中は0ACだった。Rubikunさんが終了直後に通していてすごい。埋め込みらしいがどこを埋め込めるのか分からない。

しばらくYouTubeを眺めた後日記を書いた。午前6時頃切り上げてラノベをしばらく読み、午前7時半就寝。

03/01(水)

午後2時過ぎに目を覚ました。眠気が残っているのだからすぐ二度寝に入ればいいものを、うっかりスマホを触ってしまい目が冴えて眠れなくなった。そのまま4時間ほどかけてカクヨムを1作読了。

kakuyomu.jp

「凡人転生の努力無双〜赤ちゃんの頃から努力してたらいつのまにか日本の未来を背負ってました〜」。設定は好みだしキャラ達の配置も良い。幼少期の時点で面白かったがやはり主人公の行動範囲が狭かったりするので、成長してからはもっと楽しみ。

布団から出て2月の読書記録をツイートした。意識的に本を読んでいた日も数日あったが、油断するとすぐスマホで楽に読めるネット小説にのめり込んでしまう。じゃあこれからは電子書籍を買えばいい、とはならない。自分の中では物理書籍を本棚に並べることが最優先されているからだ。それが既読か未読かというのは、そこまで重要な点ではない。

2月の集計
買った：26冊
読んだ：8冊
積読：+18冊
積読（累積）：+28冊
— こたつがめ (@kotatsugame_t) 2023年3月1日

TLで知った競プロキャンプに登録した。CFのレートが2200以上だと無料で参加できると書いてあった。チームを組んでいないが、登録時に何も聞かれなかったのでどうなっているか謎。ソロでも5h頑張るつもりとは言え、書いてある通りPetrozavodsk Campのミラーなら難しすぎて手も足も出ない恐れがある。

Hello Muscat 2023 - Codeforces

午後7時半ごろ外出。ドラッグストアに寄ったり油そばを食べたりした後ゲーセンで閉店まで遊んだ。今日は理論値三つに加え14+の「HERA」でSSSを出した。通常解禁されたばかりの新曲なので別に苦労はしていないが、縦連が思ったより押せなくてひたすら擦ったら首筋の筋肉を痛めてしまった。

スライダー清掃に真剣 pic.twitter.com/PbQaUhFq3o
— こたつがめ (@kotatsugame_t) 2023年3月1日

最後の方は15の「Trrricksters!!」を詰めていた。終盤ボロボロだったのがだんだん改善されてきた。家で少し座学してもう一回挑戦したら出そうだと考えている。

現在地 pic.twitter.com/ehvbpxSZEx
— こたつがめ (@kotatsugame_t) 2023年3月1日

平日ボーナスのデュエルクリティカル率UPの影響が大きかったようで、結構な回数クリティカルが出て15クレ程度しか遊んでいないのにチュウニズムデュエルが90万ダメージ進んだ。あと5クレもプレイすれば終わるだろう。今回は開催期間の終了直前に焦る必要がなさそうで良かった。

ドンキで菓子パンやカロリーメイトを買い込んで日付が変わったあとに帰宅。シャワーを浴びてからラノベをしばらく読んでいたが、眠気に耐えきれなくなって就寝。午前3時だった。

03/02(木)

午前8時過ぎに目を覚まし、昨日読み止しにしたラノベの残りを1時間ほどかけて読了。「世界で一番『可愛い』雨宮さん、二番目は俺。」。

そう言えばこんな話だったなあ、と思い出しながら読んでいた。やはり設定が好み。口絵になっているhikariがチャラ男をやり込めるシーンも良かった。今はなろうの更新が再開され、四章が進行している。まだ読んでいない。続刊してくれれば2巻に収録されるだろうから、せっかくなのでそちらを待ちたい。

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

別のラノベに手を出した。午後1時過ぎに「異能学園の最強は平穏に潜む」を読了。

「よう実」を彷彿とさせる学園の設定だったり、潜むと言いつつ1巻から大胆に動いていたりと大丈夫かと思ったが、かなり面白かった。そもそも後者については本当に潜まれると面白くならない。主人公が活躍するシーンが結構あって只者でないことは十分に伝わった。しかし何者であるかはまだ隠されていて、続きが楽しみである。

学食で昼食を摂った。カツカレー。3月に入り春休み期間でミールカードが使えないのに会計時に気づいた。1日あたりの金額を使い切ろうとしなくていいのなら、わざわざカレーにカツを乗せる必要はなかった。

ラノベを受け取ってからサークルメンバーと合流し、3時間ほどTUPCの準備をしていた。当日の飲み物としてお茶や水の500mLペットボトルを48本買い、段ボールに詰めてひいこら部室に運んでから名札を作成した。

午後5時帰宅。布団に倒れ込んですぐ寝たらしい。午後11時に目覚ましで起きて半からCF #855 div.3に出た。

Dashboard - Codeforces Round 855 (Div. 3) - Codeforces

Aは大文字小文字を揃えたあと連続する同じ文字を圧縮してから判定するのが書きやすい。Bは最初の段階で貪欲にペアを作ったあと、残った大文字2個または小文字2個のペアを一つ答えに含めるのに操作が1回必要になると考える。

C1は制約からなにかdpできるんだろうなと考えつつ、解けたとしても実装が面倒で時間を消費するだけだと思ったので最初からC2を解いた。まず全部のボーナスカードを山札に積んでシミュレートし、最後に何枚か余ったら、代わりにどれを捨てるのが最適か考える。

1枚捨てるとそれ以降の山札の枚数が一様にデクリメントされるから、それで枚数が負にならない範囲のカードを捨てることができる。つまり右からの累積MINが1以上の範囲から1枚、2以上の範囲からさらに1枚、……と選ぶことになるので、選べるカードを優先度付きキューに詰めて貪欲に取ればよい。

Dはギャグ。 $i$ 文字目から2文字取るのと $j$ 文字目から2文字取るので得られる文字列が一致しているとしてどこの文字が一致するか考えることで、重複チェックの際は $|i-j|=1$ のケースしか考えなくていいことがわかる。

E1は謎。 $k=3$ なので例えば左端の文字を経由して左から4文字目と5文字目がswapできる。最初はこのような隣接する文字のswapだけを考えていたがそんな必要はなく、swapできるペアをグラフにして連結成分を考えればよい。グラフはE2でも陽に構築できる。 $k=3$ の何が嬉しいのか分からなかった。

Fは文字列ごとに奇数回出現する文字種をbitで持つと文字列連結がXORで表現できる。このXORを26bit中25bitが立った数として26通り全探索すると、片方の文字列を固定したときにもう片方の文字列の候補が絞れる。この時点で条件の四つ目は満たされているので、あとは三つ目を判定すればよい。

25種類の文字が出現することは分かっているので、残る1文字が出現しない文字列だけ考えれば良いことになる。片方の文字列を固定してから出現しない文字を全部試すと候補のカウントがメモリ制限内で行えなかったが、逆にすれば良い。

Gは木のmirror imageなる謎の用語が出現しているが雰囲気で読める。mirrorを忘れ、単に根付き木として同型であると思ってよい。つまりある部分木がsymmetricalである条件は、その子を根とする部分木たちが同型なもののペアに分割できるか、あるいはsymmetricalな1個だけが余るということになる。根付き木の同型判定はAHUアルゴリズムで計算した。

1時間弱でノーペナ全完、open hacking phaseで上の方から数人落ちて12位。調子が良かったつもりだが順位は思ったより良くなかった。CとEで時間がかかっているらしい。Eはギャグにすぐ気づけなかったのが悪い。Cはなんと山札を優先度付きキューにしてシミュレートすれば答えが求まるようだ。

今日も動画を撮っていた。コンテスト中に非公開状態でアップロードし、チャプター分けまで済ませておいて、コンテスト終了後すぐに公開した。

www.youtube.com

午前9時まで日記を書いたあとTUPCのテスター作業をした。問題文・解説の校閲。いつかやろうと思っているうちに本番が明後日に迫っていた。改めて読み直し、いくつか気になる点を指摘。こんな直前になってしまい申し訳ないとは思っている。

午後1時就寝。

03/03(金)

午後8時起床。TUPCの校閲を続けていた。日付が変わる前になんとか一通り読み終えて指摘を送った。ほとんどはすぐに修正されたが一部は明日の朝に対応される予定。ただそうして残っているのは軽微なものだけなので、ほぼ問題ない状態に仕上がっているはず。その後入力に余計な文字、空白や改行が入っていないかをチェックした。

以上のことが午前1時前には完了し、それからSRM845に出た。

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

Easyは2パターンのcheckerboardのうちどちらが近いかを決め打つと、 $RC$ マスのうち食い違っている $D$ マスを選ぶごとに一つのbitmapが得られる。 $D\lt RC-D$ ならこうして得られたbitmapは重複せず、距離も確かに $D$ になっているから答えは $2\binom{RC}{D}$ 。 $D=RC-D$ ならどのbitmapも2回ずつ数えられるので $\binom{RC}{D}$ 。 $D\gt RC-D$ なら距離 $D$ でないので $0$ 通りとなる。

Medはつまらない問題。値とインデックスのペアでソートしておくと、タイプ0のフェーズでは左端の、タイプ1では右端の要素を取り出して端に寄せることになる。もともとどこにあったかがわかり、そこから左あるいは右に残っている要素数がswap回数となって、BITで更新・取得が行える。こんな問題は読解が終了した瞬間に解けているはずなのに、SRM特有の入出力に余計な手間をかけさせられて腹が立つ。

Hardは解けなかった。約数だのなんだのとややこしく見えて、結局素因数の個数を見てニムをしているのと変わらないから、normal playについてはいつものXORで判定可能。値から個数への変換も区間篩で前計算できる。しかしmisere playがわからなかった。負けの状態のXORが1だからそれで判定できると思ったが全然ダメだった。

コーディングフェーズ終了間際にメモ化再帰で答えるコードを提出したが、当然間に合うわけはない。しかしチャレンジフェーズでは落とされなかった。終了直後のチャット欄で、自分のHardを落とそうとしたらエラーが出たと言われていた。再帰が深すぎるとかメモが多すぎるとかでジャッジごと変な落ち方をしたのだろうか。謎である。

ちゃんとシステスで落ちて17位、2897→2830(-67)。Hardは「misere nim」とまんまの単語で検索したら日本語の記事が出てきて愕然。こんな問題にほぼ自明なEとMをくっつけてdiv.1にするのは正気を疑う。いやもうSRMに問題の質は一切期待していないけれども。

Game Theory (HackerRank) : Misère Nim - 4bitにっき

さらなるTUPCのテスター作業としてRubyで数問解いてみた。当然ながら特に問題はなさそう。数問で切り上げ、シャワーを浴びて少し日記を書き午前6時就寝。

03/04(土)

午前9時前に目を覚ました。スマホを触らないようにして二度寝を試みたが、どうにも目が冴えている。しばらく転がっていても意識がはっきりしていくばかりだったので、結局は諦めてスマホを触っていた。

午前10時半くらいになってようやく布団から脱出。準備してコンビニで朝ご飯を買いつつ大学に向かった。今日はいよいよTUPC本番である。ここから解散するまでのことは参加記に書く。

ここにリンクを貼る

午後8時過ぎに解散してコンビニで食べ物を買い込み帰宅。買ってきたおにぎりを食べて録画の準備をし、午後9時からABC292に出た。

AtCoder Beginner Contest 292 - AtCoder

Aは問題名から内容がエスパーできたので、開いて一瞬確認したら即座にVimのコードを書いて提出。ジャッジ待ちの間に制約を読んで大文字が入力されないことを確認した。無事AC。僅差でFAだった。

Bは単にカウントするだけ。レッドカードをイエローカード2枚分として処理した。Cは $1\dots N$ の各整数を2数の積に分解する方法を全体 $O(N\log N)$ で数え、組み合わせた。DはUF。

Eは $x$ から $y$ へのパスがあるなら $\rightarrow y$ の有向辺も存在しなければならない。そのような $(x,y)$ を数え、最初からある辺の分 $M$ を引いた。

Fは二分探索。判定は正三角形の一つの頂点を長方形の角に固定し、長さ $B$ の辺からどれだけ傾いているかのパラメータ $\theta\in[0,\pi/6]$ を考えて行った。

一辺の長さを $x$ とすると $x\cos\theta\le B$ かつ $x\cos(\pi/6-\theta)\le A$ が条件。前者をギリギリ満たす $\theta=\arccos(\min(B/r,1))$ を取って、値の範囲と後者をチェックすればよい。サンプルが弱くて怖かったが一発で通った。

Gはdp。 $i$ 桁目以降だけ見たとき $S_l\lt\dots\lt S_{r-1}$ となるような?の決め方を数え上げる。 $i$ 桁目を決めて、そこで大小関係が確定しなかった区間を $i+1$ 桁目以降に関するdpから取得する。

$i$ 桁目の決め方については別にdpを行った。どの数字がどの区間で使われるかという遷移になって、 $O(\sigma(r-l)^2)$ で計算できる。ここで $\sigma=10$ は数字の種類数である。全体 $O(\sigma N^4M)$ だが定数倍がかなり軽い。

Exはパフォーマンスから $B$ 引いた値の累積和が最初に0以上になるタイミングが求まればよい。累積和の累積MAXはセグ木で管理できるので、その上で二分探索する。単に累積和だけ管理していて1WA、0より大になるタイミングを求めていてさらに1WA。後者についてはサンプルすら合っていないことに2ペナ出すまで気付かなかった。

43分半と2ペナで全完、11位。Exのしょうもないミスが残念。振り返りをしてもなおコンテスト時間が余ったので、録画を続けたままTUPCに関しても話していた。撮り終えてすぐ投稿。

www.youtube.com

コードゴルフ。AはやはりVim。BはAWK。CもAWKでこちらは負け。FはRubyで二分探索していたが、答えを直接求めるコードにボロ負け。他は手付かず。

今日は午前3時からUniversal Cupに参加する予定。すでに眠いため、日付が変わったくらいに布団に倒れこんで仮眠に入った。

午前2時過ぎに目を覚ました。非常に眠い。時間的にはあと30分ほど眠っていられるが、そうやってギリギリを攻めるともしかしたら寝過ごしてしまうかもしれないほどの眠気だったため、そのまま起きていることにした。時間をかけてじっくり布団から這い出しUniversal Cup 6回目。今日はTaiwanセットだった。

2022-2023 ICPC Asia Pacific - Taoyuan Regional Contest - Dashboard - Contest - QOJ.ac

チームでMAGCBDJIFHLを解き、11完13位。自分はABJFLを担当した。質の悪いセットだと感じたが順位が良かったのでそこまで嫌いにはなれない。

最初、順位表に従ってMAGCがポンポンと通された。MとCがぷらさん、Gがかっつさん。この4問は明確に簡単枠だった。自分が担当したAはそれに加え不快な要素もあった。コドンからアミノ酸への対応表が問題文に与えられているので、それに従って入力のRNAを翻訳せよという問題。場合分けのコードをプログラムで生成した。

次にBを通した。ladder部分は簡単で、四角形のグラフで下の2頂点が彩色されている場合に上の2頂点を彩色する方法が $(\lambda-2)^2+(\lambda-1)$ 通りあるので、これを $(n-1)\cdot k$ 乗すればよい。

真ん中の $k$ 角形の部分は、ある固定した頂点に色1を塗るとして、そこからぐるっと一周しつつ「色1を塗る場合の数」「色1以外を塗る場合の数」を計算し、最初固定した頂点に戻ってきたときの前者の値を $\lambda$ 倍すると求まる。一周する部分は連立漸化式になるが、解くのが面倒だったので行列累乗で計算した。

次にDが通されていたのでぷらさんと一緒に読んでいたのだが、まったく問題が理解できなかった。問題文では図を含め丸々2ページに渡って暗号通貨の説明がされているようで、どこが問題になっているのかが把握できない。そのうちぷらさんに「自分がこれをやるので別の問題に進んでください」と言われたので、ありがたく押し付けることにした。自分が離れてからしばらくしてついに読解に成功したらしく、解法自体はやるだけですぐ通っていた。

自分はJに進んでDの後に通した。切り開いたサイクルとパスをそれぞれ別で管理し、辺の使用可不可をセグ木で、コストを累積和で取得した。最短距離を求めるクエリでは指定された頂点がサイクルの上にあるか辺の上にあるか考え、各パターンでどのような経路が最短になり得るかを列挙してそれぞれ長さを求めた。列挙が足りているか心配だったが一発で通って安堵。

かっつさんによってIが通されるのを眺めつつFを考えていた。両端はとりあえず1が確定する。その両端からそれぞれ確定している範囲でオイラーツアーを辿ることで、根から現在いる頂点までのパスを管理することができる。確定している範囲を全部見終えたとき、その二つのパスは根からある位置までは一致しているはずで、その間を繋ぐ未確定の部分では、左から作ったパスに沿って一致している一番下の頂点まで登った後、右から作ったパスに沿って降りていくことになる。

そのような登って降りての間にこれまでに使っていない頂点たちを子としてくっつけると全体のオイラーツアーとなる。ここは貪欲にやればよい。子として頂点番号が最小のものをくっつけるか、一つ上ったり右から作ったパスに沿って降りたりするという二通りしかないので、辞書順最小になるように選ぶ。特に後者について丁寧に考えながら実装したら一発で通った。

Hはランダムに生成された点列のすべての連続部分列に対してそれぞれ最小包含円を求める必要があるらしい。検索すると $n$ 点の最小包含円を求めるのが $O(n)$ になるようだ。ランダムな順で点を追加して、これまでの最小包含円に入らなければ更新するというもの。今は点自体がランダムなので追加を順番に行うだけでよく、連続部分列の始点を決めるごとに $O(n)$ ですべての終点に対する答えが求まる。

最小包含円 | libalgo

この段階で解けたと勘違いし自分はLに移ったが、まだ解けていなかったようだ。その後ぷらさんにより無事通された。Lは特殊なプログラミング言語のコードを書くタイプの問題で、そういうものが大好物な自分としては存在を知ったときから気になっていた。しかし読んでみるとほとんどBrainfuckで拍子抜け。メモリが-1から9までの値しか取らないことと、実行を停止する命令が追加されていることが変更点。

問題は、 $k=1\dots 6$ が入力で与えられるので、非負整数を読み込んでそれが $k$ の倍数かどうか判定するプログラムを出力せよというもの。読み込むというのは十進表現を1桁ずつだから、0から9の数に対して適当な操作、例えば $\bmod 3$ だったりができればほぼ十分。そしてそういうコードをBrainfuckで書いたことがある。

条件分岐がwhileしかないのでそれを使う。例えば数xが0から3の範囲にあるとして、0で初期化されたansに $\bmod 3$ した値を代入するコードは次のように書ける。

while(x){x--;ans++;while(x){x--;ans++;while(x){x--;ans-=2;}}}

3重のこのコードを9重にすれば9まで対応できる。同様の方法でいろいろな条件分岐を実現し、 $k$ の値に応じて6通りのコードを手作業で作成した。デバッグ機能付きのチェッカーが配布されていたのでかなりスムーズに正しく動作するようになって、提出したら通った。

後からよく問題文を確認するとサンプルに $k=1,2,3,6$ の場合の答えがあって愕然。こういう問題のサンプルは実際には使えないプログラムになっていることが多く、はなから当てにしていなかった。

1時間20分残して残りはEとK問題。EはTL 30secだしかなり大変そうなフローの雰囲気があった。一方Kはグラフに言い換えると考えやすそうな形になったので、そちらに注力した。ぷらさんは自分と一緒にKに、かっつさんはEに取り組んだ。

Kは連結成分ごとに解いてよい。辺を偶数本持つならtype Aだけで取り尽くせると分かった。この時の証明は正しくなかったが、結論自体はEven Degreesを考えると正しい。さらにtype Bまたはtype Cは使うならどちらか片方を一つだけということも分かっていた。なのでグラフからtype Bまたはtype Cの辺を一組取り除いた後の各連結成分が辺を偶数本持つか判定できれば良いことになって、できなかった。Eも実装に移れるほどの進展はなかったようでそのまま終了。

感想戦。最初4問はどれも本当にしょうもない問題ばかりだったが、しょうもないだけまだマシ。自分が読解を諦めたDは、頂点に重みがある出次数高々2のDAGが与えられて、全頂点に対し自分に到達可能な頂点の重みの和を求める問題だったらしい。愚直が通る。問題を解くのに関係ない説明がひたすら続いていた問題文が最悪だった。元ネタが暗号通貨だからと言ってそれについて説明する必要はない。

Iは二部マッチングで、怪しげな制約から辺の本数が十分少なかったらしい。問題文や図がいかついのでやってもらえて助かる。

Hは点列を連続部分列 $K$ 個に分割し、それぞれの最小包含円の半径を求めて総和を最小化する問題だった。半径が全部求まっても、分割する部分が普通にdpすると $O(N^2K)$ なのでまだ解けていなかったということ。結局枝刈りしたら爆速だったらしい。

TLの言及で、最小包含円の半径が同じならそのうち極大なものだけで遷移するとよいと知った。自分で実装してみたら、ユークリッド距離を真面目に計算したせいで距離の比較で毎回sqrtを使うことになり、全然高速にならず苦労した。2乗の状態で持っておくと一気に爆速になってびっくり。自分の幾何ライブラリで距離を比較している部分も、EPS周りが少し怖いがそう書き直しておくべきかもしれない。

水曜日にレジったキャンプ「Hello Muscat 2023」だがコンテスト中にメールが届いていて、これからチームを組めるようだ。せっかくなので今Universal Cupに出ているこのチームで組もうと誘った。全員OKだったのでひとまず各自での登録をお願いし、解散。

キャンプに本格的に参加することになったので期間中の予定を確認。日本時間で午後3時から午後8時までがコンテスト時間らしい。インターン先の定例会は欠席させてもらうことにした。セミナーはたまたま休みだった。1on1は予定をずらしてもらった。

それからずっと日記を書いていた。午後5時就寝。

03/05(日)

消えた。