Close

2015年6月29日

ICPC参加記 – aLice

こんにちは、中澤です。

ACM-ICPC 国際大学対抗プログラミングコンテスト2015の参加記を書きます。

チーム名: aLice
メンバー:
snakazawa (私) 4年
taku 2年
tibimosu 2年

で参加しました。

takuが読解・考察、私がコーディング、tibimosuがペアプロ的な感じでコーディングチェック、という構成です。
A,B,C,Dと順番に確実に解いていく、という方針です。

チーム練習 (2月中旬~)

前回までの経験から、チーム連携に難があるということで、例年より早めにチーム練習を始めました。
ただ、大会一ヶ月前までは、チーム練習は2週に1回ぐらいしか出来ていなかった気がします。

追い込み(6月10日~)

このあたりから、ICPCの過去問を個人でも取り組み始めました(遅い)。

国内予選模擬(6月14日)

JAG国内予選模擬にaLiceチームで参加しました。
A, B までは早めに通せたものの、Cの実装でバグり、Dは解法ミスで2完でした。
やばいっって思って、以降、大会まで2週間もありませんが、練習量を増やしました。

リハーサル(6月26日)

いつもは工房で練習していますが、リハーサルはプリンターチェック等も兼ねて本番環境(実験室)でやりました。
案外確認しておかないと時間を食ってしまう部分があり、やってよかったです。

本番(6月26日)

A

全探索。
誤読とバグと緊張により、30分かかってしまいました。

B

全探索。
Aを解いている間にtakuがまとめてくれており、コーディングするだけだったので、10分で通しました。

C

構文解析っぽくやりました。
ここで、範囲外アクセスで数値がバグってて、WA出しました。
(範囲外アクセスでRE出してくれないの辛い)
この問題には30分ほどかかったので、ここまでで70分。

D

DP(コンテスト中には通していない)。
愚直にやると状態数多すぎて実質TLEするので、考察。
takuが、各商品のmod 1000の総和÷500が、最終的に獲得可能な最大の500円玉の数と等しいという法則を見つけ出し、そこから手持ちのお金の硬貨の内訳は考えなくても良いのでは?と考えてコーディング。
(今見ている商品 * 獲得した500円玉の数 * お釣りの総額) でdp配列を作ったらメモリが足りないと怒られたので、一次元目の要素数を2にして交互に見ていくアレを使ったら動いたので提出。
が、どっかでバグったぽくて時間足りずに終了。
後から見直したら、dpのアクセス部分だけでなく、商品のアクセス部分でもmod 2して0番目と1番目を交互に見ていたようで、それを直した出力と解答のdiffとったら一致しました。

結果

結果は3完56位8071s(ペナルティ+1200含む)、予選敗退です。
通常選考最下位チームが3完6881sなので、A問題を10分で通すか、WAを無くすか、Dを通すかすれば突破していたようです。
すごく悔しいですが、やはり予選突破の壁は高いなぁというのと、これが自分たちの実力なんだろうなぁと。

反省

次に生かすための反省点。

  • 言わずもがな、勉強量を増やす。
  • 場所も机もプリンターも、本番環境と同じ練習をして、本番の緊張感を軽減させる(A問題30分かかったことから)。
  • 頑張ればD通せる、という戦力だとどうしても安定しないので、E,Fレベルの問題も解ける頭にする。
  • assertを使ってエラーを検知する。

終わった後の飲み会で今後の活動方針について話し合う予定でしたが、タイミングが無くてやりませんでした。
コーチ兼監督のio先生にビールの”感謝”を貰いました。美味しかったです。でも突破できずにすみません。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA