6完 38:32 + 1ペナ 185位
イコールの有無で30分溶かしてかなしい
A Nine
3で割った商とあまりで位置が特定できるので、愚直に判定すればいいですね～
WA(え？？？)
上下も入れてました...
(AC 4:46)
B Rotate
これむずかしくない？250点
時計回りに通るマスを列挙します
右向き・下向き・左向き・上向きの順でたどります
列挙したマスについて、1個先のマスに移していくことを丁寧にやるとできます
(AC 13:12)
C Medicine
350点でまた重実装かと思ったらそんなことはなかった
i日目に飲む薬の数は広義単調減少なので、値が変わるところだけ調べればよいです
(日数、個数)のpairをソートして、順にみていけばOK
最初からK以下なのがコーナーっぽいけど優しいのでサンプルにある
(AC 16:16)
D Add One Edge
条件がちょっと複雑そうな見た目ですが、簡単に言うとN1個の頂点からなる連結グラフとN2個の頂点からなる連結グラフがあって、この2つは連結でないということになります
1からN1+N2に動こうと思うと、1からAに行く、AからBに行く、BからN1+N2という3ステップになることがわかります
よって求めるべきdは「1から最も遠い点の距離」 + 1 + 「N1+N2から最も遠い点の距離」になります
ここまでくると、BFS / Dijkstraなどの最短経路を求める手法を適用してあげればよいです
(AC 24:19)
E Family and Insurance
これっぽさを感じた
各保険ではある頂点iから下に向かって対象者が広がるので、根をスタートして子に向かう方向で計算していくとよさそうだなと思います
公式解説と同じことしか言うことがないのですが、あと何代先まで補償できるか？という値をもってDPすれば解けます
(AC 28:53)
F Box in Box
典型詰め合わせセット
まず前提として、{hi, wi, di}はソートしておいてよいです
今回の hi < hj のような大小関係があるものを数えたい・求めたいときの典型テクニックとして、「ソートして大小関係を自明にする」というものがあります
今回ではhiをもとにして、それぞれの組をソートするとhi < hjという条件を直接調べずとも、i < jという条件とほぼ同一視できます(同じ値はうまく処理するとして)
i < jという条件は、普通にfor文を回すと「今まで出てきたものだけ見ればよい」ということになるので、かなり扱いやすくなります
これで一次元落とすことができるので、二次元のverを考えていきましょう
つまり以下の問題を考えます
wi < wj かつ di < djを満たす(i,j)の組は存在するか？
これはいわゆる「平面走査」というテクニックで解けます
Segment Treeをつくって、それぞれの葉ノードにwiを対応させます
葉ノードの値は、そのwiにおけるdiの最小値とします
こうすると、wi < wj かつ di < djを満たすかどうかの判定は
seg.prod(0 ~ wj) < dj であるか？ (prodはSegment Treeでの区間の演算)
で行うことができます
ということで、hiでソートしたうえでどんどんとSegment Treeにおける葉ノードを更新していけば、3つの条件すべてを満たすものが存在しているかわかります
2D Segment Treeとかで数え上げもできるのかな？(よくわかりません)
(AC 38:32)
G Ban Permutation
めっちゃこれ
上のネタバレになっちゃいますが、i-X ~ i+Xのどれを使ったか？を情報として持つといいんだろうと思います(制約が明らかにそう言ってるので)
普通に考えるとdp[i][bit] := i番目まで見て使ったものがbitであり、条件を満たすものの通り数としたくなります
しかし、「bitの範囲のものを使わない」としたときに使える個数が何個残っているかわからないので遷移ができない気がします
そこで
dp[i][j][bit] := i番目まで見てj個以上違反箇所があって、使ったものがbitである通り数
と定義します
「j個以上」というのが不思議かもしれませんが、これは包除原理を使うことを前提としているためです(j個違反するのが確定していると考えることもできます)
誤った記述だったので修正しました(参考)
包除原理をするときは「合計で i 個以上」ではなくて「特定の i 個を選んでそれらが hoge (選んでいないものについては何も言っていない)」であることを意識するのが重要
— SSRS (@SSRS_cp) 2023年7月10日
dp[i][j][bit] := i番目まで見てj個違反箇所として決めていて、使ったものがbitである通り数
と定義します
遷移は公式解説の通りです
自分がやらかしてたんですが、問題文の条件は|Pi - i| ≧ Xなので、違反する条件は|Pi - i| < X(イコールが入らない)ことに注意しましょう
(AC 111:11)
総括
実装で無駄に詰まるのかなしすぎる
