ABC-D 65-68
今日は4問。
問題文読み違えてたり、発想力を要する問題で、確信のない方針のままコード書いてそれにこだわってしまったり。
以下、解いていたときのメモ。
ABC65
辺のコストがマンハッタン距離であることが効きそうか？各点から伸びる辺の数を抑えたい。
実装重そう。500点で出るか？
計算量同じだけど想定解法はもっとシンプル。
というか、よく見たらコストがマンハッタン距離じゃなかった。
ABC66
1…nのうちで一つだけダブっている。
連続とは限らない部分列の個数。
各kについてO(1) or O(log n)で求められないと無理。
重複要素が無ければbinom[n,k]の和で良いが、
1 1 2で長さ2だと 1 2がダブルカウントされる。
重複要素をxとしたとき、一般に下のような並び。
. . . . . x . . . . . x . . . . . .
重複が発生しうるのは、
・２つのxの間に挟まれた領域から選ばず
・xのうち一方のみが選ばれる
ような場合。
各 k について, binom[n+1,k]をまず計算し、重複するパターンをそこから除く。重複は、binom[n+1-len[x…x], k-1]個
600点にしてはシンプルな問題だった。
ABC67
塗れる部分木を稼いたほうが勝つ。
根が塗られた部分木はどちらか一方のプレーヤーに占有されるので、お互いにとにかくまず最短経路を通って潰しにかかるのが最適っぽい。
まず1からNへの最短経路を調べて、両端から順に塗っていく。最短経路長/2回目で塗れなくなるので。1, N のそれぞれから、相手の色に出会わない限りという条件のもとでdfsしてマスを数える。多いほうが勝ち。
最短路を塗り終わるのが先手番か後手番かは気にしなくていい。
経路の重みが同じなので、最短路は幅優先探索で求められる。
ACは一発で取れたがずいぶんとごちゃごちゃしたコードになってしまった。
結局の所、1とNの近い方に対応する色で塗れば良かったっぽい。
考察もう一段深めるべきだった。
ABC68
とりあえず、aiの制約を考えなければ [k]が候補。
k > 10^16 + 1000の場合にどうするか。
[n-1 + n*(k/n) -(k-(k/n)), n+ n*(k/n) -(k-(k/n)), ….]
としてみる。
つまり均等に引く。
kがnの倍数であればこれで良さそう。
k = 100; n=1
0 + k - (k - k)=k
n=2
1 + 100 - 100 + 50
n=3
2 + 99 - 100 + 33 = 34
34 -> 4 + 10
[34,34,34]は 96回...
n個から一回ずつ引く操作によって、全体が -1される。
よって、kがnの倍数であれば、全ての要素を n-1 + k/n にすれば事足りる。
問題は中途半端な時。
n=3, k=9
2 + 3 = 5
[5,5,5] -> (3*3) -> [2,2,2]
n=3, k=10
[5,5,5]を[6,4,4]に -> (3*2) -> [4,2,2] -> [1,3,3] -> [2,0,4]->[3.1.1]->[0,2,2]
n=3, k=11
[5,5,5] を[11,2,2] -> 3 -> [10,1,1] -> [7,2,2]->[4,3,3]->[1,4,4]->[2,1,5]->[3.2,2]->[0.3.3]->[1.0.4]->[2.1.2] で11回。
k%n個に+k%n * 3, それ以外に-k%n?
少なくともkが小さい範囲では正しそう。確証は無いがジャッジに突っ込んでみる -> WA。kが大きいときに条件を満たす配列が存在しないということがありそう。
実際、入力499999999999999999に対して空出力になってしまう。
想定解は、終了状態から構成していくというもの。
"これを発想するのは難しいですが、これが以上の条件を満たすことを示すのはあまり難しくありません。"
NPかな？？？？
k%nが重要というところまで気づいた段階で、ノリで一つの要素に押し付けようとしてしまったのが間違い。
N = 50として、
44 45 46 47 48 49 50 0 1 ....
のようにして好きなk%nを作れることに気づく必要があった。
kの小さいところでもう少し紙とペンで遊んでみるべきだったか。
