大阪大学の方々による5時間コンテストでした
チーム決めPhase
@mi2uさんと会津大の方とチームを組ませて頂きました
ミーティングPhase
- エディタはgedit
- 言語はC++
- けしからんマクロは無し
- 「問題読み終わったよ表」を作る
- 私は最初にA問題を担当
コンテストPhase
- Aを読む。正整数Nに最も近い回文数を出力する問題(N+iとN-iの両方が回文数の場合はN-iを優先)。std::reverseを使いました。
- iの初期値を0にしなければならないところ、1にしてしまい、サンプルで間違えていたので書き換え
- あれ?なんで合わないんだろう? → コンパイルしてなかった
- B問題担当の@mi2uさんと交代する。僕が問題を他の問題を読んでいる間に、いつの間にか終わっていました。
- Dを読む。gotoと、それに対応するラベルのみからなるソースコードが与えられるが、そのまま実行すると無限ループになるので、できるだけ少ない個数のgotoを取り除き、正常に終了するようなプログラムに変更する問題。
- 貪欲で解いてみて、特に大きな間違いは無い感じだったのでsubmitするとWrong Answer
- しばらく考えてみると、反例を発見しました。サンプルが通るのにWrong Answerになる人は参考にして下さい。
8 goto A; goto B; A: C: goto C; D: goto D; B
- 行数的に考えてみると、探索なのではなかろうかということになり、会津大の方が実装することに
- 「なんか他に解ける問題が無さそうだね」ということで、私がJ問題を書く準備をする
- Dがうまくいかないということで、お二人に見守られながらJを1時間以上かけて実装する(時間かけすぎ)。回転テーブルのミスなどもありながらもAC
- 解けるとしたらDだよねということで交代。会津大の方が神がかった枝刈りを書く → AC
- 残り時間をsqrt(x2+1)の積分をしながら過ごすなど
解説Phase
- Dはジャッジ解でない方法でACしていたらしい。ジャッジ解は聞いてみるとなかなか美しいですね。
- Jは展開図上でのピースの移動の仕方をテーブルに直接書いてしまったほうが楽です。クソ真面目に面とピースの関係について考察する必要はありません。
- sqrt(x2+1)はなかなか厄介。ただし、この問題は数値積分でも解くことが可能だそうです。
感想
- 全体的に満足度は高かった
- 文字列sの逆向きの文字列tを作りたいときは string t(s.rbegin(), s.rend()); という作り方もあるそうです