ICPCの裏側をちょこっとだけ
どうも、@bakamingです。
この記事は Competitive Programming Advent Calendar 2015 - Adventarの12日目の記事です。
お前誰だよ
僕は2007〜2010に現役でICPCに出場していました。
引退したはずだったのですが、その後もボランティアお手伝いとしてICPCに参加し続けています。
もう9年目になります。継続参加年数ではかなり上位の方に入るのではないでしょうか……。
関係者と話をするのを楽しみに、毎年参加しております。
今年のネットワーク配線の裏側
私は今回、ネットワーク配線の担当の一員として働いていました。
今年は特に、皆様にケーブルを踏まないようお願いをすることが多かった年かと思います。
皆様のご協力のおかげで、ケーブルスイッチ類が破損して故障対応、ということはありませんでした。
ご協力、本当にありがとうございました。
そこで、今回のつくば大会向けにどんなことをやっていたのか、少しだけお話ししたいと思います。
今年の配線準備は不安だらけでした。
ネットワーク配線を担当し始めて2年目になりますが、今年は特殊な年になったと思います。
去年は、現役時代にも何度もお世話になった、勝手知ったるオリンピックセンターだったので
詳しく設計などしなくても（と言っても去年もきちんと設計しました）
正直なんとかなるだろう、と思っていたのですが
今年はつくばでの開催ということで、全く知らない環境での挑戦でした。
問題点
加えて体育館での開催だったので以下の2つの問題がありました。
・スペースがかなり広いので、所持している資材ではケーブル配線が極めて複雑になる。
・講堂側の建物にも配線をする必要があるが、途中の扉をケーブルが通過するかわからない。
持っている資材が、完全にオリセンのようなスペースを想定したような装備なので
カピオのような設備に対応するためには、別の敷設方法が必要になります。
これを誤ると、敷設が複雑すぎて前日に敷設しきれなかったり、ケーブル長の計算
をミスして、必要なケーブルがないという事態になりかねません。
2つ目の問題は特に深刻でした。そもそもケーブルが扉を通過しなければ
部屋のレイアウト（スタッフ、ジャッジ等）を全て入れ替えなければなりません。
対応できました！
上記の問題を解決するために、幾つかの対処策を打ちました。
・体育館のケーブルは、3箇所程度で集線し、配線の複雑さを減らす。
・ケーブルの扉の通過具合によって、3パターンほどの部屋配置を考える
1つ目の対応が、今回かなり効いていて、敷設の際の指示をシンプルにでき
マンパワーを有効に利用することができたと思っています。
ただ、その代わり配線の束が太くなってしまうので、足元に気をつける
必要がありました。その点で今年は足元に関してのアナウンスが多かったと思います。
2つ目に関しては、結果的に杞憂に終わって、問題になる扉がほとんど存在しなかったので
一番理想的なパターンで敷設することが出来ました。
実は部屋配置はかなり気を使っていて、ジャッジルームに音が漏れないか
プリンターや風船音を選手に如何に聞こえないようにするか等、考慮点がとても多いのです。
用意していた最悪の案では、ジャッジ用PCとプリンターが体育館内に設置され
風船部隊がトイレへ行くのを遮るスペースにいるというとんでもないものでしたが
そのような案を取らずに済んだのは本当によかった…。
体育館内以外でも、様々なシステム向けにケーブルを伸ばしています。
扉を開け閉めできるよう、踏まれないよう、いろいろ工夫して配線しているので
来年お越しになった際には少し注目してもらえると幸いです。
今回使用したケーブルの中で最長のものは、50mのケーブルでした。
体育館のトイレ側の入り口付近のスイッチから選手用スペースの外周を通って
スタッフ用出入り口前のスイッチまで引っ張っています。
正直、これを切られたらプリンターが全停止するのでどうしよう…とかなり不安でしたが
皆様のご協力のおかげでなんとか無事に乗り切ることができたようです。
来年の配線がどうなるかはわかりませんが
どうか線を踏まないよう、ご協力を宜しくお願いします。
その他
他にもいろいろ裏話はあるのですが、今回はこんなところで。
明日は@enuemuenuemuenuさんです。
haskellにおけるincってなんだって話
何回かHaskellを学んでみようみたいなことを考えていて、ちょこちょこ入門をうたったサイトを見ていたりしました。
で、ずっと前からそうだったのですが、Haskellを学んでいる時に意味不明だった文章に以下のものがありました。
「add a b = a+bとしたとき、inc = add 1とすれば"inc"は1を足すという関数を返す関数」
何者だよ、関数を返す関数とは・・・。で、それに関して色々考えてて、自分なりにそれなりに納得したので
それについて書いてみようと思います。
本文を書く前に、この文章はHaskellどころか、関数型言語をほとんど知らないバカが書いています。
なので、Haskell等、言語を極められた方からすると、不正確、曖昧な表現があるかもしれませんが、あまり
怒らないでいただけると幸いです。それから、コレから書くことはとてもとても当たり前なことなのだと
思うのですが、あまりこういう書き方をした文章を見たことがないので書きました。当たり前じゃん！
何をいまさら！と思っても許してください。
さて、"inc a"について書く前に、そもそもHaskellってどんな風に計算を行っているのでしょうか。
ということを考えます。C言語などは、ある変数に数字を代入して、それを計算式でいじって計算を
行いますが、Haskellはおそらく違います（本当に違うのかは議論がある所でしょうが）。
端的に言うと「式に式を代入しまくって、最後に出てきた、式を答えとしている」
例えば「x=y+z」「y=1」「z=6」という3つの式が定義されていた時に
「xを計算してください」というプログラムが書かれたら
「x」→「y+z」（式をそのまま置き換えただけ）→「1+6」→「7」
日本語で書くとxにy+zを代入、yに1を代入、zに6を代入して、最終的に「1+6」が出てきて
「7」という答えが帰ってきます。
次にもうちょっと思考を変えます。ここからzの定義を抜いたらどうなるでしょうか。
「1+z」という式が現れて、それ以上計算できなくなってしまいますね。
しかし、これで良いのです。上記した通り、別に答えは値である必要は無く、式でも良いのですから。
「1+z」が答えになるのです。数学でも変数が答えに入ってることは別に不思議ではないです。
では、もっと変則パターン、「x=y+」という定義になっていたらどうなるでしょう。
「x」→「y+」→「1+」（ただ単に定義に従って置き換えただけ）
「1+」というのは、数学的にはとても気持ち悪いですが、まぁ数式に変わりはないので、
コレが答えだということに異論は無いでしょう。
最後のパターン、「x=y+」という定義のもと、「xzを計算しろ」と言われたらどうなるか、置き換えてみましょう。
「xz」→「"y+"z」→「1+6」→「7」
どうでしょうか。xzはかけ算ではと言われるかもしれませんが、ここでは演算子は省略できないものとしてください。
そうすれば、割合納得できる”置き換え”なのではないでしょうか。
ここで本題に戻ります。"inc"とは何なのでしょうか。答えは、置き換えると"add 1"になるものです。
プログラムの例を見てみます。
「add 1 2」→「1+2」（式をそのまま置き換えただけ）→「3」
「inc 2」→「"add 1" 2」→「1+2」→「3」
どうでしょうか、あまり変な感じがせずに受け入れられたのではないでしょうか。
「関数を返す」と言われるとすごく違和感のある表現ですが、単に置き換えたら良いです、と言われると
割合納得しやすいものなのではないでしょうか。
で、ここでHaskellのプログラムにおいて、「=」を置き換え規則だと見ると、結構すっきりすることが
たくさん有るのではないでしょうか。言いたいことはこれで全部です。
最後に重ねて言いますが、僕全然Haskellのこと知らないので、この文章の正当性は非常に怪しいです。
しかしまぁ、そこそこ感覚的で分かりやすいのではないでしょうか。
この文章が、今後Haskellを学ばれる方の一助になることを祈りつつ。
ではでは。
陸前高田に行ってみて
3月11日を迎えました。
この1年、幸いにしてあまり地震の影響を受けずに過ごせました。
節電を少し言われた位で、後はほとんど影響を受けなかったと言ってもいいと思います。
しかし、そんなレベルでは済まない地域が多々あったことは確かで
僕は少しそういう地域が気になって、実際に行ってみることにしました。
先に言っておきますが、別に悲しみを共有しようとか、そういう文章ではないです。
多分、実際見た感覚というのは重要だと思ったので、そのまま記録しようと思っただけです。
次に、文章の論理構成がむちゃくちゃです。
ただ思いつくままに書きなぐっているので。
それから、被災者の迷惑になるんじゃないかとか色々考えましたが、
少し時間が経ったら、東北に金を落とそうと思ったこともあり、行ってみることにしました。
2月29日、僕は、飛行機を使って仙台空港に降り立ちました。
この場所も当時凄い被害をうけていて、実際僕と同じ大学の方が何名か亡くなっています。
にしては、綺麗でした。重ねて言いますが綺麗でした。
あの時ほんとに人が死んだのか、というのが疑問なくらいでした。
実際、仙台駅周辺では、バスの路線や時刻が変更されていたり、工事してる場所がある等
何箇所か地震の被害を感じさせるものがあるものの、未曾有の大災害が起きた
という痕跡は、消えつつあるように感じました。
仙台は普通に観光可能でした。
青葉城にも行きましたし、美味い飯も食えて、言う事無しでした。
さて、問題の陸前高田です。
陸前高田には3月1日に仙台から日帰りで行ってきました。
未曾有の災害に会った場所ですが、現在はわりと簡単に行くことができます。
宮城交通と岩手交通が運行している、日中の長距離バスというのがあり
仙台と陸前高田を4000円で往復することができます。
朝、仙台を出発し、途中気仙沼を通り、陸前高田に行くルートです。
バスに乗って、出発したわけですが、気仙沼につくまでは、ほんと田舎道を走っているだけな感じでした。
ほんとに地震にあったのか疑問なレベルで、なんだ、こんな感じなら大丈夫じゃないかと思っていました。
実際、気仙沼市内にはいってもそんな状況はかわらず、気仙沼の駅前のバス停に停まった時も
なんだ、こんな被害だったのかとおもったのですが
地震の爪痕が残っていたのは、この先で、気仙沼の駅を少し海側に降りると
未だに津波でぼろっぼろの家が残っていたりしました。
そして、海岸沿いに出ると、それこそ、本当に日本なのかよくわからない光景が広がってました。
空爆でもされたのかというくらいぼろぼろな家、打ち揚げられた船等々
震災からほぼ一年がたつのに、未だに片付いていない場所が多々あるということを思い知らされました。
で、気仙沼を抜けて陸前高田についたのですが
はっきりいって拍子抜けしました。
なにもないのです。「災害っぽい」という意味では気仙沼の方が酷いくらいでした。
前日に雪が降ったこともあり、雪に覆われていた部分が多かったのですが、
本当になにもなかったです。
町が存在したということがまるで信じられませんでした。
このあたり一帯田んぼですと言われたら、そのまま信じてしまうくらいに。
いろんなところで奇跡の一本松というのが話題になったと思いますが
あれ、2km先から視認できるくらい、周りに何もないのです。
あるのは瓦礫でできた山だけ。
どうも陸前高田は気仙沼から先の大船渡へ行く、交通の要所になっているらしく
県道はわりと交通量がありました。
しかしそれ以外何もない。
一人で、陸前高田をとぼとぼ歩いていたのですが
その時に思ったことは、さみしいと感じました。
死者への弔いの気持ちとか、そう言うなのより先に、さみしいと感じました。
人が住んでた場所が、一瞬で吹っ飛ぶと、ここまでさみしい風景になるのかと感じました。
で、件の奇跡の一本松まで歩いて、手を合わせて、それだけで帰ってきてしまいました。
もっとなんかなかったのか？と聞かれても、答え辛いです。本当に何もなかったので。
言っておかなくてはならない話があって、これは陸前高田の海側の話です。
同じ陸前高田でも、丘を登った部分は津波の被害も小さく（といっても地震に被害は大きいですが）
今も普通にたくさんの方が暮らしていらっしゃいます。
そこに住んでいる学生さん（多分中学生かと…）が笑っているのを見た時
なんだかあったかいな、と感じました、海側を見ていて、さみしいと思った気持ちが和らいでいくのを本当に実感しました。
人って一人では生きられないわ、という謎の感想を得ました。
多分、陸前高田に行って、一番感じたのはこれだと思う。
人は一人ではさみしくて生きていられません。
なんだかよくわからない文章になりましたが、行った僕もよくわかりません。
けど、人のいない陸前高田の海側を見て、無性にさみしいと思ったことだけは確かです。
願わくば（そして現地の人が願うなら）、あの何もなくなった土地に
もう一度人が戻って、賑やかに暮らす日がもう一度来ることを、と思います。
そのために自分が何ができるかは、もうちょっと考えてみたいと思いました。
おわり
d3sxpにいた頃、意識していたこと
さて、Competitive Programming Advent Calendarの順番がやってまいりました。
何を書こうかなー、と思ったのですが、タイトルは見ての通りになりました。
これから話すことは、僕のいたチーム、d3sxpがICPCで闘う上で僕（と多分チームが）が意識していたことです。
・WAを出さないために
基本的に、WAを好きなチームはありません。
しかし、うちのチームは特に2つの意味で、WAを嫌っていました。
まず、WAを出すとテンションが下がって、全く問題が解けなくなってしまうこと。
そして、アジア予選の戦略としてのWA回避です。
2つ目は何を言っているのかと思われるかもしれませんが、重要なことで、
日本のアジア予選において、東大の直下の日本チームの解答問題数は団子で1問差程度でほぼ同問になります。
なので、世界大会を狙おうとするなら、タイムで勝つ必要があります。（現在は海外勢も混じってそんなに甘くありません。）
逆に言うと、落ち着いて、WAを回避していれば、多少各問が解く時間が遅くても、勝てると信じていました。
問題数で追い付けさえすれば、確実にタイムで上回るという状況を作りたかったのです。
WAを出さないため注意することは只一つ、チェック体制です。
うちのチーム、コーディングに入る時、必ず他の人の同意を得ます（アルゴリズム等）。
極力、1人でコーディングさせることはありませんでした。
1問に1人でアタックすることもほぼありません。
解答を投げる前には、コーダー含め2人以上の同意がなくては、投げてはいけない事になっていました。
1人でコードを書いた場合、必ず、投げる前に詳細な口頭説明を行います。
この過程が結構重要で、話しているうちに、適当に書いていた部分があらわになって
バグが大量に取れたりします。お勧めです。
・問題を解くために
問題を解くためには幾つか注意していた点があります。
1つ目は「問題を見逃さない事」です。
問題数で追い付くことを意識していたので、簡単な問題を見逃すことは避けねばなりません。
なので、うちのチームは、中盤、全ての問題を読むことを徹底していました。
それからもうひとつ重要な点があって、問題を共有し、難易度について、多人数で検討することです。
誰かにとって難しい問題が、誰かに取って簡単なことは良くあります。
また、問題難易度に対して意見が共有出来ていると、解答作成進行時に
変なコンフリクトが起きずにスムーズに行きます。
2つ目は「バグを共有すること」です。
実際問題、全ての問題をバグ無し、というわけにはいきません。
なので、いつかバグは出てしまいます。その時、極力2人以上で取り組みます。
少なくとも、1人しか知らないバグがあるという状況はつくらず、問題を共有します。
解答は正しいと思って投げるのですから、WAが出た時点で、後はトライ&エラーしかありません。
バグが取れるかどうかは、それこそ、5時間という短い時間では、運だと思います。
なので、極力多人数でアタックして、その運を少しでも上げるべきです。
3つ目は「落ち着くこと」です。
これが、チームメンバーが意識していたことで最も重要な事だったと、今になって思います。
皆さん、問題解いているときに落ち着いているでしょうか。
怒っていたり、過度に集中していると、逆に問題が解けなくなることは良くあります。
怒っていたりすると、落ち着けよ、と言えばいいのですが
過度の集中はなかなか厄介です。視野が狭くなるくせに、本人はなかなか気付きませんし、
静かにしているので、周りもそれに気付きにくいのです。
コーディングやバグ取りの時によく陥ってしまいますね。
なので、僕は、時々、意識的にコーダーに話しかけることを行っていました。
「どう？」とか「おちついてやってるー？」とかそんな軽い感じです。
集中してるんだから邪魔してやんなと思うかもしれませんが、
変にドツボにはまってPC占有されるよりはよっぽどましで、
それで「話しかけんな」とか「話しかけられたら頭こんがらがるやん」
とかなったら、逆にそれは冷静でなく、良くない証拠です。そんなことで問題は解けません。
「うんー大丈夫ー」という返事を出来るくらいが丁度よいのです。
問題を解いている間、こういう風にちょっと交流を持ってみるのはいいことだと思います。
試合中の良いリフレッシュになりますし。適度な集中を保つこともできます。
落ち着かなくてはいけない状況は他にもあります。
問題数で負けている時、アルゴリズムがわからない時等々…
しかし、僕は（多分チームも）、WAの時に語った通り
最終的にどうせ団子になるのだから、落ち着いていけば大丈夫大丈夫
と高をくくってやっていました。
落ち着く方法は他にもあります。タイムキーピングをして、適度な区切りを設けることです。
うちのチームでも、「○○したいけどいい？」「じゃあ△分以内ね」
みたいに、時間を区切ってテキパキやろうとすると、適度な集中が出来てよかったです。
以上が、チームにいた時に意識していたことです。
これを読んだ皆さんに参考になればよいのですが…
余談ですが、Competitive Programming Advent Calendarの企画で
僕のチームメイトの人が、記事を書きます。14日だったかな？
実は内容が似通っていて、彼はd3で取った戦略等を書くそうです。
というか、俺も彼が戦略的に何考えてたのか良く知らないので
（あまりじっくり話し合ったことも…ない…気がする）
楽しみでもあるし恐怖でもある……
考えてたこと全く違ったらどうしようｗｗｗｗ
内容を見比べてみると、面白いのではないでしょうか。
僕も、見比べて楽しもうと思います。
GCJJ出る人の助けになれば…
「
追記、本家へのリンクを張っておきます。
今回取り上げるのは、ここにある練習のＡです、他にも様々な情報があるのでみてみましょう！
http://code.google.com/codejam/japan
」
さて、明日あたりにGCJJが始まるわけですが、初参加の人が増えれば良いなぁ…と願って、
実際にどのように競技がどのようなもので、どのように参加すれば良いのかをまとめてみたので
ちょい長いですがよければご覧ください
さて、例は、今GCJJのサイトに上がっている練習問題のA問題としましょう
これを実際に解いていく過程で、どのように参加したらいいかを説明したいと思います。
まず、問題を開きます
読んでいきましょう、ふもふも、なんかスイッチが切り替わるわけですね
しっかし、良くわからんなぁ…よし、とりあえず、愚直にシミュレートしてみることにしましょう
さて、実際にプログラムを書いていくことにしましょう（今回はC++言語とします）
恐らく、こういう競技初参加の人にとって、2つほど疑問が上がるでしょう
入力って何？という疑問と、出力って何？という疑問です
GCJJでは、全ての入力はファイルから、出力もファイルに行われます
（ぐえーーファイル入出力！と言う人がいるかもしれませんが、これは後で解決します）
さて、入力の欄を見ていきます
ふむ、あるファイルが与えられて、入力の一行目にテストケース数
続くT行に2つの数字があるわけですね
つまり、こういうファイルが与えられるわけです（後で出てきます）
出力ファイルはというと、書いてあるようなファイルを生成すれば良いわけです
Case #hoge: ON or OFFと各行に書いてあるようなファイルですね
では早速書きましょう、かきかきかき
#include<iostream> using namespace std; int main(){ int tn=0; cin>>tn; // read test case number for(int ttn=1;ttn<=tn;ttn++){ cout<<"Case #"<<ttn<<": "; //output test number int n,m; int L[50]; //L[i]==0 => OFF, 1 => ON for(int i=0;i<50;i++)L[i]=0; //set OFF cin>>n>>m; //read two int for(int i=0;i<m;i++){ //simulate for(int j=49;j>=0;j--){ int flag=1; for(int k=j-1;k>=0;k--){ if(L[k]==0) flag=0; } if(flag==1){ if(L[j]==0)L[j]=1; else L[j]=0; } } } int flag2=1; for(int i=0;i<n;i++){ //check on or off if(L[i]==0)flag2=0; } if(flag2==0){ // output answer cout<<"OFF"<<endl; }else{ cout<<"ON"<<endl; } } return 0; }
というわけで上記のようなプログラムが出来上がりました
あれ？お前これファイル入出力じゃなくて、これキーボードから読んで画面に出すアレじゃん？
と思った方、魔法の構文がありますので、それは後ほど、コンパイルして、サンプルを手入力してみて
どうやら正しそうなので提出してみましょう
A-smallを解くのボタンを押すと、A-small.inをダウンロードするというのがあるはずです
それを押すと、A-small-practice.inというファイルがダウンロードされるはずです
これがインプットになるので、大切に扱いましょう
（中身は本文に指定されているような形式のただのテキストファイルです）
さて、いよいよ解答作成です、魔法のコマンドを入力します
a.exe < A-small-practice.in > A-small.out
これは、真ん中のファイルを手入力の代わりに入れて、その出力を後ろのファイルに入れろというものです
別に出力ファイルの名前はこれでなくてもよいのですが、分かりやすいのでこうしています。
さて、このA-small.outの中身をテキストエディタで見てみましょう
それっぽいファイルが出来ていますね、これはGCJJで覚えておくと便利です
リダイレクト、というOSの機能をつかっています、様々な場面で応用が利くので、覚えておきましょう
さて、これを提出してみます、提出ー
おお、正解と出ました、どうやら正しかったようです。
続いてLargeも…と行きたいところですが
実は、このままではだめです、理由は、試しにA-large-practiceをこのプログラムに食わすとわかります。
…終わりませんね、なかなか
今は練習セッションなので、提出に制限はありませんが、本番ではLargeはダウンロードしてから8分
しかも一回のみしか提出できないので注意してください（smallはダウンロードから4分、何回か提出はできます）
もっと早く動くプログラムを書かないといけないようです
ここで余談ですが、試しにループの中身が最大何回ほど実行されるのかカウントしてみましょう
テストケース数5000*K(10^8)*50*50で、とりあえずとんでもない大きさになります
経験のある人は、この数字が大体10^8以内になるように調整します
だいたいの目安なので、覚えておきましょう
余談おわり
もっと早いプログラムを書かねばならないようです
試しに、ON,OFFの変化を一回指を鳴らすごとに絵に描いてみましょう
なにか気付きませんか？そう、2進数です
スイッチのON,OFFという状態は、何回指を鳴らしたかの2進表記になっているのです。
よって、ある数字を2進表記で書いた後、Nbit目以下が全て1かどうかを判定すればよいです
これをもとに、Large用のプログラムを書いてみます、かきかきかき
#include<iostream> using namespace std; int main(){ int tn=0;cin>>tn; for(int ttn=1;ttn<=tn;ttn++){ cout<<"Case #"<<ttn<<": "; int n,m;cin>>n>>m; int ans=1; for(int i=n-1;i>=0;i--)if((m&(1<<i))==0)ans=0; if(ans)cout<<"ON"<<endl; else cout<<"OFF"<<endl; } return 0; }
だいぶ短くなりましたね、しかもわりと変なコードです（なぜ動くのかの説明はしません）
これでループの回数は5000*30で充分間にあいそうです
提出してみましょう…
a < A-large-practice.in > A-large.out
正解と帰ってきました、どうやら正しかったようです
と、ここまでが問題を解く流れです
少し加えて述べると
まず、smallは提出した時点で判定が行われる上、何回か提出が可能です
しかし、largeに関しては、1回しか提出チャンスがないので(8分の縛りもある)注意して下さい
正解かどうかも試合後に判定されます
ここら辺詳しくは、GCJJサイトのルールを見てみてください
予選はsmall-largeのセットを1問題分解けば決勝ですね！
皆さんのご健闘をお祈りしています！（といいつつ僕も落ちないよう頑張らねば…）
ではGood luck and Have fun!
ICPCのまとめ的ななにか
終わって2ヶ月近くたつのですか・・・
アメリカにいる間に書こうと思ってたのですが
なかなかまとまらず、日本に帰ってきたら案の定書きませんでしたので
一念発起して書いてみます
さて、大会の感想っていっても難しかったとかしかないのですが
今回の大会はほんと綺麗に順位がつくセットだったなぁ…という感じに思いました。
5問以下は普通のチーム、6問は解ける問題を確実に解いたチーム、7問以上はメダル
感想終わり
はい、これだけで終わりではいろいろアレなので、過去のことも含めてまとめ的なものを書いてみます
なんか4年ほどこれに参加してた気がするのですが
問題のアルゴリズム思いつくことって大切だよね？ということよりも
バグを出さないことって大事だねということの方が重要ではないかという事を思い知った4年だった気がします
いや、もちろん、練習に練習を重ねて、アルゴリズム力をつけることはとても重要なんですが
ICPCにおいて出る問題は、確実に他のコンテストに比べて実装量が多い
アルゴリズムが分かってても解けないことが圧倒的に多いコンテストだと思うのですよ
基本的にICPCの順位は、知っているアルゴリズム力、実装力に応じて、問題数という形でつきます
けど、それが狂う要因があって、それが、バグ
ここで言うバグとは、コーナーケースを含めた様々な要因がありますが
アルゴリズムの根本レベルでは間違ってなくてもWAが出るような場合です
誤解を恐れず過激に言うと、一度バグを出したら、それをACに持っていけるかどうかなんて運だと思うのです
だって、間違いだと分かって投げるやつはいないのだから、投げた解は正しいと思っている
だけど、それが間違っていると言われたなら、あとはトライ&エラーを繰り返すしかない
ここで、競技時間が「わずか」5時間しかないことを考えると、充分にトライ&エラーを繰り返すことは
おそらく不可能でしょう
しかも、ICPCは1WAにつき20分という途方もない重さのペナルティがつくので
WAを量産しすぎると、今度は、タイム差で逆転される
ここで、絶対に分かっておかなくてはいけないのは
現実問題として、大会本番で全ての問題を一発ACできるチームなんて、恐らくありません
だから、バグを出さないようにできるだけ振る舞うのと同時に、いざバグを出した時にどう対処するかが
とても重要な大会であると思いました
うちのチームの場合だと、どんなにアルゴリズムが分かってる問題でも
一人で書いていることは少なかったように感じます
一人で書いたとしても提出する前に、もう一人誰かに、コードを全て説明して、納得がいったら投げる
としていました、今思うと、すごくよく回っていたシステムだと思います
特に、コードを口で細かく説明するのはとても良いです
変数の意味もきちんと意識するようになるので細かいバグが結構とれたりします
競技プログラミングで、バグについて、くどくど言う文章がないようなちょっと書いてみました
なんか、書いてて思う、この文章、偉そうなこと言うなって多方面から怒られないだろうか…
まぁいいや
一応言っておくと、UT内の争いのような、日本の超トップクラス間の争いで
こんな悠長なこと言えるのかは、知りません
それから、やっぱりもちろんアルゴリズム力が競技の基本なので、皆一緒に頑張って修行しましょう
とにもかくにも、4年間のまとめは、バグ出さないって大事だねってことでした、まる
ああ、それから最後にこれだけは言っておかないと
チームメイトの二人へ、見ているか知りませんが（超高確率で見ないでしょう）
WFの帰りにも言いましたが、楽しい4年でした
ほんとに楽しかったよ？
競技中（競技中以外でも多分）に俺にキレたくなるような場面は多々あったと思いますが
皆さんがぐっと我慢してくれたおかげで、楽しく終わることができました
僕がチームに大きく貢献できたのかについてはとても自信がありませんが
微量くらいは貢献できたと信じています
横でコードを見ているのは、とても勉強になりました
本当にありがとう
おわり
GT5 国内A-8と国際C-1ゴールドについてのちょっとした攻略
この二つはやたら手間取ったのでちょっとした日記をかいてみる
一応、ドライバー視点、MTでやってます
TCSがレベル5、ABSがレベル1です
・国内A-8 シューマッハ―5
最初のコーナーをどうやって抜けたらいいかが問題なのは模範を見ればわかる
つまりは速度を維持したまま方向を変えたい
で、最初の左コーナーは、進入前に右手に縁石があるが
進入前に軽く右に車体を振り縁石を軽く踏んで、その後左に切り返してやると
車体が上手く左を向いてくれる
車速は忘れてしまったが、140弱で抜けられた・・・はず
あと、左コーナーは、左側のタイヤを縁石の内側に入れるくらいインに切り込むのが良い
これで13秒795…ギリギリすぎるだろっていうツッコミはなしで…
・国際C-1 1000mで止まるやつ
これ、かなり邪道かもしれませんが…
まず、最初レブリミット少し前くらいまで回転数を上げて起き
スタートと同時に全開
2速、3速、4速とギリギリまで粘ってシフトアップ
その後、225km/hの時にフルブレーキ
と同時にサイドブレーキも引く
で、滑り始めるけど気にせずフルブレーキとサイドブレーキを維持
100km/hを下回ったくらいで今度はサイドブレーキを離す
これを忘れると逆に後方に吹っ飛んでいってしまう
つまり、高速域からのブレーキにのみサイドブレーキを併用する
細かなタイミングはスタートの成否にもよりますが
225からフルブレーキでシルバーは取れるようになるはず
あとは225kmブレーキ+サイドから車速落ちてきたらサイド離すで
コンマ7台が出ればあとは経験を積み重ねたらオッケーです
これで26秒557でした…
やっぱサイド使うのは邪道かなぁ…と思ったのですが
むしゃくしゃしてやった
困っている方の参考になれば幸いです
