自力AC。
とりあえず、答えの個数を聞くため、S={1, 2,..., n}、とし、全ての始点に対して質問しなくてはいけなそう。それらをメモしAとしておく。
その後、xが始点なら、A[x]=A[y]+1となっていて、かつx→yに辺があるものを探していけば良い。
のだが、このクエリ回数がn以下になることが分からず考え込んでしまった。
ちゃんと考えると、A[i]=kとなるiを一つ見つけたらk-1を探し始めれば良いため、このパート全体でn回質問すれば済む。
なので、全体でのクエリ回数は2*n回に抑えられている。
D. Chicken Jockey
解説AC。
結論からいうと、
・一つ前を倒して落下ダメージをくらわせるか
・順に倒していき、落下ダメージは1のみにする
かのどちらかになり、DPできる。
前者を使う場合は、後ろの方から倒していくことで、最大の落下ダメージを実現できる。
解説を見ても、この二通りなのが明らかという感じはしない。なので結構難しい。
0 件のコメント:
コメントを投稿