kyos1704活動記

適当に考えたことや調べたことを垂れ流すものです。質問等ありましたらtwitter:@kyos1704 に質問してください。

夏休みのICPCチャレンジ部の活動

ICPCチャレンジ部

今日は２回生にqueueとstackを教え、
１回生に今年の国内のAを解かせてalgorithmのsortをできるようになってもらいました

追記

毎回書こうかなーとか思ってたのに全く書かなかったので

2回生
1.queueとstackが使えるようになってもらったので、幅優先と深さ優先探索を再帰なしで書く練習
2.ダイクストラを一応一回書いてみる
ぐらいをしました

なんかだいたいいつまでにこれこれはできるようになってるといいなぁってフローチャート（？）的なものが作れるといいかなあと思っています

SRM 585 の結果と感想

rating 1061->1117
良い感じ

easy

やるだけ

med

なんか微妙に複雑に見えたけど　
紙に書いたら別になんてことなかった
計算量も大したことなし

hard

にぶたんと組み合わせてうごうごしたら大丈夫っぽいけど
判定がめんどくさすぎて投げてしまった

ICPC 2013 国内予選 kyos1704@(++c)-- 参加記

ICPC国内予選に参加しました
紺青氏(@konjo_p) と　Aさん(仮名)と参加しました

結果：３問解いて61位でした。
感想：戦犯です！ゆるしてください！！！

準備編

紺青氏とAさんと話し合って週二回ぐらいなら練習できるんじゃねという感じになる

毎回数問問題を解く

環境になれるために私のパソコンを使った

AさんがA担当
紺青氏がB
私がC担当ということにする

解いてるうちに、CよりDのほうが行けるんじゃねという話になったけど
C解けないのはあれなので練習はCを解く

結局AOJの日本語で追加されてる問題の
AさんはAを全部
紺青氏はBを全部解けた

私は解けてない（だめじゃん

本番

以下　ここを参考に書いています　（@not_522 さんありがとうございます）
https://docs.google.com/spreadsheet/ccc?key=0Ao_ilfIsS8SodFliUTUyT3REYmJ1ZjBTOTJLWXE5Q0E#gid=0

開始

とりあえず問題印刷してる間AさんがAを読む（横から覗きこんでたけどよくわからない

印刷した問題が届いたので、私はincludeとかのあたりのライブラリを打ち込んでいく。

ついでにわかってることをAさんに読みあげてもらう。割と簡単そう。

A実装はAさんにまるなげする予定だったので、
input部分とか書いて欲しい関数とかを横から口突っ込みながら
私はC,Dを読む。

C意味がわからないぞ・・・・？

Dがおもいっきり素数なので素数ライブラリを用意しておく（ページめくっただけ

この段階でAさんちょっと詰まっているのでお話する。

比較関数が必要なことと、150*150ぐらいなら全部ぶん回せばいいことの了承を得る

書いたのでサンプル通す

バグってる

比較関数のなかでなんでかグローバル変数（入力）と比較してたので修正

A Accepted!!! (1732秒=28分)

すぐに紺青氏と交代する

C意味がわからないのでAさんに全部まるなげする。
設定意味分からないだけっぽい匂いがするので
サンプルインプットとアウトプットがどうなってるか説明できるようにしてくれと頼む

私はDを見る
素数テーブルとマップ生成さえ出来れば深さ優先探索するだけっぽいと思う（真っ赤な嘘

紺青氏とAさんに　A->B->D->Cで4完行けそうですとプレッシャーを掛ける（思えばここがフラグ

とりあえずDのマップ生成の法則を考える

向きを変えながら二回変わったら進む数増やすだけだなこれとか思って簡単そうと思う

余裕っぽいのでCの説明を受ける。設定めんどくさい・・・・

設定めんどくさいけどソートして足すだけっぽいねというふうな合意ができる

Bがバグったので交代

Dのために素数ライブラリをカタカタする

マップ生成のコードを書いている途中でBのデバッグ思いついたらしく

私がBのコードを変更する（席変わるより楽という主張により）

B: Accepted!!!! （4546秒=75分）

想定よりものすごく早かったので興奮した

Dのコーディングに入る

Aさんと紺青氏はCの解読をする

とりあえずDのマップ生成と深さ優先探索らしきコードが出来上がる

D:サンプルを通す→時間かかりすぎてヤバイ

