TCO 2010 Qualification Round 1 (本番)

キャンセルになったのを24時間後にやったヤツなんだけれど、参加していないのでやってみた。抜けるだけなら...、という感じ。

250

0と1からなる文字列を、隣接するもののスワップ処理をして昇順か降順にソートしたい。最小何回のスワップで実現できるか、という問題。

昇順の場合、0を左に寄せるとして、一回のスワップで一個左に移動するのと、0と0のスワップは起こらないのと、を勘案すると、0を見つけるたびに左にいる1の数だけスワップしてやればいい。降順の場合は逆。

多分もっとクレバーな解答があると思う。

500

上下左右に移動する命令を持つロボットに、複数回同じ命令列を投入したとき、ロボットが通過したマスの数を答えよ、という問題。

何回か繰り返していくうちに、追加で通るマスの数は一定値になるはずなので、適当な回数テストした後は増分だけ考慮すればいい。

1000

等差数列、等比数列、ランダム数列、が与えられるので、N番目の要素を答えよ、という問題。

バイナリサーチと誰かが言ってた。ある値以下の数がいくつあるか、というのは比較的簡単に求まるので、N以上個ある最小の値を求めてやればいい。