スポンサーサイト

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

WUPC 2012

2012/06/02 14:00 ~ 16:00

学校の図書館から参加。
外部枠。
遅刻やむをえない事情により 10 分くらい遅れて参加。 ( register だけは予めしていた )

Tags : プログラミング WUPC

一週間以上経ってしまって、忘れていることも多いけど、思い出しながら簡単に参加記録を書く。



いつもどおり A から解こう。

A.
読み読み。
二つの日付の差が何日かを求める問題。

サイズがちっちゃいから一つ一つ数えればいいか。
書く。
何も考えず、日付 1 の変数名を m1, d1 に日付 2 の変数名を m2, d2 にしたところで、
「 M1 から M2 になるまであと○○日しかない。今日は有意義だったか?」
みたいなことを想像してしまった。
胃に悪い。

問題なく書きあがって submit. accepted.

B.
文字列たちから二つ以上選んで cat してできる辞書順最小の文字列を求める問題。

まず、三つ以上つなげるのは損ということに気付く。三つめ以降は消してしまったほうが辞書順で早いよね、ということで。
なら、二つ選んでできる文字列を全探索しようというのが自然。

書く。
submit. accepted.

C.
迷路である地点を経由しつつゴールに行く最短手数を求める問題。

立命のセットでも似た問題があった気がするなぁ。2D 好きの彼を拾いつつ電車に乗るみたいな設定だったような。

で、これはふつうに BFS すればよい。
( スタートから中継地点までの最短距離 ) + ( 中継地点からゴールまでの最短距離 )
が答え。

ひさしぶりに良心的な問題セットで心やすらぐ。

D.
問題文の図だけ見て、
左下 or 下 or 右下 に進んでマスの和を最大化する問題かなぁと予想していると、ほんとにそんな感じだったので、さくっと書いて出したら WA。

よく読んでみると、左下に行けるなんてどこにも書いてなかった・・・

修正して AC。

E.
みんなのとらうま lucky number きた。

無向グラフ上の最短経路問題だけど、総距離が 4 or 7 で割り切れるタイミングでゴールしないといけない。

一瞬では解法が見えなかったけど、しばらく考えると、mod 4×7 = 28 での最短距離だけわかれば十分だと気付いたので、それで拡張 Dijkstra することにした。

これもさくっと書きあがって、この程度で実装ミスもないだろうと思って submit すると、また WA。
よく読んでみると、一度ゴールに着いたら動けないという一文を見逃していた。むぅ・・・

一行追加して AC。

F.
やったー幾何だ、などとはしゃぐ。無言で。

点集合が与えられるので、それらの四点を頂点とする軸に平行な長方形で、内部に点を含まないもののうち面積最大のものを求める問題。
ちょっとややこしい。

どうするんだろう。ぱっと見ただけでは全然わからない。

しばらく試行錯誤して、あまりすっきりとはしないけど、それっぽい方針がまとまったので実装しはじめる。

長方形の左下の点について全探索。
左下の点 P = (x0, y0) を固定したとき、P より右にある点について、P に近いものから順に O(N) で調べていく。
このとき、どの高さまでなら内部に点を含まないかを同時に更新していく。

ある座標値に点があるかどうかを判定するのは、今回の場合は座標値が小さいので、前計算して bool 配列でもっておけば O(1) でできる。
( 座標値が大きくてもハッシュテーブルを使えば O(1) でできる )

これで O(N^2) になる。
N ≦ 10^4 で 5 sec なので大丈夫だろうということで、投げる。
Wrong answer.

サンプル弱いよ・・・
サンプルではなく、問題文の最初の図のケースを試すとあっけなく間違えていた。
修正。submit. WA.
さらに修正。submit. AC!

全完できたのでよろこぶ。無言で。
順位表を見てみたら、すでにちょこちょこ解かれていて、ちょっと落ち着く。
暫定 9 位だった。

この時点で 15:11 だったから、遅刻した分を差し引くとちょうど一時間かかったことになる。

あとから見てみたら、WA のペナルティが思った以上に大きかったらしく、時間差でたくさんの人に抜かれて 19 位まで落ちていた。



こういうセットがたまにあると、気分の切り替えにもなっていい。
楽しかった。
運営の方々、おつかれさまでした。

そういえば、後から解説を読んだら F がもっとずっと簡潔に解かれていて、少し悲しい気持ちになった。



ソースコード
A. http://wupc2012.contest.atcoder.jp/submissions/20544#
B. http://wupc2012.contest.atcoder.jp/submissions/20589#
C. http://wupc2012.contest.atcoder.jp/submissions/20668#
D. http://wupc2012.contest.atcoder.jp/submissions/20738#
E. http://wupc2012.contest.atcoder.jp/submissions/20843#
F. http://wupc2012.contest.atcoder.jp/submissions/21085#
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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