スポンサーサイト

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

JAG Summer Camp 2014 Day 4

10:00 ~ 15:00
5 時間で 10 問
阪大・東工大の人たちのセット

オンライン参加
久しぶりのオンラインコンテストは楽しかった

結果 : http://jag2014summer-day4.contest.atcoder.jp/standings
ABC--F---- の 4 AC で 16 位。
平凡な結果だった。

後ろの方のおもしろそうな問題に手をつけられなかったのは残念。

以下、コンテスト中考えたこととか。
こういうの書くことにも懐かしさを感じる。

A : 山手線
十分多い回数ループを回してもまだゴールに着いてなかったら一生ループしてるはず、という方針で適当に書いた。
提出した段階では 4 位でなかなか良かった。

ソースコード
http://jag2014summer-day4.contest.atcoder.jp/submissions/232012

B : 不審者
最初、移動距離を最小化と誤読して、BFS 書くだけの実装めんどうなやつだと思った。
大体書き上がってからサンプルが合わなくて誤読していたことに気づいて悲しかった。
よく考えてみると、移動のバリエーションは全然なくて、右手を壁に付けながら進み続けるしかないので、普通にシミュレーションするだけでよかった。
コードが短くなって嬉しかった。最初からこれが書ければよかった。

ソースコード
http://jag2014summer-day4.contest.atcoder.jp/submissions/232070

C : Magic Bullet
特に工夫しなくても通る三次元幾何。
必要なライブラリはすべて持っていたのでコピペするだけだった。

ソースコード
http://jag2014summer-day4.contest.atcoder.jp/submissions/232088

D : 夕食
初見の印象は「解ける気がしない」だったからスキップした。
あとで解ける問題がなくなって戻ってきたときに時間を取って考えたけど、全く方針が浮かばなかった。
頭が固い人には解けないみたいな感じで、そういう雰囲気が最近解いたモジュロ・クエリに似てるなぁと思った。

E : AI
無限ループにはまらないようにメモ化しながら構文解析すればいい。素直な問題。
今度は何回も読み直したから誤読はしてない。
しかし、実装力がなくてめちゃくちゃバグらせてしまって、1 時間かけても提出に至らなかった。ダメすぎる。

コンテストが終わってから通した。
if, while の条件式が偽だったときに、次の program を実行せずにスキップしないといけないけど、この「今スキップ中か」という情報をメモ化の情報に加えていたことがバグの原因だった。
ほんとは違う状態(スキップの開始位置が違う)だけど同じ状態に 2 回訪れていると判定されて間違えていた。

ソースコード
上記のバグあり : http://jag2014summer-day4.contest.atcoder.jp/submissions/232559
正解 : http://jag2014summer-day4.contest.atcoder.jp/submissions/232718

F : Longest Match
作問チームに lyoz さんがいるはずなのでやばい文字列問題かと思って敬遠してたけど、たくさん通されてたので考えてみると、ふつうに suffix array で二分探索 & RMQ をすればよかった。
suffix array を使うのが久しぶりすぎて色々忘れていたので、途中でアリ本を読んだりしていた。
TLE したという発言を twitter で見かけたけど、SA-IS と sparse table は十分速かった。

ソースコード
http://jag2014summer-day4.contest.atcoder.jp/submissions/232371

G : リサイクル
問題文を読んだだけで考える時間がなかった。

H : トーナメント
C の次にこれを考えてたけど、解答の糸口が見えなかったのであきらめた。

I : 首都
読んだだけだった。

J : Vongress
H の次にこれを考えた。
凸多角形のいい感じの対角線を一つ選んで、その上にいい感じの割合で点を置けばいいと思った。
提出したけど、最初のケース以外すべて WA になって、原因不明だったのでしばらくしてあきらめた。
アルゴリズムは正しい気がしていたけど、最終問題だしこんなに簡単なわけがない、何か根本的なことを見落としてるのかもしれないと思った。
ところで vongress って何?

楽しかった。(2回目)
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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