ABC117
また間が()
A - Entrance Examination
T/X
B - Polygon
max(L) < sum(L) - max(L)
問題文に答えが書いてあるような状態
C - Streamline
M<=Nの時、0
そうでない場合、座標間をM-N回移動する必要がある。
それを最小にしたいなら、Xをソートして隣り合う座標間の距離を求め、
その距離をさらにソートして小さい方からM-N個の合計を求めればよい。
D - XXOR
Cが簡単だったのでナメてたらハマった。
まずは2進数を1ビットずつ数にすることを思いつく。
そして、多数決で少ない方をXの該当桁のビットにすればよいこともすぐわかった。
ここまでは公式の解説と同じことをしているのだけれど、X<=Kがうまく処理できなくて80分試行錯誤しつづけても終わらず。
Xの各桁のビットを1にする場合、増えるXの数値と、増えるf(X)を求めて大きなナップサック問題にできないか?とか考えていたのだけれど、0にする場合の基礎点の処理(上位桁に1が存在しないとその0の桁の数値は適用できない)などの問題があり、正しい解を求める方法にたどり着けなかった。
ということで未提出。
結果は532位で+29の1193。今回も水色に上がれなかった。。。