Hatena::Grouptopcoder

k_operafanのTopCoder日記

2011-06-05

[]University of Aizu Programming Contest 2011 22:45

とても楽しかった.

A - It's our delight!!

読んでなんか大変そうだったので最初はBから解いた.

配達時間が8分以内かを判断する部分の絶対値の場所のミスで1WAを喰らった後にAccepted.

B - Watchin' TVA

600≤start≤2929よりある日のアニメの見かたは他の日のアニメの見方に影響しないことが分かる.

よって区間スケジューリング問題っぽい気がしたけど,全てのアニメが30分なので単純に始まるのが早い順で解けそうな気がした.

ということで,優先的に見るアニメをまず貪欲に選び,選び終わった後それ以外のアニメを貪欲に選ぶコードを書いて提出した.

23WAを喰らってAccepted→暫定的に0WA扱いに.

C - Yanagi's Comic

残り時間が危なくなってきた所で思考開始.

半直線と長方形の交点の求め方にミスがあって,バグ修正に時間がかかった.

一発でAcceptされた.

D - The House of Huge Family

最大流を用意していなかった.

仲が悪くなってしまったことが残念.

無向グラフだと勝手に仮定して,コストが0以下のものを全て取り除いてから,全点間に対して最大流を適用した.

グラフの構築にO(V^2)の方法を用いてしまってTLE

グラフの構築をO(V)で出来るようにしたらAcceptされた.

E - Legend of Storia

無理ゲー臭がしたので逃亡

F - Cutting a Chocolate

アーモンドがどこに含まれるかさえ分かれば二部探索かしゃくとり法でいけそうな気がした.

でもアーモンドがどこに含まれるかを効率的に判定する方法が分からない.

G - School of Killifish

RMQを用意していなかった.

二次元RMQの問題.

X方向Y方向それぞれに対してRMQを持っておく方法で提出したが,MLEが厳しくて回避出来なかった.

H - Squid Multiplication

多倍長整数を用意していなかった.

偶数奇数で分類し,偶数のものの小さいうちから2つの積と奇数のものの一番小さいものを見比べる方法で書いた.

Accepted.

I- FIMO sequence

平方分割かと思ったけど間に合いそうに無いので逃亡.

J - BD Shelf

問題文を読んだだけ.

K - Rearranging Seats

交換出来ればOKなのでH*Wの偶奇で解が求まる.

Accepted.

L - The Tower

訳が分からなかった.

結果

問題数:6問

ペナルティ:1012(暫定)

順位:9位(暫定)

関係者の皆さんお疲れさまでした!

TopCoder部の活用 21:57

コンテストとかの記録ははてなダイアリーの方ではなくこちらに書くようにしようと思った.

[]TopCoder SRM 508 Div1 21:57

赤コーダーの方が一人しか居ない部屋.Room12.

Easy(250点)

シフト操作と除算操作を用いて,ある物体を先頭に持ってくるのに書かる最短の時間を求めるような問題だった.

シフト操作を行うタイミングは,最終結果には影響しないことに気づいたので,N以下の素数を全て求めてDFSするコードを書いて提出した.

提出してしばらくして,素数を求めるコードに配列外アクセスをするバグがあることに気づいたので修正して再提出.

Passed System Test(157.89点)

Medium(500点)

a or b = a + bになるのはa xor b=1またはa=b=0の時しかないので,各ビットがこの条件が満たすようなものを求めれば良いんだろうな,とか考えていた.

DPには気づかず死亡.

Opened

Hard(1000点)

Unopened

Challenge Part

求めている素数が足りなさそうなコードを一つ落とす.調子に乗ってもう一つ落とそうとするが失敗.

+25点

結果

得点:182.89点

順位:248位

レート:1842(+26)

AtinAtin2012/11/16 17:15Very true! Makes a change to see seomone spell it out like that. :)

ggyzelguggyzelgu2012/11/18 07:54OVyHq9 , [url=http://brhdmiqlyqxv.com/]brhdmiqlyqxv[/url], [link=http://lkciulvcisle.com/]lkciulvcisle[/link], http://umldhftkcrmq.com/

cmsbfmindgocmsbfmindgo2012/11/18 20:00shwWdF <a href="http://kyzfdjdnlmia.com/">kyzfdjdnlmia</a>