Hatena::Grouptopcoder

yehara のTopCoder日記

|

2011-01-22

SRM 494 Div1

04:29 | SRM 494 Div1 - yehara のTopCoder日記 を含むブックマーク はてなブックマーク - SRM 494 Div1 - yehara のTopCoder日記

o o x 175.09 + 244.42 + 0 + 0 = 419.51 (107位)

Level 1 (250)

間に合うだろうと思って、愚直に調べる方法でやった。O(N^6) ?

Level 2 (500)

条件に合わない木を抜こうが抜くまいが差の絶対値の和は変わらない。たとえば A[i-1] < A[i] < A[i+1] のとき、i 番目の木を抜く必要があるが、abs(A[i+1] - A[i-1]) = abs(A[i+1] - A[i]) + abs(A[i] - A[i-1) なので、期待値計算においては木を抜くことは考えなくて良い。 すべての隣接する木の長さの差の期待値を足し合わせるだけ。

Level 3 (1000)

残り 15 分くらいしかなかったので見てない。

まとめ

チャレンジフェーズはなにもせず。今回は Level 2 がやさしめだったのかな。Rating は大幅増(1682->1779)。自己最高を更新した!

トラックバック - http://topcoder.g.hatena.ne.jp/yehara/20110122

2011-01-13

SRM 493 Div1

04:00 | SRM 493 Div1 - yehara のTopCoder日記 を含むブックマーク はてなブックマーク - SRM 493 Div1 - yehara のTopCoder日記

o x x 130.23 + 0 + 0 + 0 = 130.23 (60位)

Level 1 (300)

先手必勝となるのは1手勝ちのケースしかない。すべての手順は可逆なので、もし先手必勝かつ1手勝ちで無いケースがあるとすると、後手は元に戻す操作をすることで永遠に手数を伸ばしうるので矛盾する。

つまり1手勝ちできる場所の集合(=先手必勝エリア)を考えて、

  • 初期状態が先手必勝エリアにあれば先手必勝
  • そうではなく、初期状態から1手で行ける箇所すべてが先手必勝エリア内にあれば後手必勝
  • それ以外のケースは引き分け

となる。

時間使い過ぎた。

Level 2 (450)

時間たりなくて、ちゃんと考えられなかった。

Level 3 (1000)

みてない。

まとめ

チャレンジフェーズはなにもせず。こんな点数でも Rating あがった(1626->1682)。一応自己最高。今年は 2000 くらいにいきたいな・・・。とかいってみる。

トラックバック - http://topcoder.g.hatena.ne.jp/yehara/20110113

2010-12-08

SRM 490 Div1

04:00 | SRM 490 Div1 - yehara のTopCoder日記 を含むブックマーク はてなブックマーク - SRM 490 Div1 - yehara のTopCoder日記

Level 1 (250)

もし M と N が互いに素だとしたら、0 .... N-1 が均等に現れるはずなので期待値は (N-1)/2 になる。M と N が互いに素でないとしたら、全体を gcd(M, N) で割ると M, N が互いに素の場合の問題に帰結する。したがって解は (N/gcd(M,N) - 1) / 2 * gcd(M,N) = (N - gcd(M, N)) / 2 。プログラムは gcd メソッドを除けばたった一行なのに、時間かけすぎた。(168.02)

Level 2 (550)

すべての部分文字列について短い順に最小値を計算して DP でいけると思ったんだけど、答えがあわずタイムオーバー。なんか実装を間違えたかな・・・

Level 3 (1000)

みてない。

まとめ

Challenge Phase はなにもできず。550 だけあって Level 2 が難しかったようで、こんな点数でも rating 微増。(1619->1636)

トラックバック - http://topcoder.g.hatena.ne.jp/yehara/20101208

2010-11-30

SRM 489 Div1

23:15 |  SRM 489 Div1 - yehara のTopCoder日記 を含むブックマーク はてなブックマーク -  SRM 489 Div1 - yehara のTopCoder日記

Hanako キター

Level 1 (300)

うーん、わからない。直感的には 3 つのボール全パターンで OK なら良いような気がするが・・・。自信はないがそれ以外思いつかないので提出→これでよかったみたい。最初結構悩んだので時間かかった(197.44)。

Level 2 (500)

いろいろ転がり方を考えてみると、1 が下に来る前に 1 が上に戻ることはない。つまり1 は 必ず 1 度だけ下にきて、最後に上に戻る。つまり最初に 1 が下に来るケースの掛けあわせが答えとなる。ちょっと文章でうまく説明できないが x, y が 4 のときだけ特別に考えて定数時間で計算できる。コードでは最初に上に行くケースと右に行くケースを分けて考えた(231.62)。

public class DiceRotation {
    public int theCount(int goalx, int goaly) {
        return calc(goalx, goaly) + calc(goaly, goalx);
    }
    int calc(int x, int y){
    	int r = 0;
    	if(x<2) return 0;
    	if(x==4) r = y+1;
    	if(y>=2) r++;
    	return r;
    }
}

Level 3 (1000)

のこり 10 分くらいしかなかったので、見てない。

まとめ

チャレンジフェーズは x か y が 4 のときにちゃんと計算しているかが狙い目。最初に見たのでいきなり (4,4) で間違った答えを決め打ちで返しているものがあって撃墜。その他でまちがってたやつは他の人が瞬殺してた。500 が簡単かつチャレンジしやすい問題だったみたい。2 完 + 1 撃墜でそこそこ上位にいくかと思ったけど 121 位・・・。レートはそこそこ上がった。(1507->1619)

トラックバック - http://topcoder.g.hatena.ne.jp/yehara/20101130

2010-11-14

SRM 487 Div1

23:29 |  SRM 487 Div1 - yehara のTopCoder日記 を含むブックマーク はてなブックマーク -  SRM 487 Div1 - yehara のTopCoder日記

Level 1 (250)

干渉するのは mod k+1 が同じグループ内だけだから、それぞれのグループを独立に考える。グループ内の要素数が偶数ならすべてを取れる。グループ数の要素が奇数ならひとつだけ残して残りは取れる。ひとつ残せるのはグループ内で奇数番目の要素だけなので、そのなかから最小の数字を取り除く。(181.90)

Level 2 (550)

直感的には、解があれば期待値は m/k になりそう。要は解があるかどうかの判定さえできれば良いと思う。k が 1, 2 のケースは簡単に検査できる。k が 3 のとき悩んだが解がない反例が思いつかなかったので k >= 3 とのきは常に解ありとして提出する。550 がこんな簡単ははずないんですがね・・・。System Test で落ちる。

Level 3 (950)

550 よりこっちのほうが簡単そう。1 から逆順に *m か -1 の演算を n 回繰り返して到達できる数をカウントする。-1 して 1 か m の倍数になるケースは認められない。現在の数字が m の倍数であるときに残り n 回で到達できる数のカウントが漸化式で書けるので DP。途中で 1 を通るケースは認められないので、その場合だけあとで除外する。ちょっと時間が足りなくて間に合わなかった。残念。タイムアップ後数分で完成させたコードで Practice Room のテスト通過。惜しい。

まとめ

同じ部屋では 550 で自分と同じ方針の人が 3 人くらいいる。他の部屋で 550 が落とされまくっているので絶対に k=3 での反例があるはず。みつけられたら全部落とせるのに最後まで見つけられず。結局なにもできず。とりあえず黄色に復帰。もう何回目か忘れた。(1437 -> 1507)

トラックバック - http://topcoder.g.hatena.ne.jp/yehara/20101114
|