えっ？？？って思ったけど余裕でO(n!)だったので間に合うわけ無いと思った
別に普通にメモ化すれば良いだけだったので（良かった！！！！！）
再帰をちょっと変更する

あとから指摘受けたけど　O(3^n）っぽい、計算量の見積もりできなさすぎてヤバイ

D:もっかいサンプル通す→通らない

通らないのわけがわからない（原因も思いつかなかった）
のでCの説明を受ける。

よくわからんけど書いてる図は木だよねと言う→了承を得る
お互いどうすればいいかわからないので構造体か何か作ってそこにぶち込むということで了承する

話をしている間にそもそもマップのチェックしてないことに思い当たる

D:マップのチェック 1 2がない

よくわからんけどマップ生成がバグっているらしいのでよく見る
Cが書ける状態なら交代したけどそうじゃないっぽいので実機上（良くなかった

この状態で残り時間が１時間切ったので焦り始める
C書く暇ないかもしれないと紺青氏とAさんに伝える

実装時間を大雑把に見積もってもらう
30分ぐらいで行けそうらしい

D:マップ生成のバグ発見→訂正→サンプル通らない

残り時間40分弱
Dのバグは不明

紺青氏とAさんに相談する
そもそもD誤読してる可能性もあるし
Cは実装詰まってないけど書ける部分はあるので
そこを書いてる間に詰まってないところ考えることにする

C:実装開始

タイピングのスピードは私が早いのでコーダーは私がすることになった
言われるがままにクラスを書いて、
どう実装するかわかってないところ以外を書き上げる

書き上がった時点で
まだ未実装の部分についてどうすればいいかはっきりしていなかったので
どんな機能が必要なのか聞く

行けそうなのでそのまま書くと主張する
時間もないのでそれしかないということで賭けに出る（構文解析部分です：ちなみに練習で一回だけした）

思ったよりすんなりかけた

C:サンプル通す→通らない

ちっちゃいバグがあった　修正

C:サンプル通った

残り時間とか気にしてる余裕は無いのでとりあえずデータ落としてサブミット

C:Accepted!!! （10028秒=167分）

うおおおおおおおおおおおおおおおおおおおおお
とおったああああああああああああああああ

ハイタッチ（成功）する！！！

とりあえず目標は達成したので喜ぶ（３完が最低ラインとか話してた）

Dが通るかもしれないのでバグを必死に探す
見つからない・・・・・

timeup

ちゃんとした感想

3完が最低ラインで4完したいですねって話をしていたので、
最低ラインは突破できた

4完という目標を阻んだのは私なので戦犯っぽい
（バグッたと思ってたけど普通に出力するものを勘違いしていた可能性）

そもそもD書き上がった時点で提出できてたら
アジア予選選出28チーム枠には入れていたし
20チーム枠にギリギリ入れていたかもしれなかったので
それはとても悔しい
（climpetさんたちのチーム（// ato de namae wo kangaeru）がヤバイ成績をとっていたので２チーム出られたかもしれなかった・・・

D書き上がった時点で二時間たってなかったんだけどなぁ・・・・


ということで、上を見ると悔しい思いが大きい大会になりました
Aさんも紺青氏も私もしっかり働いて、チームとして動けたのでそれはとても良かったです

そもそも大会前に私が問題解けてないし準備段階からだめっぽいですね・・・・

来年はclimpetさんたちのチームと私達のチーム両方でアジア予選に出られるように頑張っておきたいと思います

競技プログラミングの勉強方針について

新入生についてはともかくやる気とかモチベーションは十分だという人が実力を上げるにはどうすればいいかという話


競技プログラミングにおいて何を目的にするかという点が最も大事だと思う

チームとかでの視点ではいい記事があるのでこっち見たほうがいいかも
http://topcoder.g.hatena.ne.jp/iwiwi/20120608/1339162885

個々人がどうするか的な視点でみる

ここではICPCを目的にしているものとして考える


ICPCでは、ACしている問題数が一番のファクターであるので
時間内に解ける問題数が増えることが目的となる

ボトルネックとなりうるのは2種類あって
・時間的制約
・知識的制約
が考えられます。（おそらく一般的にこれは言える気がします

以下では国内予選突破程度を目的としている人を対象とします
（要するに私です）

国内予選突破は4完したらできるものとします。
（A~Dを解きたい）


・知識的制約に関して
AB問題に関して言うと、必要ないっぽいので割愛します
知識が必要な問題に限定すると
C問題はDP、D問題はグラフ系統の問題がよく出ます。（ﾎﾝﾏｶ
要するにその辺りの知識が全くない場合、B問題まで解いてACをもらったあとに
頭を抱える事になってしまいます。
知識がない場合は座っているだけになってしまうことが考えられるので、
勉強できるならしてしまいましょう。
（過去問を信じるならDまでで必要な知識はそこまで多くない）

このことを一般化すると、勉強しましょう（あっ



・時間的制約に関して
ABCDどの問題であれ、問題を解くために必要な時間は
・・アルゴリズムを考える時間
・・実装する時間
・・バグを潰す時間
の3つが存在します（もっとあるかもしれないけどとりあえず無視
多分これICPCとか関係無い気がするけどまあいいか

ICPCではPCを使える時間が限られているため、
アルゴリズムを考える時間を短縮することはさしあたって考えないとすると
（アルゴリズム考える時間短縮ってどうすりゃいいんだろう、だれか教えて）
実装してバグを潰す時間をできるだけ短縮することが目的となります。

この場合どのような手段で短縮化できるかを考えます

・・実装する時間の短縮
・・・書いてる間に迷わない（考えない）ですむようにする
・・・タイプ数を減らす
考えなくてすむようにするには、先に変数の名前を考えておくとか（いつも同じ変数を使うとか）
関数を小分けにして、一個一個を簡単にしておくとか

タイプ数は変数名ぐらいしかないかなぁ？

・・バグを潰す時間の短縮
・・・バグらせない
・・・バグを特定しやすくしておく

やっぱ関数わけるとかしか思いつかない
あとはバグりやすい実装方法しか思いつかないときは、
練習のうちに他の人のコードを読んでバグらなさそうな
わかりやすい書き方を考えてみるとかしておくとよい
どうしようもないときはその書き方を何回もやって慣れておく

特定しやすくするには、バグの内容が予想できる場合には
バグ検知のテストケースとか作っておく

うちの競技プログラミング部での後輩育成について

今日はタイトルのような話をしていました。

うちの部には後輩を育成するという機能が今までなくて、
各自勉強して、「生き残った人」がICPCに挑戦するという
なかなかにサバイバルな感じになっています

証拠に各学年ほぼひとりずつしかいないという燦々たる状況




今年に関していうと、一回生の勧誘という段階に関しては
十分に人は来てくれたと思われるのですが、、、


すでに一人しか来なくなってるのです
（よく考えたら別に教えてくれるわけでもないところにわざわざ来るわけもない）


少なくとも「部」を名乗っている以上、どうにかしなければならないなぁという話をしました
その時にこれは絶対に教えなきゃならないなってところのメモ



プログラムを作成するのに最低限必要な概念
・条件分岐
・繰り返し
・変数及び配列

言語、書き方に関しては調べるかなにか出来る状態にあれば良い

導入として数当てゲームを作成するっていうのをやるといいかもしれないという話をした
ある数を内部に持っておく以下のようなプログラムを作って
他の人の数を当ててみるみたいな感じ

int main(){
  int num=4;
  while(1){
    int tmp;
    cin>>tmp;
    if(tmp<num){
      cout<<"low"<<endl;
    }else if(tmp>num){
      cout<<"high"<<endl;
    }else{
      cout<<"yes"<<endl;
      break;
    }
  }
}

あとは

while(1){
　問題見る・解く｛
　必要な知識を調べる
　ACする
　｝
}

みたいな感じに持っていく




あとTwitterでのちょっとした話

ゲームAIからやるのはわかりやすいし良いかも @not_522 
@kyos_1704_p 今やってるのは, AOJのvol.100も含めた簡単な問題もセットに入れつつ,
 解くことの楽しさを感じさせる形でやってますかね.
 ぼくは後輩の活動自体には, 全く口出してなくて, 練習方法は任せてます.
 今の方法で競プロに興味をもつかは, まだわからない

 うちでプログラミング習いたての新入生を競技プログラミング好きにさせた
 という成功例はないような気がします.
 というか, 競プロにどっぷりはまってる人は, 立命では僕とあと1~2人いるぐらい

from @Respect2D
初心者向けなら、会津大の練習のDiv2とかが良いと思います。
新入生達はDiv2の方で練習をしていたりします。
ただ、教育を考えると解説が出来る人が欲しいなと思います。
@WinField95