立命合宿2013 2日目

1日目の様子はこちら

大阪大学の方々による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()); という作り方もあるそうです