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。今回も水色に上がれなかった。。。