AtCoder Beginner Contest 304F - Shift Table
メモ
Nの約数M(N < M)について
青木君のシフトを周期Mで決めた時に、すべての日程でどちらかが居ないといけない。
そのような青木君のシフトを数え上げろという問題
複数の操作列(M, 長さMのシフト)について、同じシフトが重複してしまう事があるのが難しい点
こういう時はgreedyからの帰着(数え上げpdf)に沿って、判定問題を考えるかという気持ちになる
しかし今回はそんなに感触が良くない。(操作列で作るっていうような問題設定でもないからかも) あと、シフト列が作れるかの判定にgreedyに考えるとか関係ないので
判定問題を考えたくならないような問題の場合は、greedyからの帰着をあまり考えない方が良いかもと思っておこう
重複を避けるために任意のシフト列について、それを構成しうる最小のMにそれを持たせて、それを数え上げる
なぜなら、周期x(xはNの約数)で作れる時、周期 k * x(k * x はNの約数)でも作れるため
後は約数包除で出来る
AtCoder Regular Contest 108 C - Keep Graph Connected
メモ
連結グラフについて、何か性質を満たすものを考えろという問題の時に
全域木を取って、それについて考えるのは頻出
感覚的には、連結グラフにおいて、辺が多くあることが何かしら問題において選択肢を増やすことにつながっていて、辺が多ければ多いほどその問題が解ける確率が上がりそうに見える、実際はどのような連結グラフでも解ける問題の時に使う事が多い
例えばこれとかもそう
技術室奥プログラミングコンテストとかにもそういう問題があった気がするが見つけられなかった。
今回は木の上で、根の色を決めるとそこから広がるように埋めていく事が出来たが
考察に詰まってしまった
葉から決めようとしてうまくいかなかった。
根から決めると上手くいく理由
まずすべての辺の色が異なる場合、根を適当に決め、すべての辺と同じ数字は
下でそろえればいいので出来る
辺の色が同じものがある場合、実は上にくっつくのでらく
根から決めると、今選ぶ選択に影響するものが、直前の選択だけになり今までの選択と独立になるため決めやすかったが
葉から埋めていくと、今までの選択すべてを満たすように（子の条件すべてを満たすように）しないといけないという点で複雑にしてしまっていたかもしれない
AtCoder Regular Contest 152 D - Halftree
メモ
木を生成できるような操作列を求めろ。
ここで操作とはu-vに辺を貼ったときに(u+K)%N, (v+K)%Nに辺が貼られるようなものである
Nが奇数の時だけ考える
k==1の時にパスを作りたくなる
また、g=gcd(N, K)でg==1なら、0-KとKずつ増やすことで同様にパスが作れる
g!=1の場合、0,1,...g-1からスタートしてKずつ増やした時に互いに独立する
そこでそれぞれの列について長方形のように並べたくなる
以下のように、スタートした値ごとに、Kずつ足して得られる順番に縦に並べる。
N==奇数であるため 奇数*奇数の長方形ができる
以下のように結ぶと木が得られる
AtCoder Regular Contest 160 D - Mahjong
メモ
以下の二つの操作を使って作れる、長さNで総和がMの数列Aは何通りあるか
・長さKの区間に1を足す
・あるAiの値をK足す
この問題の難しさは、異なる操作によって同じ数列が作られる事があるという点にある
これは、数えあげpdfのgreedyからの帰着のように考え
任意の数列Aについて、それに対応する操作列というものを一意に対応付け（つまり単射）ればいい
こういう時は判定問題を考える
Aを作れるかという判定は、Aiに縦向きに1つ置く操作は、iを左端として横向きにK個置く操作の上位互換であるため
左から貪欲に縦においておける。
すると各iについて横向きの操作（以後これを操作Yと呼び、縦向きの操作を操作Xとよぶ）の回数と操作Xの操作回数が一意に定まる
そしてこの一対一関係を崩さないように、X, Yの操作列を数え上げれば
それが数列Aとしてあり得る場合の数になる。
ここでは各iについて、操作YをK回以上使わなければいい
Xiの操作回数、Yiの操作回数の合計がM/Kになるようにしたうえで
ほう助原理でYをK回以上使う場所が何か所あるか
というので解ける
AtCoder Regular Contest 160
メモ
1 ~ 2*10^5 の整数がN個ある時に
xという整数を二つ消して、x+1を一つ作れる
この時集合としてあり得るものの数え上げをしろという問題
dp[a][x] := aより前までについての繰り上がり処理を終えた際に、aに対する繰り上がりがxであるような状態の場合の数
として遷移することが思いつくが、dpの状態数のオーダーが分からなかった
よく考えると、この状態数は
aiをaの個数として
操作中になり得る、最大のaiをSaiとしたときに
sigma(Sai)になる
ここでai(個数)が全体に寄与する量を考えると
ai, ai/2, ai/4, ....と右に行くにつれて半分になっていき
1+1/2+1/4+.... == 2であることから
aiが全体に寄与する量は O(ai)である
よって全体の合計もO(sigma(ai)) = O(N)
aiが寄与する量は
ARC163 D - Sum of SCC
メモ
トーナメントグラフを強連結成分分解して得られる縮約グラフはパスである。
それが本質だった。
また、強連結成分の数え上げに苦戦した。
こういう良く分からないものの数え上げは、何か別のものの数え上げに言い換えられればいいが、今回は縮約したグラフ上のパスの数+1を数えればよかったようだ。
もう少し具体的には、N頂点をA, Bという二つの集合に分ける上で
Aに空のものを許さず、Bに空を許すときに、任意のAは任意のBよりも上流にあるようなものの合計がsccの合計になる
類題としてはこれが挙げられていた。
こちらの解説ではA, Bに分ける方法のうち
BからAに向かう辺が無いような、Bの分け方がsccの合計という説明がされていた。
辺の数を数えるか、下流から何個グループをまとめられるかの違いで本質的には同じですね。
また、tournamentの場合は、辺の数関係の制約がなかったので
一つずつ頂点を追加して、現在の状態を注意深く計算しなくてよかったようだ
一般に、何かの状態を後から推定するのが難しい場合は、一つずつ構成する必要があるが、そうでない場合は後からすべて数え上げられることがある。
ABC-G - Increasing K Times
メモ
問題の形からT - Permutationを連想し
dp[i][k] := i個置いたときに、前回置いた数よりも大きい数が何個残っているか
として遷移しようとしたがうまくいかなかった。
O(N^3)になってしまった
permutationの場合は、各iについて大小関係が初めから決まっているので挿入が出来なかったが、今回の場合は挿入が効果的だった。
小さい順に見ることで、大小関係の制約を解決できるのは頻出なので頭に置いておきたい
例
