今週の練習会

ICPC

今週はこのような理由で東京に出払っていたので、
私は一人で東京から参加、あとの二人は京都から参加という
チーム内対決が実現した。
…負けました。
自力で英語を読むという時点で地獄が待っているのは目に見えていたのだが、
やっぱり地獄なのだった。


問題セットは http://acm.pku.cn/JudgeOnline/showcontest?contest_id=1173


軽く各問題について触れておく。

  • 2719 どう見ても簡単です。
  • 2713 どう見ても嫌がらせです。問題自体は超易。
  • 2718 全部調べて解いた。調べ方を工夫しないと間に合わなかった。あとでもっと速い方法があることが分かった。
  • 2717 どうみてもDP。問題の仕様をたくさん読み落として(というか、読まずに解いて)11回も間違った。ちゃんと読めば簡単。

他の問題は時間中に読めなかった…。
以下、本日のチームでの復習による成果。

  • 2714 ベクトルを順方向、逆方向に決定する方法は180度ごとにまとめても最適解をもらさないことが分かれば実装するだけだろうか。私はx,y軸方向のみに最適化してそのどちらかが最適解であると思ってそれで実装したら通らなかった。今日K氏に反例を指摘されたのでこれは誤りであることが分かった。
  • 2715 練習会でのGNCの人の言うところによるとイテレーションを忠実に計算するとdoubleの桁落ち誤差が蓄積して正しい結果が出ないということだったのだが、私にはどうにも計算式を見ても誤差が蓄積するようには見えなかったので、今日普通にイテレーションするプログラムを書いて送ったら普通に通った。うーむ…。ちなみに、漸化式を数式的に解くととても大変なようで。なぜか実行速度もあんまり変わらず。
  • 2721 英語が難しくて、何を計算したらいいのかがさっぱりわかっていなかったが、実際のところは簡単な問題のようで。特に言えることはなし。
  • 2720 この問題も時間内には読んでいない問題で…。問題を聞くと、どこからどう聞いても難しい問題には聞こえない。M氏のコメントには"最難問か"とか書いてあって困惑。問題は"a^(a^(a^(...))" mod (10^n) をというシンプルなもの。とりあえず自分のカンを信じて実装してみるとサンプルが大体あってて、微妙に間違ってるような感じ。なんで間違っているかを考えるにつれて私の最初のカンが大きな見落としを含んでいたことに気づいたが、それでも部分的に正解しているという事実から私はとんでもない(？)整数の法則を見出すことになって、結果的に最初に書いたソースを少し変更することによりアクセプトさせることに成功した。できたものは簡単なアルゴリズムで、速度的にも申し分ない。さらに、図らずしもCode Length最短をマークした。アルゴリズムの詳細については明日あたりに書くかもしれない。
  • 2716 一見易問。実は難しい？普通に書いたらTLE。効率の良い実装方法は分からない。通ってない。


というわけで、今回はなかなかに興味深い問題が多かったように思う。
あと、やはり一人では駄目だということを痛感。
目となり耳となり頭となる人が居てくれないと自分の力が全然出せない。
うちのチームは型にはまれば強いと思うので、
なるべくいい状態にもっていけるようにしたいところだ。