Hatena::Grouptopcoder

(iwi) { 反省します

TopCoder: [[iwi]] / Twitter: @iwiwi

 | 

2012-06-08

ICPC のチーム体制について

22:41 |  ICPC のチーム体制について - (iwi) { 反省します を含むブックマーク はてなブックマーク -  ICPC のチーム体制について - (iwi) { 反省します  ICPC のチーム体制について - (iwi) { 反省します のブックマークコメント

チーム戦である ICPC において,チームであることをどのように生かしていくのが良いかについて私見を殴り書いておきます.

ICPC で良い成績を残すためには,各メンバーの力も当然超重要なのですが,一方で,チーム体制も非常に重要だと思います.特に,チーム体制は,あんまりちゃんとやっていない所も多いと思う(例えば我々も昔は酷かった)ので,逆に,そこをちょっと強化するだけで,ぐーんと良くなる可能性もあると思います.

言いたいことは,凄いシンプルで,ICPC ではキーボードを触っていない人が何をするかが非常に重要」ということです.

これは,決して我々がメダルを獲得したから我々を見習え,ということを言うつもりのエントリでは全くなくて,我々の反省や,世界大会で強いチームを見て思ったこと等も含まれています.もう観戦の立場ですが,これを見てもらって,皆のレベルが上がり,国内予選・地区予選でのレベルの高い戦いが見れたり,世界大会で日本チームが健闘する様子を見れたらなあという思いで書いています.



ボトルネックは PC という前提

まず,前提としたいこととして,ICPCボトルネックは基本的に PC」ということがあります.

ICPC は,3 人居るが,PC は 1 台しか与えられないというケチなルール.問題は,実装量を稼ぐように設計されているので,大抵,「解法の分かる問題がなくなり,キーボードに特に触れずじっとして終わる」というケースは少なく,「これもこれも解法が分かる,分かるけど組み終わらないよぉおお」という状態で終わります.*1



ICPC で目指すべき効率とは?

というわけで,できるだけ素早く問題を片付けたい.それ,別に普通のプログラミングコンテストと同じじゃん,と思うかもしれませんが,明確に違うのが,キーボードを触っていない時間なら贅沢に使っても良い」という点です.

ICPC は問題を速く解くコンテスト.なのだけれど,「自分が問題を見てから Accepted を貰うまで」を速くする,というのは ICPC では追求すべき効率ではない.正しくは,チームとして問題を解くことに関してどれだけ高い効率が実現できるか,それが ICPC で競っている物.

で,その 2 つが具体的な差に繋がるのは何故かというと,普通のコンテストと違って,「キーボードの前に居る時間」と「キーボードの前に居ない時間」があるから.先程も言った通り,大抵ボトルネックは,キーボードの前に居る時間.従って,いかに「キーボードの前に居ない時間」を使って「キーボードの前に居る時間」を減らせるかというのが,成績を大きく左右すると思います.そして,そこが ICPC の面白さだと,数年やった頃からやっと分かってきました(遅い...).



それを実現するための行動

ここは,チームによってかなりやり方が違ってくるところなんかなあ〜.


1. 解法を考える

超当たり前ですね.解法は,PC がなくても考えられます.*2

この時,「解ける」という事が分かったからといって,解法を考えるのは終わりじゃありません.解法を詰めましょう.

まず一番大事なのが「もっと (遥かに) シンプルな解法はないか?」ということ.自分たちだけ回り道な解法を取ってしまい,コーディングに使う時間を大損してしまうと,一気に差を着けられてしまいます.他のチームが解いている時間とかも参考にしましょう.

特に,ICPC で多い,幾何問題は,解法の幅が広く,選択によってかかる時間がかなり変わってきたりする.例えば,この問題三次元多面体を切断してゆく方針だとかなり大変な実装になるが,数値積分を用いて計算すると本当に少しの実装量で通る.

そうでなくても,時間があれば,解法をできるだけシンプルにして,コーディングの時間を減らしていきましょう.ここでいうシンプルさの目標は,コード量が少ない,だけでなく,バグが出にくいというのがあると思います.例えば,場合分けが多くなったり,微妙な ±1 が入ってくるようなコードになりそうなら,そういう部分を避けられないかを考えたり.この辺は練習で感覚を養っていくところかもしれません.


2. 紙プログラミング

解法を考える延長として,コードのレベルでどのように記述するか考えていくと,さらにコーディングの時間を減らしていけます.極限は,完全にコードを紙に書いてしまう紙プログラミング.これ別に冗談じゃなくて,PC が相当あかなくて,特に他に考えておかなければならない問題も無くなると,しばしばこうなる.

ただたいていは,PC があくまでの時間の兼ね合いで,効果が高いところからやっていく.例えば,以下みたいな点かなあ.

  1. ややこしい場合分けが多い場所,添字が難しい場所,より一般には,アルゴリズムの中心になっている場所
  2. どういう変数を作って,データをどのように持つか,あと変数
  3. どの部分を関数に切り分けるか,関数引数は何かとか(特に再帰関数

とにかく,PC の前で手が止まっちゃいそうだと思う点を潰していく.例えば入力読むとことか,普通に整数並んでるだけだったらマジでどうでも良いので優先度最低.

「1. 解法を考える」と 「2. 紙プログラミング」は,割と近いところにもあるんだけれど,明確に境界がある場合もある.それは,解法を考えた人と実装する人が違う場合ですね.なので,コードを詰めるためにも,その問題を誰がコーディングするかは早めにちゃんと決めないといけないわけです.


3. ペアプログラミング

一人がキーボードを触り,もう一人がそれを横で見て,ツッコミを入れる.これもこれで,キーボードを触っていない時間で(他人の)キーボードを触っている時間を短くするための手段です.

ペアプロはこれはこれで,やってみると意外とミスが見つけられる.「あれ,サンプル通らないなぁ何処が間違ってるんだろう」となってprintf をいれまくったりして消費する時間の期待値を,ツッコミ役を置くことで減らそう,というのがペアプロの意図ですね.あとは,悩んだ時に相談したりして,実装の洗練度も上がるかもしれない.

特にいわゆる「ペアプロ」は,ツッコミ役も完全にコードを理解しながら,2人でコードを創り上げていくスタイル.ただ,これは,コーディング役は結構先まで考えているのに,ツッコミ役からの「これどういうつもりなの?」という質問に答えなければいけなかったり,「こうしたほうがよい」「いやこうのほうがいいだろ」という議論になったりと,ロスも少なからず発生する.

別のスタイルのペアプロとして,ツッコミ役は「追っかける」ということにして,書かれたソースコードのチェックを行う,というのもあり得るのかもしれません.


4. 紙デバッグ

ICPC では必ずソースコードが印刷できます.デバッグは,PC 上で printf をいれまくったりしてやる方法もありますが,印刷されたソースコードを用いて紙面上で行うことにすれば,効率は下がるかもしれないものの,PC を開けることができます.

Wrong Answer になったソースコードを印刷して交代というのは,割と普通に行われているけれど,それだけじゃなくて,「サンプルが通らなかった瞬間に印刷して交代」というのもあり得るというのを念頭に置くべきだと思います.printf したくなる誘惑があるかもしれないけれど,さっきも言った通り,速く Accept を貰う事よりも全体としての効率を上げる事が重要なので,そのほうが良い場合もある.

また,提出する前に印刷してチェック,というのも,不安なソースコードであればやると良いと思う.




それらを組み合わせてのチーム体制

どういう風にやっていくのが良いかは,当然,チームのメンバー構成によると思います.以下は自分が想定できる感じの範囲内での自分なりの意見です.


コーダーが 2 人以上居るチームの場合

世界大会での上位チームの動画とか見てても,コーダーが交代しているシーンが頻繁に見られます.自分も,やっぱりコーダーは 2 人以上にするのが有利だと思います.

僕の意見としては,(同じような個人力なら) ICPC で最も差がつくのは,「1. 解法を考える」「2. 紙プログラミング」をどれだけ紙上でうまく出来るかだと思います.それをちゃんとやれるようになると,コーディングの時間は本当に半分とかになる.(体感)

なので,コーディングは,同じ人が連投するのではなく,代わりばんこ等にするよう意識できると良いと思います.連投がいけないというより,ちゃんと詰めてない状態でコーディングをするのがいけないわけですが,別の人がコーディングしている間に詰めて次のコーディングに備えて終わったら飛び出してドババババー,ということを繰り返すのが良い循環だと思う.ただ,中で力量に大きな差のあるチームだと,ここが難しいですね.

岩田は,この点については,「詰まるたびに交代する,頻繁に交代する体制はどうか」と言っていたけれど,自分はこれは疑問で,交代はやっぱりそこそこバタバタして面倒だし,あーあの紙どこ〜〜とか,コストあるし,事前にちゃんと詰める練習をしておけば,コーディング中に詰まることはなくせるから,そのほうが良いと思う.もちろん,想定してなかったことが発覚して詰まったりしたら交代すべし.それから,「とりあえず切りのいいところまでできている」とかで PC が開いていたらそこまでコーディングするなどは勿論よいとおもう.

ペアプログラミングは,自分的には,紙作業に比べると効果が低いと思っています.(それどころか悪くなっていることもあると思うし)まあ力量によっては,一人じゃバグりまくって解けないような問題を,ペアプロなら通せる,みたいなの,あるのかなあ.しかし,バグという意味なら,途中まで終わったら印刷してソレをじっくり読んでもらう,とかでも良いはず.相談してコードが良くなる,というのも,できれば,PC の前で相談なんてしてないで,悩ましいところを予め PC に行く前に相談できればそのほうが良い.


コーダーが 1 人のチームの場合

コーディング速度に大きな差があったりすると,コーディングを担当するのはメインの 1 人だけ,みたいにしているチームが結構ある気がします.繰り返しになってしまいますが,僕的には,多少の力量の差があっても,交代をして,コーダーが自分でコーディングを詰めておく時間を持てるようにする方がチームとして効率が上がると思います.

ICPC は実装量が多めの問題セットになっていることが多く,結局実装がボトルネックになってくるので,いかにキーボードの前での効率を上げるかが大事.コーダー 1 人だと,彼が 1 問コーディングを終えると別の問題を渡されてまた直ぐにそれに取り掛かれとなるわけですが,そうすると,1 人コンテストでかかってしまう実装の時間と似たような時間がかかってしまう.ICPC では,それは不利だと思います.(まぁ逆にそこまで分かった上でなおメインコーダー 1 人に頼ったほうが良いチームというのもあり得ると思います)

非コーダーを何に使うかですが,問題文を呼んでもらう,解法を考える,デバッグしてもらう,だけじゃなくて,多少なりとも詰める部分もやってもらえるようにできると良いですね.例えば,出てくるであろうちょっとした計算式を予め書いておいてもらうとか.



まとめ

随分と長くなってしまいました.しかもなんか割とフツーのことばっかりになってしまいました.まあいいか.

最後に言いたいことがあって,それは,チーム戦は超楽しい,ということです.

チームメイトがコーディングしてると PC 触れなくて暇だし,個人戦のほうが楽しいわー,とか,本当のことを言うと,僕も思っていた頃がありました.

今では完全に違います.いつからか,チームとしての体制がしっかりしてきてからというもの,暇なんて感じることはほぼ無くなりましたし,個人では考えられないような速度で問題を捌いていくことができるチーム戦が,とても楽しくなりました.

皆様もぜひ,楽しいチーム戦ライフを!!!!!!!

*1:この辺,あくまで本番の ICPC のセットについて話をしていることに注意.例えば ICPC 練習用のセットじゃなかったり,そういう練習をさせようときちんと意識された練習セットでなかったりすると当然この限りではない.

*2:実験をしてみると知見が得られる,みたいなのも有るといえばある.わかんないけどそういうのだと思ったらそう勇気を持って言い PC を貰う必要がある.それから,探索系っぽくて,根拠はないがやってみたら速そう,みたいなのも,言い出して PC を貰いに行きにくいが,ICPC では結構そういうのがよくあるため,そこは勇気を持って言っていく必要がある.

 |