www.youtube.com
問題
rngさんが解説をしていて、それを文字に起こしただけの記事。
0:25 E. Need for Speed
問題 N地点と合計時間Tがある。 i番目の地点は、地点D[i]でその前の地点からこの地点までのスピードはS[i]である。 スピードメーターはある一定の誤差があり、速さsと表示されていても実際はs+cである。 誤差cを答えよ
誤差cを二分探索で求める。
誤差が増えれば、各区間でかかる時間は単調に短くなっていくはずなので、その合計時間も単調に変化する。
そのため、誤差を二分探索して合計時間が丁度Tになるときのcを探せば答え。
0:35 I. Secret Chamber at Mount Rushmore
問題 M個のルールがある。 これは文字aを文字bに変換できるというもの。 これに対してN個の文字列のペアがある。 文字列Aの各文字に対してルールを適用していくことで文字列Bに変換できるかのyes/noを判定する。
'a'～'z'のグラフを用意して、ルールに従って有向辺を張る。
そして、WFを回して、各頂点間の到達性判定をする。
あとは、各文字列の変換可能性は各文字に対してさっきの到達性判定を見て、全ての文字が到達可能なら、yes
0:50 F. Posterize
問題 D個の石の塊がある。 i個目の塊は、頂点R[i]にP[i]個の石がある。 ここで、K個の頂点を選ぶ。 全ての石に対して一番近い頂点との差の2乗の総和をとる。 この総和の最小値は？
dp[R][K] := [0,R]の塊をK個の頂点に集約するときの差の二乗の総和。
各区間の差の二乗の総和の最小値を取るような座標を前計算すればできるが、これは丁度頂点の平均値となる座標である。
これを前計算しておけば、dpは遷移数がO(N)で計算できるので、O(N^3)で間に合う。
1:00 A. Airport Construction
問題 解答
「これを4問目にやろうというチームの考えていることが分からない」
問題 N頂点の凸とは限らない多角形がある。 この多角形の内部を完全に通る直線の最長は？
「最長の直線は2つの頂点を通るはず」なので、O(N^2)で通る2頂点を全列挙して、
他の直線との交差判定でO(N)をして、O(N^3)で通せる。
誤差やらコーナーやらで通すのはとてもむずかしい。
コメント見てるとこの問題と全く同じ問題であることが発覚。
AC取ってる他人の解法を3つほどパクってきて、提出してみたら全部WAかTLE。
会津大学があんだけWA取ってるのも伺える。
1:10 C. Mission Improbable
問題
「これはフローの有名問題」「マッチング」
問題 R×Cのグリッドが与えられる。 ここで横から、前から、上からのカメラがある。 横からは、行の最大値を維持する。 前からは、列の最大値を維持する。 上からは、要素があるかどうかを維持する。 のを確認している。 全ての条件を維持しながら、最大何個減らせるか。
よく理解してないのだが、列と行のマッチングを最大フローで行っていく。
よく分かってない。
1:30 「レート詐称」
1:32 D. Money for Nothing
問題 赤の頂点集合と青の頂点集合がある。 ここから、1つずつ選んで、赤が左上、青が右上となる2つの頂点から成る四角形の面積の最大は？
rngさんの二次元プロット上での問題の言い換えが反則級に分かりやすい
後回し
1:45 閑話休題（この辺からプロすぎて分からない）
1:53 L. Visual Python++
問題
あんまり解けなさそうなので次
問題 "「"と"」"が同数ある。 "「"と"」"を1対1でマッチングさせて四角形を作る。 四角形の辺は交わってはいけない。 内包するのはOK。 接するのはダメ。 マッチング可能か。
2:02 G. Replicate Replicate Rfplicbte
問題 ライフゲームをする。 近傍の和のmod2が次の状態になる。 最終状態が与えられるので、最小の初期状態を復元せよ。 ただし、各世代交代で1マスだけエラーが発生する可能性がある。
2:16 K. Tarot Sham Boast
問題 長さNのPRSから成る全ての文字列集合を考える。 その中で、S個の文字列に対して、文字列集合内で何回出てくるかカウントする。 S個の文字列を登場する回数が多い順にソートせよ。
「どう考えてもこれが得意」
2:25 休憩
2:30 K問題再開
「文字列にある特徴があれば現れやすい」
「KMPで現れやすさが分かるので」
2:38 chokudaiさん「G問題通りましたー！」
2:48 G問題へ
「flipが無いとして前の状態を復元できるが、ある1つをflipすると大幅に1が減らせるポイントがあってそれを毎状態確かめていく」(2:57あたり)
「flipする位置は一意に決定できる」
解けた（俺はさっぱり分からない）
3:07 D問題へ
「よくある二分探索のへんなことやるやつでできます」
DPの高速化でたまにあるテクニック(3:13頃)
真ん中のやつを全探索で決めて、2つに分割して、また分割後の中心から全探索で決めるみたいなことを続ける。
こうするとO(NlogN)くらいで判別できる。
解けた。
3:21 L問題へ
「これ貪欲じゃないの？」
貪欲の場合分けをする。
「座標圧縮してBIT」
これで解けなかったらどうすればいいの？
3:38 閑話休題
3:57 K問題を実験します
「実験せずに解けるような問題に見えない」
「小さい周期を持てば持つほど小さくなる」
「長さ9から効いてくる」
「周期性を元にベクタに変換して、辞書順比較」
「これ以外で解ける気がしない」
4:17 総括
4:22 J. Son of Pipe Stream
問題 無向グラフがあり、花用ソースと水用ソースとシンクがある。 それぞれのソースから、花と水が流れる。 花と水が流れる向きは同じにしなくてはならない。 全ての辺で「v*flower+water<=cap」が成立。 flower^A * water^(1-A)の最大値は？
4:39 本当のまとめ
easy
――――――――――
EFI
C(flow)
D
G(linear algebra)
KL(difficult to prove)
AB(hard to implement)
H
――――――――――
hard
「解法が嘘か本当か知っている人はコメントお願いします」
無理でした
