2008 Round2

25点とかいう微妙なスコアで通過。ほとんど全員が解けている問題を取りこぼさずやるとこんな感じ、という典型だった。まぁそれはそれでいいんだけど。

A

二分木のノード上にANDないしORゲートが並んだ回路の最終的な出力を満たすように、交換可能なゲートを交換するときの最小個数を求めよ、という問題。

要は、自分のゲートを変えるか右の子を変えるか左の子を変えるか、というのを実装するだけ。時間かかりすぎた。

B

(0,0)から(N,M)までの格子点上に3点選び、大きさがA/2になる三角形の頂点座標を答えよ、という問題。

3乗ループ回して色々最適化したら間違えたっぽい。実際には(0,0),(1,M)の二点を固定して考えていいらしい。確かに最大値はM*N/2まででそれまでの全部の値をとりそうな気はする。

C

三次元空間上の各点から、特定の点に向けて電波を出す必要がある。電波の最大強度を最小にするようにその点を決定せよ、という問題。

電波強度でバイナリサーチするらしい。届く範囲が立方体になるので交差判定とのこと。軸と45度ずれているっぽいが。

D

ある文字列についてk文字ずつをあるPermutationで並び替えてできる文字列を作成する。このときできる文字列のうち、隣接する文字が一致する数を最大にするものの一致数を答えよ、という問題。(RLEで圧縮する時にいいものを選らべ、と問題には書いてある。)

Permutationを決定すると時に、今までの決定からDP的に組んでいけば良い、ということらしい。実際にはもっと複雑なことをやらないといけないらしいが。