スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

ICPC予選に参加してきました

本日はICPC 国際大学対抗プログラミングコンテストに参加してきました.
自分たちは1回生3人で構成されたHALmon(はるもん)というチームで参加しました.
京大マイコンクラブ以外の京大生もたくさん参加していました.

時間は16:30-19:30.3人1チームで1台のマシンを使って問題を解いていきます。

僕たちのチームはとりあえず3問通そう!!ということを目標にしていました.


結論を言うと僕たちのチームは2完,3問目が解けたところ(サンプルコードが通った)でタイムアップでした。
1つ以上通した215チームの中で126位でした.

結果はこちらから ICPC2014国内予選結果

まず,開始直後A問題に目を通しました.
僕が入力をとる部分を書いて,友人が問題を解く部分を書きました。


16:30-17:05
僕は問題に目を通さずに入力をとる部分だけ書いていて、友達がバグで悩まされたときにはじめて問題に目を通しました。・・・税込み、税抜きの問題で切り捨て切り上がりの問題があったようでバグに悩まれたそうです.
結局僕は問題に目を途中で通すも日本語の理解ができず明確なアドバイスができず,35分かかってAは解けず,僕がBが解けそうなのでAをその間に考え直してもらうことに.

17:05-17:55<br> A問題に友達が挑戦してもらっている間に,Bをみて解けそうだと思っていました。簡単にいえばぷよぷよとかテトリス的な。
縦H行,横5列のマス目の数、数字が与えられて、水平方向に3つ以上同じ数字があればその数字は消えて、その上にあった数字が下にストンと落ちます。
数字が消えなくなるまで数字を消す作業をし、消えた数字の合計を出力します。
2 1 1 2 4
3 1 3 2 2
2 2 2 3 3

2 1 1 2 4
3 1 3 2 2
2 2 2 3 3

0 0 0 2 4
2 1 1 2 2
3 1 3 3 3

0 0 0 0 0
2 1 0 2 4
3 1 1 2 2
こんなかんじで、消えなくなったらおわり。

Bの実装は私が全部担当することになりました.
まず,横5個のデータを与えたときに、同じ数字があったら-1をいれて点数をかえす関数kesu()をつくり
kesu()をH回行い合計点を返す関数kesuze()をつくり
消し終わった盤面に対して、落とす関数otosu()を作って、kesuze()が0点を返すまでkesuze()とotosu()を繰り返す、という方針でした。

紙の上で問題を見ていたときは、2048のシミュレーションとおなじで簡単に作れると思ったのですが、予想外のバグ(=と==のミスや、初期化忘れ)に悩まされたのと、kesu()の効率の悪さに時間を食われてしまい、結局50分かかってコードが動作。なんとか初めてチームとして通すことができました.

17:55-18:25
もともとAを解いていた友人が、僕がBを書いているうちに場合分けをしないことでバグが生じないことに気づいたらしく、爆速で書いてくれました。いろいろありましたが30分程度で通りました。めでたく2問通過。

18:25-19:30
Cを解いた方がいいのかDを解いた方がいいのか、友人たちの間ですこし意見がわかれました。そんななかDは2^20乗ほどでごり押しすれば解けることに気づき,18:50分あたりから3人で入力を作ったり、何度も呼び出される部分的な関数を作ったりしました。そして19:20分に個数に関してはサンプルが通り、「あと10分で通さないと!!」という気分に.
何万通りかのデータをデータに保持して、最後にソートして出力する。そして少しバグがでながらサンプルが通った!!・・・のが終了10秒後くらい。問題を提出しようとすると「提出できません」という旨のメッセージ。私たちのチームのメンバーは「はぁ」とため息をつきながら、終わりました。

先輩たちのチームは,5完だったり,6完だったり。やっぱりすごいな、と思いました。

アルゴリズムの勉強+それなりに実装しないといけない簡単な問題をバグなく素早く通す 修行が必要だと思いました。

あと、チームで解くときに、「サポートする」ことが必要だったと思いました。自分も問題文に目を通さなかったことがかなり反省です。。
A→B→Aと解くのにはロスタイムが多すぎました。
まあ、競技プログラミングはじめて数ヶ月で、ある意味頑張ったとはおもいます。

もちろんバグがでて何度も試行錯誤をしている所でもロスタイムはたくさんあったのですが、特に自分がちゃんとしようと思ったのはBの部分.

2 2 2 2 1のようなデータをもらって、消す(同じ数字が3つ以上そろっていたら-1を入れる)プログラムが、とても長く書いてしまったのです。
僕がかいたB問題のコード(恥ずかしい)


どう考えてもkesu()がヤバい()

yy1.png yy2.png
この部分をもっと簡潔にかけるとは思っていたのですが、焦っていて、考えるより何も考えずダラダラ書こう ってなって書いてました。
というわけで、明日くらいにもうすこしきれいに書いてみようと思います。
とにもかくにも、チーム戦っていいな、って思いました。
懇親会では、Aは多少時間がかかっても単純な方がいい、などいろいろとアドバイスをもらいました。

来年は4つ以上とくぞ・・・・!!

おつかれさまでした。
読んでいただきありがとうございました〜
スポンサーサイト

コメントの投稿

非公開コメント

検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QR
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。