277.1

面倒なセット。自分が思った通りに実装するのは問題ないのだけれど、それが現実的な速度で動かなかったり、そもそも問題の要件を満たしていなかったり。

250

二つの配列が与えられた時、片方の配列からもう一方の配列に要素を移動することで、両方の配列の平均値が増加する要素はいくつあるか答えよ、という問題。

自分の配列の平均値よりも小さくて、相手の配列の平均値よりも大きい要素を数えるだけ。(こういう移動は最大何回できるか、という問題と勘違いして時間を無駄にした。)

500

.とSの出現回数が与えられるので、できるだけ多くのSが.と隣接するような文字列のうち、辞書順で先頭のものを答えよ、という問題。やたらと長い場合は最初と最後の50文字ずつを答える。

基本的にはS.Sというパターンをできるだけたくさん作る。.の数が多くて、Sが奇数個の場合は...S(S.S)*になり、そうでなくてSが奇数個の場合は(S.S)*Sになるという点に注意してgreedyに作成する。やたらと入力が大きいので、実際に文字列を作ると終わらない。(boolean配列で持っておいたら問題ないような気もする。)

1000

現在位置と目的位置が与えられ、道の配置が与えられる。目的位置に移動するまでに道を横断する最小回数を答えよ、という問題。

出現する座標の数がそこそこに多いものの、x座標とy座標について出現する座標で領域分割を行う。後は各領域間での遷移に際して、道を横断するかどうかを覚えておいて、ダイクストラするだけ。

ダイクストラをやると領域数の2乗くらいになりそうだったので、コストが1ずつしか増えないことを利用して、コストが増える遷移と増えない遷移の両方を覚えておくBFSをやってみた。この覚えておく作業を全部メモリに入れることはできないので、近隣二枚分を覚えておくようにしたのだけれど、swapじゃなくて毎回新規に作成するようにしていたら終わらなかった。(本当はqueueが欲しいのだけれど、遅いので配列で代用するので、usedな位置を覚えておくポインタをクリアするだけでいい。)後は入力を文字列のままで何回も処理したりしていて重いとか色々あった。