Hatena::ブログ(Diary)

antaのメモとか

2012-11-15

2012-07-31

Codeforces Round #131 Div.2

Dashboard - Codeforces Round #131 (Div. 2) - Codeforces

本番

まずA

早解き

次にB

とりあえず2,5の倍数は最下位桁が0ならよさそうだ。
3の倍数は桁のsumが3の倍数かどうか、だが、どうしよう?
とりあえずできるだけ多くの数字、また、上の桁の数字を残して何個か消せば良い。
leading zeroに気をつけてSubmit

次にC

なんかよくわからないなーと思って次に行った

そしてD

ゼロの扱いがめんどくさそうだな。
考えたのは、例えば1が3個,2が2個でnが7の時、11122??を作ってその順列の数を数えればよさそうだ。
しかしどうやったらそれが出来るのかがわからない。
結局ほぼすべての時間を使っても解決せず

少しだけE

なんか速攻解いてる人がいたので見てみる。でも問題わかってない

Challenge

解けそうにないし見てみるかと思って見てみる。
するとBで"2\n0 0"の時"00"と返すコードがほとんど。
それぞれ念入りに確認しつつ5つ全て成功。これは他にChallengeする人が居なくて良かったと思った。

System Testing

B落ちるなよ…と祈りつつ待つ。
ちょうどテストされる瞬間を見れた。
そこに現れたのは"Wrong answer on test 17"の文字列。
息が止まった。
見てみると明らかな、フラグを設定しないというバグ。
だがしかし、それを直してPracticeでSubmitしても同じケースでWAだった。

結果

A: +494
B: Failed System Test
Challenge: +500
Rank: 251/1494
Rating: 15791594
Challengeがあって順位がそれほど落ちなくてよかったか。

コード

続きを読む

2012-07-09

SRM549 DIV2

http://community.topcoder.com/stat?c=round_overview&rd=15171
前回のただのバカによってDIV2に舞い戻りました。

本番

250

うーん、確率でシミュレート?
と思ったけど何故か式が浮かばない。
少し考えたら単純な場合分けじゃん。と思ってSubmit。
遅すぎ。1分で解くべき問題。223.79pt。

500

問題の条件が英語が読めねー
とりあえず二部グラフの最大マッチングなのはわかったから適当にそのアルゴリズムライブラリを持ってくるが、そのライブラリを動かすのに手間取る。
そうこうしているうちに時間は過ぎる。
だが結局問題文がわからなくてテストが通らない。

1000

残り30分くらいで500を諦め1000を開く。
うってかわって問題文は簡単。閉路を無くすための辺の削除数の最小らしい。しかしぐぐってもぐぐリ方が悪いのか出てこないし、考えてもよくわからない。
結局何もできず。

Challenge

チャレンジでも考えるかと思うが、500は問題文がわかってないので250を。Exampleに位置が真ん中かつ回数が偶数回であるものが無いことに気づき、それを準備する。
結果、まさにそのケースを考慮していない人を二人落とせた。
だが他に250の二人と500の二人を落とされた。

解法

500

判定式は br>tr && bh*tr<th*br

1000

見てみると超単純なbitDPに見える。
新たにjという頂点を考える時、今まで考えない所の中で、そこからjにこれるものの数、を今まで考えてた奴に足す(それのmin)、的な。
理解しようとしてみた。が、まだよくわかってない。

結果

Problem: 250Pass 500Opend 1000Opend
Challenge: +100
Rank: 64/770
Rate: 1010->1102

感想

500のような問題文読めねー、は、ある程度想定される式をテストに通してみるべき。ただしその場合チャレンジ・システムテストが怖いので、その後に問題文をよく読んでみること。
グラフ理論(他の分野でも)。っていうならアルゴリズムがなんとなくわかってる、だけじゃなく、その組み合わせや証明が直ぐに出来るようにならなきゃ、詳しいとは言えない。
DIV1いきたい

コード

続きを読む

2012-07-03

SRM548 DIV1

TopCoder Statics SRM548

本番

250

こういう問題解き慣れてなさすぎ。
結局、二分探索かなーと思ったけど符号関数がわからなかった

500

適当に値を圧縮してDPかなーとか思ってみた。
でも実装できないしそもそも方針が駄目だったのだと思う。
Challenge
ヤケになって適当な嘘Submitして2回Unsuceededして-50

冷静になって、Challengeで点を落とすアホはやめよう。
DIV2降格かなあ

解法

250

最大レベルを二分探索。
前から見てった時、最大レベルでできるだけ小さくしてって、
どうしても条件を満たせない時(最大レベルで伸ばしても小さすぎる時)はレベルが足りないから正。
全部おkなら負。
何故これでよいのか?非形式的にでも理解を深めるべき。

450

DP。でもわかってない。
基本的にはそれぞれのソートしたsecondDieの間の
何番目までか・0の消費数・勝てる個数(を作れるか)とかが関係するっぽい。でもわかってない。

結果

Rate: 1285→1010
最大幅下がったっぽいね。DIV2降格。当然の結果でしょう。

感想

50^5は定数倍の高速化でなんとかなるらしい。
やっぱりきちんと考えていかないと駄目だね。
250は出来て当然であるべき。450はせめてO(n^5)の方針を立てよう
やっぱり250を落としたことと-50が悪い。悪い。悪い。反省しろ。
やっぱり練習が足りないと思うので、練習をしよう。

最近

グラフ理論の基礎を勉強してる。

2012-06-26

TopCoder SRM547 DIV1

250、パッと見簡単そうだったが手間取りすぎ。酷い
500、全然
Challengeで250が落とされまくってたのになぜだか分からなかった。オーバーフローらしいが
ChallengeはUnsucceflyしただけ。ちゃんと見てから、もしくは確信のあるバグ要因があった時に打つべきだ。
Challegeの練習もすべき。
500はSumが大きくなるから、breakしてやればいいということらしい。こういう一見TLE+枝切りが自分はわかってないので、考えていくべき。
あーIntで10^10は無理なのか。今まで勘違いしていた。そこら辺非常に重要。絶対覚える
SRM結果: [Passed,Opened,Opened] -25 240/540 R1204→1285

続きを読む