05/31 (MON)
9:15 起床。まあまあ睡眠の質は良かった。 なんかAtCoder黄色になった夢をみた。いや、来週どうせなれるから夢に見る必要がないと思うのだが(フラグ)。
大学に向かいつつ、今日の典型を確認する。
https://atcoder.jp/contests/typical90/tasks/typical90_bb
問題概要。$ N $ 人の研究者がいる。$ M $ 個の共著論文がある。$ i $ 番目の共著論文には、$ K_i $ 人が携わっていてそれぞれの人の番号が与えられる。 研究者 $ 1 $ から共著したグループ内の移動を $ +1 $ としてそれぞれの研究者について、何回の移動で到達できるかを求めよ。研究者から $ 1 $ から到達不可能ならそれを報告せよ。
見た目どう見ても BFS である。そのままナイーブにグラフを作成するとグラフのサイズが $ O(N^{2}) $ になる。 陽にグラフを構成しなければ、グループごとに訪問フラグを持ってやって BFS をそのまま実行することができる気がする。
ただ、典型ではこういうある集合内で縦横無尽に辺を貼る問題の辺の数を減らすテクニックがある。 グループの代表のノードを作ってやる。そうすることによって代表のノードに移動する際に $ +1 $ のコストを払って、 逆に代表のノードから各要素のノードに移動にはノーコストで移動できるとすることで辺の数を減らして等価な計算ができる。 こうすると、01DFS になるが、$ 0.5 $ ずつコストを分割すれば BFS をそのまま使うことができそうだ。
代表のノードを考えると、二部グラフのように考えることができる場合も多く一考の余地あるテクニックな気がする。
大学に着く。作業をし始めるも、今日は溜めに溜めた TA の採点作業をしなければならない。
教授からも、はやく採点しろやというメールが来てしまう。本当に申し訳なさしかない。
そんなこんなでこの日は採点をメインにやっていた。Java でオブジェクト指向言語を入門するみたいな講義内容のため、難しくはない。
学部生の解答が zip で与えられるため、このダウンロードがボトルネックになってしまう。
なぜなら、ここは手動でやる必要があるからだ。正しくは、認証を真面目にやれば自動化できるのだろうが流石に労力に自動化のメリットが見合っていなさすぎる。
採点をマッハで終わらすために、実は事前に zip を指定の名前のフォルダに unzip して中の java ファイルを全て javac かけて score.txt と言うファイルを作成した上で、vim で java ファイルと score.txt を開く、というスクリプトを作っておき、また採点で見るべき箇所もチェック済みであった。
というわけで、採点に励んでいた。というか家に採点用に整備した PC を忘れてきたので早めに帰宅して採点をしていた。 よって、競技プログラミングもやっていないし、買ったジャンプも放置していた。
先週の週記の最後で述べたコドフォのコンテストへの煽り気味お気持ち表明が -7 になっていた。まあ煽ったのだからそうなるだろうという気持ちになりつつ、ちょっと下の Red Coder の煽りコメントがそこそこ Upvote されていて、ratism を感じるなどしていた。
まあなぜわざわざお気持ち表明したかというと、自分は次の日の朝を犠牲にしてまで深夜コンテストに出て writer の定義を信じたのに裏切られて不快感を得たのに、writer が不快感を得ないのは不公平だと思って不快感を与えようと思ったとかいう小学生的で幼稚な理由である(もちろんちょっとは unrated にも期待していた)。 ちょっと申し訳ないことをしたかなとも思ったけど、writer は全く悪いと思っていなくて「たくさんの tester が見ても nested list の定義には何の疑問もなかったぜ」みたいな居直りをしていたので、やっぱ不快感を与えて正解だと思いなおした。フレーバー要素に定義の本質を置いていいんだったらもういっそ形式的な定義は一切書かないでコンテスト開いてくれよ、きっと称賛されるよ。 またイライラしてきてしまったので今日でこのことを考えるのはもうやめるぜ。
そんなことで特にブログにかけるような活動をせずに一日を終えた。
06/01 (TUE)
6 月になった。11:30 起床。遅すぎる。朝食を食べながら、今日の典型を確認する。
https://atcoder.jp/contests/typical90/tasks/typical90_bc
$ N $ 個の整数が与えられる。このうち $ 5 $ 個を選んで積を取ったときに、$ P $ で割った余りが $ Q $ になるような選び方は何通りあるかを求めよ、と言う問題。
DP をすると、状態が多いな～とか一瞬思ったがそもそも $ N \leq 100 $ なので $ \binom{100}{5} = 75,287,520 $ なので全探索が可能である。まあ★2 だしな。
そうこうしているうちに昼飯の時間になる。 とはいえ、今日は家に人が全然いないため、残り物を食すという感じだ。
昼から後は、基本的に作業をしていたり、ピアノを弾いていたりした。 実家ぐらしだと、逆に一人の時間がかなり貴重だったりする。 貴重な時間はあっと言う間に去り、夕食の時間になる。
驚くべきことに全然競技プログラミングもやってないし、ジャンプも読んでいない。 仕方ないので、今練習している曲の適当な人の演奏の YouTube のリンクでも貼っておくか。
改めて上から見せられると、右手のカバー範囲がところどころぶっ壊れてないか？ 音楽ゲームでこんな譜面を収録したらきっと怒られるに違いない。
夕食は外出して、サイゼリヤに行った。ラストオーダーの 10 分前らしい。駆け込みでごめんさない。 マルゲリータピザ、ペペロンチーノ、ポテト、イタリアンプリンという自分の中の鉄板メニューを頼んだ。 個人的にサイゼリヤのイタリアンプリンクッソ美味いと思うんだけど、あまり共感が得られない。
帰り際にゲーセンに少し寄ることになったが、ボルテのメンテがカスすぎて一気に萎えてすぐに帰宅。 帰宅して、今日の典型を通すことにした。
全探索ができると既に述べたが、多分典型の想定では DFS を使って全探索をするのではないかと疑っている。 なぜなら、わざわざ $ 5 $ というループをネストさせるにはデカい数字を選んだということは「$ n $ 重ループは DFS」みたいな典型を言いたいんではないかと考えた。というわけでいつも通り DFS で全探索を書いた。AC。1 sec ぐらいかかっている。 マクロを使えば $ 5 $ 重ループわけないと思ったため書きなおして、最適化を #pragma で指定したら 659ms になった。
昨日の典型もまだ書いていないので通す。 辺の本数を少なくして BFS や 01BFS をする解法は実装がいつも通りで楽。 それぞれの研究者が関わっている共著リストと、それぞれの共著に含まれる研究者リストをそれぞれ持っておくことによってグラフを陽に持たずにそのまま BFS をすることもできるぜ！と思うけど、コンテスト中はこの解法を採用することはなさそう。
E - White Pawn の実装方針がかなり悪かったので再考する。
コンテスト中は、$ Y $ 方向に圧縮（必要な区間のみを vector に載せる）した上で in-place DP をやって通した。しかしこれではあまりにも事前処理とか offset とか面倒臭すぎて時間がかかりすぎる。なんとかならないか。よくよく考えると $ Y $ 方向に実際に圧縮する必要はないんじゃないかと思った。黒のポーンの隣接する $ Y $ 座標に既に到達可能かどうかが判別できればいいので、std::set を使えば煩わしい処理から解放されそうだ。大分楽になった気がする。明示的な圧縮は往々にしてクソめんどくさいため、std::set や std::map でしなくてよくなりそうなら、しない方がよさそうだな…
F - Weed を解けたと言いながら通してなかったので心配になりやることにした。 勘違いが解けたところから書く。勘違いがとけると、青木君が残す部分は全然区間になっていないことがわかる。 特に強い制約のない歯抜けの選択最適化なので貪欲は厳しいなと思い DP に思いを馳せる。 高橋君の操作は残った集合の最大値の半分を超える要素を削除するため、大きさでソートをしておく。 最初は $ dp[i][j] \cdots $ 昇順 $ i $ 番目の数字まで見て、$ j $ 個の数字を青木君が削除したときの高橋君の操作回数、という DP を考える。ある数字を青木君が削除するかどうかで遷移をしていくのだが、削除しない場合その数字を $ X $ として $ 2X $ 未満の数字までは削除しないようにするのが明らかに最適。これらを削除しなくても高橋君の操作回数は減らないし青木君の操作回数は減らせるためである。 しかし、このアルゴリズムでは明らかに $ O(N^{2}) $ かかってしまっている。よく考えると $ X $ 以上 $ 2X $ 未満を残すと高橋君の操作回数が $ 1 $ 増えるので、高橋君の操作回数は最大でも $ O(\log{A _ {max}}) $ である。よって DP の値と $ j $ を入れ替えることで $ O(N \log{A _ {max}}) $ になり、解けた。AC。
DP table の値と状態の一要素を入れ替えて状態数を落とすのはナップザック問題の変種にもあったなあと思ったりした。勘違いしなければ、なんてことはない問題だったので割と反省している…
眠いので今日はこのへんで寝る。
06/02 (WED)
10:50 起床。目覚ましをかけ忘れた。 朝食のカステラをほおばりながら、今日の典型を確認する。
https://atcoder.jp/contests/typical90/tasks/typical90_bd
問題概要。$ N $ 日間福袋が販売されている。$ i $ 日目の福袋は $ A_i $ 円のものと $ B_i $ 円のものの二種類ある。各日付についてどちらかを買わなければならない。この時 $ N $ 日間で購入した福袋の合計額が $ S $ 円になるような買い方が存在する場合は買い方を、存在しない場合は Impossible と出力せよ。
$ S \leq 10^{5} $ で $ N \leq 100 $ を確認して $ O(NS) $ のナップザック DP をすれば良いことが明らか。復元もいつも通りやる。現代人、ナップザックは全員履修しているため実際にこれが ABC-E で出題されたらかなり簡単な部類だと思う。
今日はピアノなので手ならしも兼ねて練習をする。幸いにも家に一人である。 しかし今日は暑い。ピアノを照らすライトは白熱灯なのでもう気が狂うほど暑いんじゃ。
昼飯はマックに食べに行った。チーズキチガイなのでダブルチーズバーガーのセット(ポテト L)と、シャカシャカチキン(チェダーチーズ)を購入した。モバイルオーダーをつかったためスマホ以外手ぶらで食べに行けるのが嬉しい。あと、単純に早めに注文すれば待ち時間が存在しなくなるのもモバイルオーダーは優れていると思う。心なしか並んでいる人より優越感に浸れる（？）。
マックから帰ってきてピアノを続行。そしてピアノ教室に足を運び、あまりの下手くそさに沈没して帰ってくる。
この時点で典型のジャッジが追加されているので書く。
今まで DP の復元は全て、prev という配列を用意して手前の状態を保存しておくという手段を脳死で取っていた。
もちろんパターン化と言う意味ではこれが一番いいのかもしれないが、遷移の種類を考えた上で良い情報の持ち方を選ぶのも大切に最近思えてきた。
今回の場合、$ A $ と $ B $ でどっちを選んで遷移してきたかを配列に保存しておいた。結果から逆算して選択を求めるのはしばしば面倒なので、このように選択したものを保存しておけるのであればそうすると復元が楽かもしれない。選択から元の状態を計算するのか、元の状態から選択を計算するのかどっちが楽かという問題な気がしてきた。AC。
今日 TCO Round2B があったような気がしたので Arena を開くと will start in 2 hours 41 minutes. って書いてあってクソ焦る。
完全に夜中だと思い込んでいた。
ウォーミングアップを兼ねて、令和の ABC を $ 2 $ 個程復習した。
TCO Round2B が始まる。
Easy: 前回の TCO Round2A の Easy は 5000 文字を超える凄絶な問題文だったが今回は逆にめちゃくちゃ短くてびっくりした。 桁を見た時に交互に偶奇が配置されているような数字を昇順に並べた数列の $ K $ 番目の数字を答えよ、という問題。 こういう問題は $ n $ 桁の場合の数や、左から決めた時の場合の数が高速にわかる場合は貪欲でできることが知られる。偶奇が交互に来るので一番大きな桁が一旦決まってしまえば、そこからは $ 1 $ 桁につき $ 5 $ 通りずつ存在する。桁数を決めた後、左から決めていく。$ 1 $ 桁目は 1-indexed で $ 2 $ 桁目以降は 奇数/偶数の index であることに注意。実装が下手すぎて参っていた。実装でワタつくぐらいなら桁 DP の二分探索でも良かったな。
Med: ロボットが $ N $ 台あって，$ 1 \leq M < 10^{6} $ の番号づけされたタスクが与えられる。同じ番号のタスクが割り当てられているロボットが $ K $ 連続で存在する箇所がどこかであるようにするために、いくつかのロボットを事前に除去する。最低幾つのロボットを除去すれば良いか、という問題。最初は見た目から全探索ベースで DP を考えた。naive にやると爆発。高速化を考えると、同じ番号のタスクが割り当てられている中で $ K - 1 $ 個先のロボットを前計算しておけば高速な DP ができるなと思った。しかし冷静にほぼ前計算で答えが出るので全てのタスクについて答えを求めて min をとる。
Hard: 分数の分母が与えられ、分子分母に共通する桁を順次消していくという操作を繰り返して最初と同じ値になるような分数を発見して分子を答えよ、という問題。まず分子になる数字は分母の約数しかない(約分できないといけない)。制約が $ D < 10^{7} $ なので約数の個数は $ 500 $ にも満たない。元の分母 $ D $ 分子 $ N $ がわかっているので、分母のうちどれを残すかを bit 全探索する。その後分子についてもどれを残すか bit 探索して削除した数字の分布が同じで分数の値が元と同じなら答えとなる。分母と同じ数だけ桁を削除するので定数倍改善が可能。高速化をしなくてもかなり厳し目に評価して $ 448 \times 2^{14} \times 7 = 51,380,224 $ なので耐えてる気がするが、定数倍改善をすれば $ 2 $ 倍以上早くなるはずなので心の余裕が生まれそう。実装が間に合わず落とした。けど人類が落としまくっていたので耐え。
レーティングが 1499 になった。草。TopCoder 適当すぎて黄色にすらなれてないの悲しいので次回なろうね。
06/03(THU)
8:30 起床。スマホを充電器につないで寝なかったためアラームが鳴らず寝坊。仕方がないので今週は家から一限を受けることにした。 とりあえず今日の典型を確認する。★6 だ。
https://atcoder.jp/contests/typical90/tasks/typical90_be
問題概要。$ M $ 枚のパネルがあって、最初は全て裏面を向いている。$ N $ 個のスイッチがあり、それぞれを押すことによっては対応するパネルの集合をひっくり返すことができる。 パネルの状態が一つ与えられるので、スイッチはそれぞれ高々 $ 1 $ 回推すことができる時そのパネル状態を作るようなボタンの押し方は何通りあるか。$ \bmod 998244353 $ で答えよ。
一目見て簡単ではないし、自分が苦手そうな雰囲気を感じたので一旦忘れることにした。 というか 9:00 から講義なので、普通に見た瞬間わからなかったら考える時間なかった。
というわけで講義を受ける。ふむふむ。講義内容に関しては触れることがないぜ。 言えることがあるとすれば、Microsoft Azure をオモチャとして使う課題がある。 大学 1, 2 年ならこの程度の事で喜んじゃうだろうが、もうだいぶ大学に慣れてしまって別にと言う感じになっている。 いや、修士 1 年だしはしゃいだ方がいいかもしれない。
講義が終わると作業をする。今週は結構作業をしている気がする。
というのも一番気が狂いそうだったパートはなんか解決したっぽくてやる気が出てきたというのがある。
今日の MTG では教授に「久々に〇〇くんが明るい声で安心した」と笑われた。草。
自分は外側から見ると相当分かり易い人間らしく、ちょっと恥ずかしい。
ともあれ、作業が楽しいフェーズに入っている気がする。この調子で話がまとまってくれると嬉しいな。
C++ のコードを C で書き直すとかいう拷問をやっていた時はどうなるかと思った。
しばらく元気に作業をしたり、やるべきことを処理したりしていた。 気が付いたら 18:00 を普通に回っていた気がする。かねこさんがボルテ配信をしているので覗くことにした。 上手すぎて作業をちまちまやりながら左側に配信を表示していた。この時間本当に作業が進んでいなかったりする。
去年一年間リモートのマシンに接続するとき毎回パスワードを手入力していたんだけど、このままでは後輩に ssh key を生成して鍵で認証するようにしよう！と言えないので仕方なく公開鍵をマシンにぶち込んだ。 目先のことしか考えられないゴミ野郎なのでわかっていてもこういう設定を後回しにするんだけど、やめた方がいいな。
そんなこんなで夕食の時間になる。美味しい。オムライスを作ってもらえた。オムライスってなんであんなに美味しいの？
食後は Twitter 閲覧、YouTube 閲覧に力を入れていた。この時間が多分一日の中で一番生産性がない。 適当に閲覧している自分でも結構な時間を使ってしまうので、好きな YouTuber や VTuber とか追っている人って相当時間使ってそうだしすげえなあと思ったりした。
気が付いたら 11:00 を過ぎていた。競技プログラミングをやっておこうということになる。 A - AtCoder Jumper を開く。セグ木みたいな形を考える。ウンウンうなっても全然条件を満たせないことに気づく。解けない。完全に参った。青 diff に対して解説を見るのも悔しいので見ないで放置を決める。
そういえば、放置と言えば今日の典型を考えていなかったのでやるか。線形代数みたいだな。 01 ベクトルが $ N $ 本あって、その span みたいなことに思いを馳せる。とりあえず、$ N $ 本の張る span 内に目的の 01 ベクトルがなければ答えは自明に $ 0 $ だと思う。いや span って言っていいのか？xor 結合で張られる空間を何と呼べばいいんだ？代数学など何もわからないのでこのまま線形代数と同じように考えて進める。一次独立なベクトルが張る span に目的のベクトルが含まれる時、構成は明らかに一意（線形独立性から一次結合が一意なのはすぐわかる）。$ N $ 本中で、一次独立なベクトルの最大本数を $ L $ 本として、この $ L $ 本が張る span は全体の span と当然同じ。$ N - L $ 本のベクトルはこの span 内にあり、$ 2^{N - L} $ 通りの一次結合も当然すべて span 内にある。よってそれぞれに対して一意な構成が存在する。したがって答えは不可能なら $ 0 $ 、可能なら $ 2^{N - L} $ となる。
実装は一次独立なベクトル集合を管理するんだけど、制約が微妙に大きくてベクトルを整数で表現できなくて面倒くさい。 普通に掃き出しをすることを考えると $ O(NM^{2}) $ かかる。まあ、間に合うやろ。AC。33ms。最適化されてないかこれってぐらい速い。
64 ビット整数を $ 5 $ つつなげていつもの高速かつ簡素な xor 掃き出しをやってみる。
xor の掃き出しすごい簡単に出来るんですね
— 熨斗袋 (@noshi91) November 30, 2019
vector<int> basis;
for(int e : a){
for(int b : basis)
chmin(e, e ^ b);
if(e)
basis.push_back(e);
}
これで数列 a の基底が basis に入る
有り体に言うとこれをして楽をしたい。
TODO ←こう書きつつ結局今週書かなかったな。来週チョロ書きします。
06/04 (FRI)
9:00 起床。眠い。ダラダラしながら、昨日大学に行かなかったので今日は行くことにした。
行きの電車の中で今日の典型を確認する。★4 か。
問題概要。$ 5 $ 桁の数を表示できる電卓があり、ボタンを押すと表示されている数字を $ X $ として桁和を $ Y $ とすると、$ X+Y $ を $ 10^{5} $ で割った余りの数に変化する。 最初に表示されている数字が与えられるので、ボタンを $ K $ 回押した後の数字を求めよ。
一番最初、朝と言うこともあり繰り上がりがあるから行列階乗は難しいな〜とかほざいていた。 冷静になると、functional graph で頂点数も $ 10^{5} $ なのでいつものサイクルゲーをやるかダブリングをやるかである。 サイクルゲーでやると実装は面倒だが、$ \log $ がつかないぐらいかな。
完全に余談だがこの手のダブリングをする時毎回適当に in-place にやろうとしてめんどくさくなってる。 更新待ち queue を持たないと完全に in-place にはできない。けどまあ queue を使って更新をするのまあまあ好きな実装。
大学について作業を開始するも、とんでもない失態を犯していたことに気が付く。 あまりにもとんでもない失態なのでとてもじゃないが書けない。複数人に迷惑をかけたので申し訳なかった…
金曜日は Java の講義の TA をしている。と言っても最近は全然質問が来なくて作業をしていることが多い。 Java の講義の前にもしかしたら典型のジャッジが来ているかも知れないと思い確認したら来ていたので投げる。AC。
TA 開始。今日は質問が来てビックリした。TA のあとはゼミがある。 失態を犯してしょんぼりしていたので、ゼミが終わったらおとなしく帰ることにした…つもりなのだが、楽しい気分になるためにゲーセンへ行く。
翌日に久々に同期と一緒に音ゲーをすることになっていたので前日のウォーミングアップぐらいのつもりだったが、かなりうまかった。
そんなこんなで帰宅。音ゲーを毎日やらなくなってから音ゲーをすると疲れてしょうがない。 今日は Codeforces のコンテストがあったことを思い出す。家に帰って夕飯を食べてから体力回復のためにダラダラしていた。 開始直前は眠かったが、ガムを噛んで誤魔化した。
Dashboard - Educational Codeforces Round 110 (Rated for Div. 2) - Codeforces
A 問題。$ 4 $ 人でトーナメントをする。寂しいな。しかし一回戦で勝ち上がった $ 2 $ 人は $ 4 $ 人の中で強い方の半分でないと fair でない。トーナメントの組み合わせが与えられるため、fair かどうか判別せよ、という問題。意外と面倒臭い。勝ち上がった $ 2 $ 人と上から $ 2 $ 人をそれぞれ求めて一致するかチェックした。
B 問題。長さ $ N $ の数列 $ a $ が与えられる。$ \gcd({a_i, 2a_j}) > 0 \quad (i<j) $ のような組の数が最大になるように並び替えたときのその数を答えよ、という問題。$ a_i $ が偶数であれば $ j $ はなんでもよく、奇数同士偶数同士の組の数は順序に依存しないため偶数を左に持ってくれば OK。数え上げを丁寧にやらなくても $ O(N^{2}) $ が間に合うためこれで書いた。ちゃんと正当性を確認してから投げたので、早解き的には出遅れていた感はあるが個人的にはいい感じだった。
C 問題。$ 0 $ $ 1 $ ? からなる文字列が与えられる。? をうまく決めたときに $ 010101 \cdots $ か $ 101010 \cdots $ になるような文字列を beautiful と呼ぶ。beautiful な連続する部分文字列はいくつあるか、という問題。まず ? のみの文字列は beautiful だと思った。というか$ 1 $ つでも ? 以外の文字があれば上記のどっちのパターンを目標にするかが決まるな。 $ 1 $ が奇数 index にあるのと $ 0 $ が偶数 index にあるのは論理的な矛盾を起こさない。また index の偶奇を入れ替えた条件も矛盾がない。それ以外の共存パターンは不可能なのでこの条件を活かしつつ尺取りをすれば $ O(|S|) $ で解けそうだ。問題があって自分は尺取りがすごく苦手だ。案の定すごい時間をかけて通した。
D 問題。$ 2^{K} $ の人数が参加するトーナメントがある。$ 2^{K} - 1 $ 回の試合に関して、$ 0 $ $ 1 $ ? が与えられる。それぞれ、選手番号が小さい方が勝つ、大きい方が勝つ、どっちが勝つかわからない、という情報を与える。$ Q $ 個のクエリが与えられて、この情報が $ 1 $ つずつ変更される。それぞれの変更の後に優勝する可能性のある選手の数を答えよ、という問題。単純に考えると、トーナメントをシミュレーションしていけばいいが間に合わない。よく考えると、トーナメントは完全二分木の構造をしており、それぞれのノードがそこまで勝ち上がってくる可能性のある選手の数と考えると、一か所の情報が変わった時影響を受けるのはその祖先のノードだけである。よってクエリ毎に木の高さ程度しか計算量がかからず、全体 $ O(2^{K} \log K) $ で求まる。
E 問題。online を共用してくる問題だ。最初に木の root とそこにある金の量と単価が与えられる。クエリが $ 2 $ 種類 online で渡される。$ 1 $ つめのクエリでは指定したノードに子ノードをくっつける。金の量と単価も与えられる。$ 2 $ つめのクエリでは指定したノードから root へ移動していき指定された量の金を購入していく（足りない場合はできるだけ買う）。その過程で買った金の量とコストを出力する。ただし、子ノードの金の単価は親よりも高いという制約がある。
祖先ほどコストがかからないので、指定されたノードから root へのパスを考えたときに root から貪欲にとるのが最善なのはすぐわかる。しかし、愚直にこれをやると到底間に合わない。まだ金が残っている最も root に近い祖先を高速に見つける必要がある。offline ならニヤつきながら HLD で殴るのだが、多分 writer はそれをさせたくなかったのだろう…まあよく考えると木なので親は $ 1 $ つだしダブリングができる。というか忘れてたけど LCA ってこのダブリングでも求められたな。というわけでダブリングを書く。これで二分探索によって目的の祖先を見つけることが出来る。実装に手間取り時間がなかったので目標の金の量に達するまでこれを雑にループさせた。投げる。通った… 3000ms 弱あったと思う。
CDE の実装パートで時間を使っていたのがもったいなかったが、順位表を見る限り F は無理そうなので解くべき問題は全て通したと言える。めでたしめでたし。ただ E の TL だけがちょっと不安だ。
あとは D 問題は個人的に好きだったので Comment をした。前回意図的な negative な Comment をしたのでこれからは positive な Comment などもしていくぜ。就寝。
06/05 (SAT)
10:00 起床。今日は同期と遊びにいく予定だ。といっても秋葉原とかは混んでてまあいろんな意味でよくない（ゲームで待ちが発生して面白くないし、ご時世的にもね）ので、千葉の妙典とかいうところまで行った。初耳だった。まあ電車を調べると秋葉原と大差ない距離だったのでよかった。
ここで「イオン市川妙典店」とかいう文字列を見たので「てんてん」が含まれていて面白いなと思ってニヤニヤしながらツイートをしたら、「妙典」は「みょうでん」と読むらしく泣いてしまった。いや「でんてん」でも面白いかもしれない。
今日はマジで一日遊ぶつもりで実際そうした。昼から夜まで遊んだ。
うまかったリザルトを一つだけ貼っておく。色々うまかった気がするが、あんまり写真を撮っていなかった。 久々に同期と一緒に音ゲーしたり飯を食ったりして楽しかった。少人数なら時々こうして会ってもよさそうだし今後もしていきたいな。 居た同期のうち半分がもう社会人になっているのですごい変な感じがした。
今日の典型問題に関しては、チラ見したがまともな解法が思いつかなかったため、日曜に回すことにした。
06/06 (SUN)
12:00 起床。最悪の目覚め。だがよく寝た。一回アラームを消したという記憶がある。
多分午前中は Twitter の TL には昨日の典型に関する情報が流れていると思い、見ないようにした。 朝食は諦めて昼食を食べた。
そういえば書き忘れていたが、昨日ゲーセンでカバンの中をガサゴソしているときに入っていた名札の安全ピンによって右手薬指を怪我した。綺麗な指し口だったのか、圧迫したらすぐに血も止まって特に痛くもなかった。 しかし今日は AtCoder の Rated で割と黄色になれるかどうかがかかっているのであまりパソコンに触らず安静にしていようと思った。 こういうとき、油断して普通に酷使するとまた血が噴き出すのである。
と言いながら、ずっとパソコンから離れていた。よくよく考えたら自分はあらゆる趣味、仕事、勉強・研究などを指を使って行っていることに気づく。マジでやることがなくなってしまい、漫画と YouTube でお茶を濁していた。
ところで最近、金色のガッシュの完全版を電子書籍として購入して読み始めた。金色のガッシュどこまで読んだのかもよく覚えていないし、一から読んでいくことにした。内容は面白いし、完全版は一冊のボリュームが大きくてなんか得した気分になる。 そういえば清麿って中学生だったな。すっかり忘れていた。
18:00 ぐらいになって、絆創膏を外してみる。絆創膏剥がしたて特有の白さになっている、タイピング確認をしたところ、特に痛くなく競技に支障は出なさそうで安心した。 解けていない問題をチラチラ見たりネットサーフィンをしたりして夕食までの時間を過ごした。
食後休みつつ AtCoder Beginner Contest 204 - AtCoder の準備をする。
A 問題。最近の A 難しい。$ (6 - x - y) \bmod 3 $ でいいが本番は一致する場合とそうでない場合で場合分けをした。
B 問題。$ 10 $ 個を超えている木に対してのみ $ A_i - 10 $ を足し合わせれば良い。
C 問題。$ O(N(N+M)) $ が間に合うので素直に DFS を各頂点から実行するのが良いだろう。最初双方向だと思って sample 合わなくて困った。 ちなみに、強連結成分分解をすれば $ O(N+M) $ でも解けるな。
D 問題。 $ 2 $ つに分けたときの max-min 問題。ついでに和が一定なので片方の和のみを考えればいい。よく考えると部分和 DP でいいや。 単に部分和 DP よりは和一定が本質だな。 こういう $ 2 $ 択の最適化は余程選び方にいい性質がない限り全探索ベース以外無理なの明白な気がするが、意外と貪欲を試す人が多かったらしい。
E 問題。各辺のコストが時間とともに広義単調減少するね。よって dijkstra にコスト計算を生やせば良いと思う。 $ t+1 $ が $ \sqrt{D} $ 以上になるまで待つのが最適。商の値の性質は、分子が分母の平方根以前以後で変わるというのは時々競プロで出る気がする。 分母を $ 1 $ ずつ増やしてくと平方根以前は狭義単調減少になり、平方根以後は被りながら高々 $ 1 $ 変動の広義単調減少になる。 $ 1 $ 以下の変動の時待つコストと合わせてトントンなので、結局平方根以上になるようにするのが最適だとわかる。 $ (t+1)^{2} \geq D $ の条件式を書いてオーバーフローによる WA でゲロ吐きそうになっていた。
F 問題。2x1 と 1x1 のパネルを敷き詰める方法の数え上げ。 $ H \leq 6 $ で $ W \leq 10^{12} $ だ。うーん。どう見ても DP だ。うーん。行列累乗だぁ。 ベクトルを考えると、列ごとに見て埋まっているかどうかの $ 2^{H} $ 次元で十分そう。 ただ行列の計算が下手でかなり困っていた。それぞれの状態について DFS をした。$ H $ 小さすぎるし余裕で間に合う。 あとは累乗して出たベクトルの全部空いている成分が答え。AC。
全完タイムがかなり悪かった（ペナ込みで 100:50 ）ので祈りながらコンテスト終了。 どうやら perf 2211 。黄色になれた〜。
黄色だまりの仲間になった余韻に浸っていたら、Div.2 の存在を忘れていた。おやすみなさい。
