06/21 (MON)
9:30 起床。眠い。昨日の夜はとりわけ暑かったので睡眠の質の低下を感じる。
今日は先日（だいぶ前だが）失くした Suica の再発行をしてから大学に向かった。 記名式 Suica の再発行は手数料さえ払えば完全な復元が可能になる。 事前に手続き自体は済ませておいたので、今日は引き換え券を持って行って実際にカードをもらうだけだ。 みどりの窓口に取りにいくのだが、先客がいる。 何やらチケットを買おうとしているのだが、これが長くてモヤモヤしてくる。 チケットは多くの場合、インターネットやら他の券売機で買えるし窓口の対応する人とのコミュニケーションも円滑とは言えず 12 分ぐらいかかっていた。 ちなみにその後の自分のカード受け取りは身分証明書を見せてものの 2 分で終わった。
みどりの窓口はチケット対応するだけの窓口を作ってくれても良くないか？って千年ぐらい前から言っている。 まあそんなに人いないんだろうけど。
今日の典型を確認する。今週はちゃんとやるぞ。
https://atcoder.jp/contests/typical90/tasks/typical90_bt
問題概要。$ H \times W $ のグリッドが与えられて、それぞれのマスは山か平野である。このグリッドに鉄道を引きたいのだが、 平野にしか線路はひけず、かつ始点と終点が一致してそれ以外では同じマスを通らないような鉄道しか引けない。 最長の鉄道が通るマスの数を求めよ、という問題。
結構エグい問題が出てきたなあと思ったが、$ H \times W \leq 16 $ という制約を見てハイ、となった。 というか冷静に考えると最長路問題に落ちるので効率的な解があってたまるか。 全ての始点に対する全てのパスを DFS で探索する。最後に始点に戻ることができる場合、そのパスが含む頂点の数を答えに寄与 (chmax) する。 流石に全てのパスは多いかもと思うかもしれないがグリッドグラフのパスの数はかなり少ない。 実際に後で今回の問題での自明な最大ケースである $ 4 \times 4 $ グリッドで平野しかないパターンで再帰関数が呼ばれた回数を数え上げたら $ 28,512 $ だった。 最悪でもこれの $ 4 $ 倍程度の計算量しかかからないので、余裕で間に合う。
グリッドグラフのパスの数の見積もりって難しいなと思って、ついでに大きくして検証した。 $ 5 \times 6 $ の場合に再帰関数の呼び出し回数が $ 39,012,544 $ で $ 800 $ ms で間に合ったがそれ以上大きいと厳しそうである。 グリッドグラフのパスの数は辺が全てある場合は $ 5 \times 6 $ ぐらい、つまり $ 30 $ マスぐらいが愚直の限界と覚えておこう。 当然枝刈りをすればもっと速くなるだろうが、話が面倒になるので一旦ここで区切りたい。
大学につく。いつものケイジャンビーフのチー牛メシを食べる。いつも通りゼミが始まる。 後輩のスライドがしっかりと作り込まれていて、真面目だな〜と思うなど活動は多岐にわたる。
ゼミが終わった後は、先週の分の週記を投稿した。 そして作業に戻る。途中で典型のジャッジが来たので通しておいた。6ms だった。流石に軽いね。
大学を出て、ゲーセンに向かう。最近ゲーセンに向かいすぎである。 周りの人が上手すぎて頻度を上げないと拮抗する実力を維持できないのだ…。
足繫くゲーセンに通っている成果が出ているのか高難易度でのいいリザルトが最近は見られる。 5 月ぐらいに最終更新の PUC 難易度表では、上のそれぞれの曲の PUC 人数は $ 71 $ 人と $ 33 $ 人だそうだ。右の方をちゃんと PUC だせば地域ランカーぐらいは名乗ってもいいかい？ちなみに自分が既に出している 19PUC は $ 86 $ 人のと $ 91 $ 人のだ。 maimai とかいうゲームを真剣にやってた頃は 30 人目代の理論値 AP とかランクイン曲を複数持っていた気がするので、まだその域にすら相対的に達していないと思うと気が遠くなる。
家に帰ってご飯を食べる。夜に帰ってもご飯があるのは有難い。 今辛うじて競プロにつなぎ留められているのは Streak のおかげなので切らさないようにしてから寝ることした。 よく見たらついに前回の Streak を越している！
ジャンプは…眠いし明日読むことにした。
06/22 (TUE)
10:30 ぐらいに起床。濃い緑茶をやめてから胃の調子がそこそこ良い。
ジャンプを読んだ。田村隆平の最新作「灼熱のニライカナイ」が終わっていた。 最近のジャンプ、前作が売れた作家がコケまくっていてなかなか（業界の）厳しさを感じる。
気づけばジャンプ惰性購入記に入ってしまっている。週 250 円とかなので全然買い続けるんだけど、今真剣に楽しみだなぁと思っている漫画はヒロアカぐらいで、他もちゃんと読んでいるのだが週ごとに状況を確認するレベル。 漫画アプリの漫画の方が続きが気になるとかいう最悪の状態に陥っている。今は我慢の時期っぽい。伊達に中2 からジャンプを買い続けていないぞ俺はつってる。
今日の典型を確認する。★5。
https://atcoder.jp/contests/typical90/tasks/typical90_bu
問題概要。$ N $ 頂点からなる木が与えられる。各頂点には a か b のラベルが与えられていて、各連結成分が両方のラベルの頂点を含むような辺の切り方をしたい。切る辺集合の数を数え上げろ、という問題。
制約が $ N \leq 10^{5} $ なのを確認。条件を満たすように木を切っていくなんて問題は木 DP と相場が決まっている。その方向性で考えると、必要な情報はある頂点を根とする部分木に対して、a しか持っていない・b しか持っていない・両方持っているの $ 3 $ つの切り方の場合の数だとわかる。
状態数が抑えられていい感じだが、最後に枝のマージを考える。
マージ先の頂点のラベル（ $ c $ とする）は必ず持つことになるため、実質 $ 2 $ 通りを考えれば良い（両方持っている場合と $ c $ だけ持っている場合）。
$ c $ だけ持っている場合の数は、全ての枝の $ c $ だけ持っている場合の数 + 両方持っている（けどその枝は切る）場合の数の総乗となる。余事象によって両方持っている場合の数は求められるので結果的に $ O(N) $ の木 DP ができる。
★5 にしては面倒だなと思いつつも、まあ見た目からして木 DP だしマージぐらいしか考えることがないのでそんなものか。
昼飯を食べてからは、母親がドラゴン桜をみていたのでのぞき見した。
お前は帝京平成大学へ行け pic.twitter.com/2Fyqn9mlqj
— フルメタル安藤政信 (@nasuno500000000) May 5, 2021
ドラゴン桜自体は面白いと思うのだが、このツイートと画像がチラついて困るという問題がある。 ファミリーマートのマークを雑にくっつけているのもかなり好きだ。
そのあとはいつもと同様にピアノをしばいていた。大分つらい部分を練習していたのだが、だんだん慣れてきた。 この調子で今月中には形にしないとなぁと思っている。 記録として YouTube にピアノ動画を up することも時々考えているのだが、なんか恥ずかしい（演奏者にあるまじき発言）ので断念している。
夕食。おいしかった。 夕食後はもこうの動画を見ていた。 ポケモン動画で負けフラグ立てて台パンするもこうみると、変わらぬ実家みたいな安心感と笑いが得られる。 ポケモンで発狂するもこうはまあもうお馴染みなのだが、時々 DS とかの昔めのゲームをプレイしてる。 やわらかあたま塾をプレイするもこうの動画が最高に面白かった。 最初のつみきを数えるゲームでルール理解してなくて沼プレイしている時、呼吸困難にさせられてしまった。 妙にうまくて澄ました実況よりこういうのを求めてるんだよなぁ。
Streak のための虚無を一応解く。B - アキレスと亀を解いたのだが、アキレスと亀に思いを馳せることができて、いい問題な気がした。 アキレスと亀の問題は両者が等速運動をしているなら極限という概念の暴力によって解決するの初見はかなりスッキリした覚えがある。 等速運動しないケースを問題にしたらかなりダルそうだなと思うなどしていた。
次にC - 正直者の高橋くんも解いた。 無向グラフと頂点 $ A,B $ が与えられて $ A $ から $ B $ への最短経路数を求めよと言う問題だった。 制約が $ N \leq 100, \quad M \leq 200 $ とかだったので、ベルマンフォードっぽい更新で求めた。$ O(NM) $ である。 解説を見ると、最短経路木を作ってやれば、木に含まれない辺も有向にできて DAG になるので $ O(N+M) $ になると書いてある。 最短路 DAG はちゃんと頭に入れておこうと思いつつも、「なら $ N,M \leq 10^{5} $ とかで出してくれよ」とか思ってしまった。
典型のジャッジが来ないので明日出すことにして寝た。
06/23 (WED)
9:45 起床。今日は大切な用事もあるしピアノもあるので最低限の時間には起きた。 昨日の典型を提出する。問題なく通る。★5 にしては難しかったな～と思ったので一応想定解を確認する。 完璧に同じ木 DP だった。これをもっと早く書けるようにしようと思った。
今日の典型を確認する。★6 だ。
https://atcoder.jp/contests/typical90/tasks/typical90_bv
問題概要。a b c の $ 3 $ 種類の文字からなる文字列 $ S $ が与えられる。この文字列に対して、次の操作が行える。
a以外の文字を選んでアルファベット順で $ 1 $ つ前の文字にする。その後左側の文字を全て"変化"させる- "変化" とは a→b, b→c, c→a のように文字を変換することである。
文字列 $ S $ に対して行える操作の回数の最大を答えよ、という問題。
$ |S| \leq 60 $ であることを確認する。とは言え、このぐらいの大きさの制約が一番情報量がない。
なぜなら、こういう制約のときは愚直を却下したいだけのパターンと、四乗ぐらいのアルゴリズムを想定する場合があるからだ。
というわけで冷静に問題を観察する。全て a になってしまったら操作をすることはできなくなる。大まかな操作可能回数として $ a=0, b=1, c=2 $ と置いてみる。変化に関しては $ 2 $ を $ 0 $ にしてしまう処理であることに気づく。これを出来るだけ避けたい気持ちになると、非 $ 0 $ の最左要素を選択して操作を行い続ければ $ 2 $ が $ 0 $ に変化することないと割とすぐわかる。最初これを実装して TLE を食らい我に返った。"0001" の操作回数は $ 8 $ であるように $ 2 $ のべき乗を係数として操作回数を効率的に求められるのでこれにより、$
O(|S|) $ で解くことができた。
今日はジャッジがかなり早くきたのでとっとと AC した。
わりとすぐわかる最適な貪欲手順があって、それをそのままやると間に合わないので効率よく貪欲と同じことをするみたいな問題はしばしば出題されて、自分は苦手なので学びになった。
今日の用事のために既存のスライドを弄っておく必要があったので、コピーしてちょっと弄るなどした。 スライド作成って全然やる気が起きないのはなんでだろう。 多分もうスライドを作成できる段階になっていたら、既にその内容は頭の中では完結しているからかもしれない。
昼飯を食べてから、ピアノのウォーミングアップ兼練習をする。 うーん本当に今月中にものにできるか心配になってきた。先週の惨状よりマシなので今週はこれで許してもらおう。 自転車がパンクしているため、走って教室に向かうハメになる。というか、うちの自転車頻繁にパンクしている。 だれか棘とか刺してないか？これ。
ピアノから帰ってくると大事な用事の時間になる。 多分これはマジで喋っちゃいけない奴なのでふんわりと大事な用事と言っておく。 18:00 ぐらいに終わった。実りのある内容だった気がする。やることが明確化されたが、言い直せばやることが増えたぜ。
休憩がてら、クラッカーに Kiri クリームチーズを付けて食べる。 これ本気でうまいのでお勧めする。クラッカーが家にあるとか、安く売っているとかだったら試してみてほしい。 この方法で俺は幾度となくクラッカーを箱ごと消した。
休憩後、長らく色々あってなかなかまとまって動けなかったインターンのタスクを改めて消化しなおす。 というのも前回の稼働から大分時間が経っていて何をやっていたのか忘れていたので自分のコードを読みながら作業を追っていた。 過去の自分が聡明だった（レアケース）ので、コードにコメントが残っていて読みやすかった。
食後、作業を続行する。この時間はよく兄が部屋に乱入してくるのだが、例にもれず乱入してきた。 面白いことを言って笑わせてくることもあるが、今日はイマイチネタが伝わってこなかった。 作業の結果、意味不明なものが錬成され、多分これは自分のせいじゃないので slack に投げて本日の営業を終了した。
この後、研究や競技プログラミングをしようかと思ったが乗り気じゃなかったので Twitter 閲覧などをしていた。 すると tolt_santyoku が BMS を 1 時間ぐらい配信するというので、見ることにした。 勝手に人の配信で認識のリハビリをしたり、セイウチくんに癒されてるうちに 1 時間が経った。
明日は普通に大学に行くので今日の分の週記をつけて、就寝を決めた。
06/24 (THU)
8:50 起床。ぼやぼやしながらやることを処理していた。 ちょっとして、今日の典型を確認する。★3。
https://atcoder.jp/contests/typical90/tasks/typical90_bw
問題概要。正整数 $ x $ がある時に、これを叩くと $ ab=x, \quad a \geq 2, \quad b \geq 2 $ を満たすような $ 2 $ つの整数 $ a, b $ に分裂する。 最初箱の中に正整数 $ N $ が入っていて、箱の中の整数は $ 1 $ 回の操作で同時に叩くことができる。箱の中の整数を素数にするのに必要な最小の操作数を答えよ、という問題。
流石に見たまんま。箱の中の整数が全て素数になっている状態は素因数分解で一意、なるべく素因数を均等になるように分裂させると二分木のような構造になる。 よって、完全二分木の葉の個数が素因数の数以上になる最小の高さ $ k $ を求めればよい。素因数分解がボトルネックになり、試し割りで $ O(\sqrt{N}) $ で解ける。
家に長い時間いた気がするが、大学に向かう。 とは言っても先日の MTG によって、結構方針転換したばかりで大学に行ってどうというわけでもないが、家族以外の人間の居る環境に行くためも大学には行くことにしている。
大学の最寄り駅に着いたのが結構遅く、キッチンカーで今から食べるのも渋くなったので First Kitchen で昼食をとることにした。 今週はちゃんとチー牛だなと把握しながらチーズベーコンエッグバーガーを頼んだ。美味しかった。
大学に着く。最初は作業しようとするも調べものや論文読みみたいなことをしなきゃいけないので、もぞもぞしていた。 調べものフェーズが苦手すぎるし、研究に向いているのか向いていないのか段々わからなくなってきた。
もぞもぞしていると、研究室の同期が paiza のページを開いていたので、自分も登録してやってみることにした。 paiza の仕組みがイマイチわかっていないのだが、同期に教えてもらいながらやった。 競技プログラミングの問題を解いていくと paiza がどんどん軽率に褒めてくれるのでうれしくなった。
途中で教授との MTG とかがある。まあ、上記の通り特に新しいことはなく調査フェーズだ。
paiza をやって気持ちよくなっていると、先輩が来て過去にコーディングテストか何かで解けなかったらしき問題を、解けないかと聞かれた。 制約はイマイチ覚えていないらしいが、興味深そうな問題なので掲載しておく。 因みに僕はまだ考え中です。自分のより速い解法があったら教えてください。
問題文
$ 1 $ から $ N $ の番号の付けられた $ N $ 本の木が生えています。 それぞれの木には $ m_i \quad (1 \leq i \leq N) $ 枚の葉が付いています。 $ 1 $ 日に、それぞれの木から $ L $ % の葉が落ちてしまいます。 正確には、その日の始めに $ X $ 枚の葉がついている木から $ \left \lfloor X \cdot \frac{L}{100} \right \rfloor $ 枚の葉が落ちます。
この時、$ K $ 日後にはそれぞれの木には何枚の葉が付いているでしょうか。
ただし入力は全て整数とする。
解法
$ O(NK) $ で愚直に割って引いてを実行することができる。まあこれは流石にわかる。
次に愚直改良として、$ L $ が整数なことを利用して $ K $ が大きくても速くできるのではないかと考えた。
10^18 * 0.99^x < 100 - Wolfram|Alpha
を見ると、$ m_i $ が $ 10^{18} $ であったとしても実数で考えると $ x = 3665.68 $ ぐらいで収束することがわかる。 そのため日数経過によって葉の枚数が変化しなくなったら打ち切ることで一気に速くなる。 $ 1 \leq N \leq 10^{4} $ ぐらいまでなら $ 1 \leq K \leq 10^{18} $ とかにも対応できそう。 現実問題、$ m_i $ は $ K $ と掛け算をするため良識があるなら $ 10^{16} $ とかにするだろう。（まあ大して変わらないけど）
うーんこれ以上はわからん。これでファイナルアンサーなら ABC の C や D あたりに置かれそうだ。
さて、paiza をやっていると S ランクになる。スーパーエンジニアだって。そんなに褒められると照れる。 べた褒めしてくれる paiza くんのことが大好きになった。 記念に S ランクの問題を解く。paiza は問題言及ができないので詳しい情報は省きます。 なんと TLE を食らう。確かに軽率な $ \log $ を付けた自覚があるが、軽率な $ \log $ を付けたぐらいで落ちる問題はクソや。 しかもこれ提出が一回までしか許されないのも知らなかった。ボケカス。paiza はクソや。 現場からは以上です。
今日は所属している音ゲーサークルの総会があるらしいので、早めに帰宅する。 マジで今日ちょろっと調べた以外は全て paiza くんに振り回されただけだった気がするが、気にしないことにした。
帰宅。総会の時間にはなんとか間に合ったので zoom を起動して接続。 若者が多い。 $ 4 $ 年前は自分もその立ち位置だったのかと思うと感慨深い。 大学に入ってから時間の流れが速く感じているが、中1 が 高2 になる時間が経過していると考えると長い時間を大学で過ごしているな。
総会の後は多くの人は zoom に残ってわちゃわちゃ会話に花を咲かせるのだが、楽しくて夜中まで通話していた。 友人がナスのアバターみたいなのにしてたり、よくわからない生物になったりしていてウケた。人生が $ 2 $ つあったら一回オンラインゼミ中にアレになってみたい。 適当にやっていた、ボルテの譜面クイズも楽しかった。音ゲーサークルみを久々に感じた。
06/25 (FRI)
11:11 起床。ゾロ目を狙って起床した。 いつも夜中に起きているのだが、通話はなんだかんだ疲れるのかしっかり寝坊する。
とりあえず今日の典型を確認する。★3。
https://atcoder.jp/contests/typical90/tasks/typical90_bx
問題概要。ホールケーキがあって、半径に $ N $ 箇所切れ込みが入っていて $ N $ 切れに分割されている。 時計回りに $ i $ 番目に分割されたケーキの大きさは $ A_i $ である。 連続するケーキを、合計の大きさが全体のちょうど $ 10 $ 分の $ 1 $ の大きさになるような選び方は何通りか答えよ、という問題。
よくある奴だ。見た目は完全に尺とりなのだが、円環上の問題なので列を $ 2 $ 倍加して尺取りをすればいい。 コンテスト本番なら惜しみなく二分探索をしてしまうだろう。
さて、ちょっと論文を読んだり昼ごはんを食べたりしている内に TA の時間になる。 先週は久しぶりにちゃんと質問がきて答えたのだが、今週はまた質問 0 に逆戻りした。 TA が終わるとすぐゼミ。ふむふむ。ほーん。ゼミはなんだかんだ初めて知る知見も多く面白い。自分が発表の回はつまらん。
すべてが終わって、用事を処理していたりしたらもう夜になる。金曜嫌い。 今日は TopCoder SRM があるのでぱっぱと夕飯を食べてパソコンの前に構える。
Easy。$ N $ 問の問題がコンテストに提案されて、 $ N \times N $ 行列 $ A $ が与えられる。 $ i $ 問目と $ j $ 問目の関係について、「 $ A _ {i,j} - A _ {j,i} $ だけ $ i $ が直接的に優位である」と定義される。 また、$ i,j,k $ について $ i $ が $ k $ に $ X $ だけ（直接・論証的）優位で $ k $ が $ j $ に $ Y $ だけ（直接・論証的）優位なとき、 「 $ i $ は $ j $ に $ \min(X,Y) $ だけ論証的に優位である」と定義される。 $ i $ の $ j $ に対する論証的な強さは、論証的優位な値の最大であり、 $ S(i,j) $ と表現される。 $ S(i,j) \geq S(j,i) $ の時問題 $ j $ より $ i $ を優先的に選出するとすると、他のすべての問題に対して優先的に選出される問題を全列挙せよ、という問題。
読みにくかった。$ N \leq 200 $ なので、正直どうとでもなりそうだが、グラフに落としてベルマンフォードっぽく更新して $ S(i,j) $ を求めた。 ワーシャルフロイド法の方が楽だったらしい。
Med。$ 2^{a} \times 3^{b} \times 5^{c} \times 7^{d} \times 11^{e} $ で表現される $ M $ が与えられる。 $ a,b,c,d,e $ の中央値を $ m $ として、以下の操作の果てに任意の $ M $ を $ 47^{m} $ にしたい。
- リストとして、分数が並んでいる
- 左から見ていって、一番最初に掛けたら整数になる分数を掛けて一番左に戻る
- 掛けて整数になる分数がなかったら、そこで操作終了
有限操作、ステップ数が $ 3000 $ 以下、分数の数 $ 99 $ 以下…その他細かい制約を守って要件を満たす分数のリストを構築せよ、という問題。 とっかかりがなく悩む。 ちょっとすると、分母を $ 2^{5} $ 通り全て使うことを考える。冷静になると、$ 3 $ つ以上の素因数の積で割れる回数が $ m $ である。 よって分母の構成素因数の数の降順に分数を並べ、 $ 3 $ つ以上の素因数の積の分母を上には $ 47 $ を乗せ、それ以外には $ 1 $ を乗せれば良い。 面白いな、これ。しかし sample が通らない。通らない。通らない…。一生ここで躓きタイムアップ。
オチはこちら
分母1は処理が終了しなくないですか？
— tute (@tute7627) June 25, 2021
さよなら…。制約は冷静に確認しような！
そのあと Codeforces もやる。Div.1 がんばるぞ～。
A: よく覚えてないし、大した証明もせずに通した。
B: わからなかった。助けてくれ。
そんなわけで冷えました。見ての通り気力も残らなかった。就寝。
06/26 (SAT)
11:00 起床。土曜だしこの時間でもいいかな。 とは言え、今日はサークル関係の大切な会議がある。 昨日の Codeforces や SRM の復習がちらつきながら典型を確認。
https://atcoder.jp/contests/typical90/tasks/typical90_by
問題概要。$ N $ 台の飛行機があって、最初 $ (AX_i, AY_i) $ にいる。それぞれの飛行機はグリッドグラフの $ 8 $ 近傍のどの向きかに $ 1 $ 秒ごとに移動する。 飛行機の向きは途中で変わらない。 $ T $ 秒後に $ (BX_i, BY_i) $ の位置に飛行機が存在するという報告があったので、これに矛盾しないそれぞれの飛行機の向きを答えよ。 適切な向きの組み合わせがない場合はそれを報告せよ、という問題。
$ N \leq 20000 $ とそれなりに大きい。当然 $ O(8^{N}) $ なんてかけられない。 $ (AX_i, AY_i) $ について $ 8 $ 方向を探索して $ B $ のどの飛行機と対応する可能性があるかは計算できる。 スンと冷静になると、完全マッチングの復元問題だとわかる。Dinic 法は全ての辺の容量が $ 1 $ なら $ O(|E| ^ {\frac{3}{2}}) $ とかだった気がするな。 なら通るな。でも結構 TL 怪しそうだしどうだろうと思っていた。まあ神を信じて解けたことにした。
昼飯はカレーを食べる。完全によそう皿を間違えて、 $ 3~4 $ かわり食べた。
昼食を終えるとサークル関係の会議の時間になるので、これを開始。 いい感じに決まっていた気がする。うん。17:00 ぐらいには終わっていたかな。 そこから昨日の Codeforces の B の続きを考えたりしていた。難しい～。
わからないのでダラダラして、夕食はマックを食べた。トリプルチーズバーガーうますぎて震えた。 AtCoder Beginner Contest 207 - AtCoder に臨む。
A: $ 3 $ つの数字から $ 2 $ つ選んだ時の最大値。ヤバい人なのでソートした。
B: 水色のボールが $ A $ 個入っていて、$ 1 $ 回の操作で 水色のボールと赤色のボールをそれぞれ $ B, \quad C $ 個入れる。 水色のボールが赤色のボールの $ D $ 倍以下の個数になるのに必要な操作回数の最小を答えよ、という問題。 $ A + Bx \leq CD x $ を満たす最小の $ x $ を求める問題。$ A $ は自然数なので、$ B < CD $ でないと絶対に式を満たすことはない。 後は式を整理して $ x \geq \left \lceil \frac{A}{CD-B} \right \rceil $ となれば解けている。
C: 開区間・半開区間・閉区間がすべてのパターンを混ぜて $ N $ 個与えられる。共通部分を持つ組み合わせの数を求めよという問題。 $ N \leq 2000 $ なので全ての組み合わせについて考える。区間の端を全て $ 2 $ 倍してやって、 開いてるなら左端は $ +1 $ 、右端は $ -1 $ してやることで閉区間と同様に扱える。あとは閉区間の共通部分判定。
D: 本日の発狂問題。二次元平面上の点群が与えられて、それ全部に対して平行移動と原点中心の回転が自由に行える。目標の点群があるのでこれに一致させられるか判定せよ、という問題。 $ N \leq 100 $ なので色々できるが発狂していた。点群は重心をとると回転では不変、平行移動では同じ分だけ移動する。 重心を基準にした座標を取ることで平行移動を完全に無視できる。 これは Big Bang とかいう問題で学んだな。というかあの時はちゃんと自分で思いついた気がするが。 あとは適当な元の点と目標点の偏角を回転によって一致させる。点群同士が一致しているかチェックすれば OK。 ここでハマっていた。まず回転によって一致させるプログラムがいかれていた。$ \cos $ を内積から求めたはいいが $ sin $ を求めるとき $ sqrt $ をかけ忘れる。 また、さらに $ eps $ の設定が悪かったせいで誤差落ちもする。もう散々や。E から先にやって本当によかった。
E: 順当にそこそこ難しい。長さ $ N $ の配列が与えられて、任意の連続部分列に切り分ける。 左から $ i $ 番目の部分列の和は $ i $ の倍数である必要があるとき、分割方法は何通りあるか、という問題。
シンプルでいいな。$ dp[i][j][k]: $ $ i $ までみた $ j $ 分割目の和 $ k \quad (\bmod j) $ の場合の数とすると解けそう。 $ O(N^{3}) $ になってしまって $ N \leq 3000 $ では間に合わない。最後の情報は正直微妙なので消せる可能性を疑う。 $ k=0 $ の状態どうしで遷移すれば次元が落とせる。しかし単純に個の遷移をしてしまうと結局 $ O(N) $ 遷移で計算量は変わらなくなる。 そこで DP の遷移高速化のテクの一つである、最左の遷移可能状態のみに遷移するというのをやる。 実際、同じ分割内で $ k=0 $ 同士の遷移を何度もすることと、$ k=0 $ の遷移一回で次の分割に向かうことは等価。 丁寧に遷移を実装すると通る。
F: D にハマってて読んだだけ。また考えます。
D にハマった割には成績は悪くなかった気がする。ABC で冷えることはよほどでない限り、まあなさそう。 明日は AGC なので震えています。しかし辞退するようでは、黄色に復帰してからが伸びないのでちゃんと出ます。
深夜に典型問題を通した。1000ms とかでブルブル震えていた。
06/27 (SUN)
11:00 起床。昨日の典型の解法を確認する。 昨日の典型はやっぱり Dinic 法で問題なかったようだ。Ford-Fulkerson を落とすための厳しい制約だったそうだ。
朝食後は作業したり、漫画アプリを閲覧をしたりしていた。 本日は昼食兄と自分しかいないので、昼飯をなんとかしなければならないのだが、起きていないので起こす。
昼飯は里のうどん。カレーうどんを毎回食べている。具が充実していて、満足度が高い。
ゲーセンに行こうかという話も持ち上がったが、普通に混んでそうだしやることもあるので断念。
帰ってからは最近のコンテストの復習とかをしていた。 昨日の F 問題を解いた。D で発狂していたから気づかなかったが F も個人的にはなかなか辛かった。 木 DP のマージ部分が苦行になってしまっていた。
お馬さんレース（宝塚記念）を見る。よくわからないのだが、兄が最近よく見ているので一緒に見た。 自分もちゃんと勉強してお馬さんレースを見たいな。
そうして、お馬さんレースを見終わったら作業や競プロをした。 夕食後、AtCoder Grand Contest 054 - AtCoder をやる。
A: 文字列 $ S $ が与えられて、左端と右端の文字が異なる segment を消去する操作を任意回数行える。この時文字列を空にするのに必要な最小の操作回数を求めよ、という問題。 $ S $ 自体の最初と最後が一致しなければ自明に $ 1 $ になる。一致していても、途中に非頭文字の文字が $ 2 $ 連続以上で並ぶと $ 2 $ を達成する。 他の場合を考えると、頭文字が交互に出現する文字列になる。これは空にできないことが数学的帰納法でわかるので、$ -1 $ ということになる。AC。
B: 数列 $ A $ が与えられる。$ A $ を並べ替えたのち、左から数字を $ 2 $ 人で取っていく。 $ 1 $ 人目のとった数字の和が $ 2 $ 人目のとった数字の和以下の時、$ 1 $ 人目が数字を取り、そうでない場合は $ 2 $ 人目が取る。 最終的に $ 2 $ 人の取った数字の和が等しくなるような $ A $ の並びの数を数え上げよ、という問題。 数え上げ.pdf を信じているので「順列の数え上げは挿入ソート」を復唱していた。 実際に小さい順に挿入することを考えると、挿入した後ろの数字を取る人が変わるというなんとも言えない性質が出る。 永遠に沼っていた。実際は挿入 DP では解けない。
C: 長さ $ N $ の数列 $ A $ が与えられて、それぞれの要素の左側にその要素より大きい数字がいくつあるかを考えた時（$ x_i $ などとしておく）に、その値が $ K $ 以下に収まる数列が与えられる。 これは、この条件を満たすように元の数列に対して（最小回数の）隣接 swap を繰り返した後と考える時、元の数列としてあり得る場合の数を答えよ、という問題。 $ 1 $ 個前の状態としてふさわしいのは前より $ \sum _ {i=0} ^ {N-1} \max(0, x_i - K) $ の値が $ 1 $ 大きくなるような swap をして得られる並び。 というのもこの値は一回の swap ごとに高々 $ \pm 1 $ される。具体的には $ A_i < A _ {i+1} $ のような隣接要素を swap すると $ x_i $ が $ +1 $ される。 つまり、$ x_i \geq K $ の場所を見つけて $ +1 $ する操作は行える。詰めると、動かせる要素の場所候補の数をかけるといいことに気づく。AC。
結果は AC 二完。苦しすぎ。B が解けなかったの悲しいね。 地力の足りなさ（精進の足りなさ）を嘆きながら今週を終えることになった。
