Hatena::Grouptopcoder

TopCoderの学習のお時間 RSSフィード

戦績(topcoder.com) / 戦績(competitiveprogramming.info) / 過去記事 / 日記

 | 

2015-01-12

[]January Challenge 2015 21:24 はてなブックマーク - January Challenge 2015 - TopCoderの学習のお時間


http://www.codechef.com/JAN15

2年ぶりくらいに参加した。

このコンテスト形式、マイペースに取り組めて良いので今後も出ようと思う。


Chef and Stones(CHEFSTON)


やる

http://www.codechef.com/viewsolution/5713322


Gcd Queries(GCDQ)


配列を前から見ていった累積GCDと後ろから見ていった累積GCDを覚えておく

http://www.codechef.com/viewsolution/5713655


Sereja and Votes(SEAVOTE)


取り得る和の上限と下限を求める

http://www.codechef.com/viewsolution/5713840


One Dimensional Kingdoms(ONEKING)


よくあるGreedy

最初、区間の開始・終了をオブジェクトとしてソートしていたらTLEした

座標の範囲が狭かったので座標をキーにしてソート無しでやった

http://www.codechef.com/viewsolution/5714255


Chef and A Large Permutation(CLPERM)


実装も知識も無く考察のみで解ける愉快な問題

存在するカードを昇順に並べた配列をBとする。

B_1〜B_n のカードを使って S=ΣB_i(1<=i<=n) までの全ての整数を表せるとすると、B_n+1 を考えると次のようになる

  • B_n+1 <= S+1 の場合
    • B_1〜B_n+1 のカードを使って ΣB_i(1<=i<=n+1) までの全ての整数を表せる
  • B_n+1 > S+1 の場合
    • S+1が表せない

これをそのままやるとO(N-K)だが、カードの数が連続している範囲をまとめて処理するとO(K)になる

http://www.codechef.com/viewsolution/5717846


Queries on the String(QSET)


count[x][y] := (文字列先頭からx文字目まで見たときの数値 % 3 == y) ? 1 : 0

上記の値をSegmentTreeで管理する

この問題が今回の中で一番難しかった気がする

http://www.codechef.com/viewsolution/5716782


Xor Queries(XRQRS)


永続SegmentTree

xor最大化やk-th smallestのクエリに対しては、上から1bitずつ決めていく

http://www.codechef.com/viewsolution/5867272


Sereja and LCM(SEALCM)


D(なぜかコード中ではUという名前にしてしまった)を素因数の冪に分解して、包除原理で補集合の要素数を求める

http://www.codechef.com/viewsolution/5872152


Ranka(RANKA)


白を下から埋めていく→黒を1つ置いて白を全滅させる

を繰り返す

黒が最後まで行ったらいったん黒を全滅させ、盤面を90度回転させた形で同様のことをやる

http://www.codechef.com/viewsolution/5873615


Sereja and Number Division 2(SEAND2:タイブレーク)


焼きなましただけ

ΣB の値が大きいケースに長く時間をかけるようにした

http://www.codechef.com/viewsolution/5729963


CodeChefではJavaC++の2倍時間を使えるけど、有利なのかどうかはよくわからない


結果

  • 10問中10問AC
  • 14位/7943人
 |