スポンサーサイト

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

2011 年度 ICPC 国内予選

2011/06/24 16:30 ~ 19:30
阪大某所にて。

チーム miso のメンバーとして ICPC 国内予選に出場した。
期間が空いてしまったのであまり詳しいことは覚えていないけど、参加記録を書いておこう。

Tags : プログラミング ICPC

予選を通過できるかは正直、微妙なところで、5 問目が解けるかどうかにかかっていると思っていた。

結果は、7 問中 5 問正解で 15 位。
通過圏内に入れたようでうれしかった。



以下、コンテスト中の思考過程とか。
そのうち AOJ にも問題が登録されると思うので、ネタバレ注意

A.
チームメイトが書いてくれた。
素数を列挙するだけらしい。
accepted.

B.
チームメイトが書いてくれた。
括弧の対応を見るだけらしい。
accepted.

C.
A と B を解いてくれている間にこの問題を読んでいた。
パネルの色を 5 回変えて、連結成分のサイズを最大にする問題。

問題文で 「左上の」 パネルの色を変えるように指定されていたけど、そこを読み飛ばしてしまって、任意のパネルの色を変えられるものだと思ってしまった。

そうすると、問題は一気に難しくなる。
探索空間が広すぎるので全探索も間に合いそうにない。

わからん。
ぐだぐだ。
コンテスト中は、まさか問題文を誤読しているとは思っていなかった。

先に D ができそうだというので書いてもらう。

D.
たくさんの円が重なっていて、上から順番にとっていく。
最適な手順で円を取るとき、最大いくつ取れるかという問題。

同色の円が 4 つまでしかないという制約から、全探索でも何とかなるらしい。
ぎりぎりまで最適化したら間に合ったと言っていた。
accepted.

この時点で残り 1 時間を切っていた。

E.
まだ C の誤読に気付かないので、E を読んでみる。
このペースだと、どうせ 5 完しないと通過できない。

ある条件を満たすように区画を分割していって、最大いくつの区画に分けられるかという問題。
問題文が読みにくい。 ( 日本語なのに )

「停電していないたくさんの区画に関する条件」 を 「停電している 1 つの区画に関する条件」 に言い換えると、問題が見やすくなった。
DP ( メモ化再帰 ) やるだけな気がする。
E なのにそんなのでいいのか? とは思ったけど、間違ってなさそう。

C.
ここでチームメイトが C の誤読に気付いてくれた。
全探索するだけだった。
微妙に実装が重い。

誤読しているときに書いていたコードを少し修正。
accepted.

E.
実装軽い。
ペアプログラミング
書いてるそばからバグをどんどん見つけてくれる。

コードはすぐに書き上がった。
accepted.

このとき、競技時間は残り 10 分くらいだったように思う。

F.
幾何。
インボリュート曲線みたいなの。ちょっと違うけど。
実装するだけっぽいので総がかりで解き始めたけど、間に合うはずがなかった。

G.
Dijkstra やるだけに見えるのだけど、多分何か見落としている。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。