スポンサーサイト

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

2011 年度 ICPC 模擬国内予選

2011/06/12 14:00 ~ 17:00
阪大某所オンサイト。
チーム miso で ICPC 模擬国内予選に参加したので、簡単に記録しておこう。

Tags : プログラミング ICPC

毎年、国内予選の直前に開かれている、OB/OG 会が主催のコンテスト。
本番とほぼ同じルールなので、ここで上位が取れれば本番も通過できる可能性は高い。

結果は、7 問中 4 問正解で 11 位。
4 冠したチームの中では下のほう。
ただ、諸事情があってチームの実力を出しきれなかったので、本番ではもっとやれるはず。

上位 10 チームは合宿に呼ばれるらしい。
合宿行きたいな。
そもそも、通過できないと話にならないけど。



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

A.
qwerty キーボードで文字列をタイプするときに左手と右手を何回変える必要があるか。
やるだけ。
'y' を左手で打つとしてしまって、30 秒ほどバグった。

B.
通れないマスがある六角形座標で t ターン以内に到達できるマスの数はいくつか。
BFS やるだけ。
チームメイトが書いてくれた。

C.
CAPCOM の某有名ゲームっぽい設定で、全部のステージを攻略するのに必要な最短時間を求めよ。
bit DP やるだけ。
なぜか最初、priority_queue で Dijkstra っぽくやろうとしてしまった。ほんとばか。

D.
四則演算で演算の順序を自由に決められるとき、何通りの答えが得られるか。
構文解析 + 実装。
チームメイトが書いてくれた。

これをやるだけと言える実力はまだない。
再帰で構文解析しつつ、同時に括弧のつけ方を全パターン試していく。
括弧付けの総数としての Catalan 数の漸化式をつくるときみたいに、最後に行う演算に注目して、その左右で再帰的に分割する。
特別なデータ構造は使わずに、文字列のままやった。
最悪ケースで 10×10! 回くらいのループが起こって、さらにその中で std::set をいじっているので実行時間が心配だったけど、意外にも一瞬で終わった。
全テストケースをあわせて 2 秒くらい。

E.
幾何。ハムサンドイッチカット。確率。
謎。
直線をうねうね動かしていくのかなぁ、とか。

F.
辞書にある文字列を結合して、季語が 1 つだけ入った、決められた長さの文字列を作る。
謎。
DP らしい。

G.
最初から読む気もなかった。



安定して予選を通過するためには、E. F. を解けるくらいの実力がいる。
本番までに絶対復習しておくこと!!
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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