Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2013-09-019月に解いた問題 このエントリーを含むブックマーク

8月試してみてモチベ向上につながったので続けます。

目標

ある程度の難易度以上のものを30問以上(1日1問)

  • Topcoderならdiv1-med、div2-hard以上
  • Codeforcesならdiv1-1000、div2-2000以上
  • その他のコンテストの問題は本番中の正解者数を参考に雰囲気で

状況

  • 25/30

解いた問題一覧

  • ◯ : 何も見ずに解いた
  • △ : 解説を見て解いた

DateProblemStatTime Tag Difficulty解法メモ(ネタバレ注意)
9/7 CF198-D1C >120 数学 ★★★ 自由に置ける数字と、そうでない数字に分けて考える。
不自由な数字の場所に、どのタイプの数字を置いていくか決めていくとうまくいく
9/7 CF199-D2D 30 数え上げ Oと、その上下左右2マスを使えないと考えドミノ敷き詰めする
重複は包除原理で取り除く
9/14 きゅうり問 >120 数え上げ ★★★ 一番大きなbitを諦めると、下位のbitを任意に調整できることを利用する。
9/14 CF200-D1C 60 探索 素直に二分探索。一番左のヘッドから貪欲に進めていく。
左に行ってから戻るパターンと、その逆のパターンがある。
9/14 CF196-D1B >120 グラフ ★★ 自分を含む子と、それ以外の頂点でそれぞれ最も遠い感染地を管理。
どちらも親からのdfsで求まるが、自分の兄弟を毎回全探索しないように!
9/14 CF196-D1B 60 グラフ ★★ どの頂点をどの子につけるかで全探索。
素因数はなるべく細かく分解したほうがオトク。
9/14 CF184-D2D 60 グラフ 条件を読み解くと、限られた形のグラフしか許可していないことが分かる。
9/15 CF142-D1C 90 グラフ ★★ 各頂点の次数させ分かれば答えが出る。グラフは作らなくて良い。
アリスでもボブでも作れない三角形は、アリスの方にある辺が1つか2つと考える。
9/15 CF142-D1D 30 探索
9/16 CF187-D1C 60 数え上げ ★★ 出現順に同じ数字を区別する。BITでうまいことごにょる
9/16 CF145-D1C 30 数学 人間を半分に分け、それぞれチームを組ませると問題が半分になる。
nが2の乗数でない場合は、2^k > n に関する問題を解いて、余りを無視する
9/16 CF145-D1D 20 数学 後ろから考えて、なるべく同じ向きが連続するように重ねていく。
9/16 CF125-D1B 20 探索 ダイクストラ法
9/19 CF111-D2D >120 グラフ ★★ 辺の重みでソートし、同じコストの辺をまとめて考える。
2点が同じグループでなく、その辺が橋になっていればany
9/19 CF112-D2E >120 数学 ★★ ある数字がどの数字とペアになるのかを考えるのではなく、
逆にbit反転した数字とペアになれる数字を探す
9/19 CF100-C 60 探索 数が多いサイズの雪球から貪欲に使う
9/19 CF100-D 30 探索 dp[n][a][p] := 前半にn問解き、a問は後回し、前半にp分使った時のペナルティ
前後半を跨ぐ場合のペナルティは min((a+1)*オーバー分数, 後半の分数)を加算
9/19 CF100-E 90 数え上げ ★★ 1. 1層で先頭からi 個まで j 色の飾りを並べる場合の数 dp1[i][j]
2. i層まででk色の飾りを使う場合の数 dp2[i][k]
2.は一見O(N*5000)かかるようだが工夫するとO(N+L)に落ちる。
9/20 CF201-D1B 30 文字列 一見、典型なDP (O(n^3))に思えるが実は罠が。
ウイルス文字列と不一致の場合、どの位置まで戻る必要があるかを前計算。
9/20 CF201-D1C 50 数学 ★★ 貪欲にmodを取ったとき大きい数を使う。
使うとbより小さくなるx_{i}は貪欲のステップごとに取り除く
9/21 CF93-D1B 30 文字列 まずprefixとsuffixのハッシュを計算し、prefix=suffixとなる長さを探す。
中間の文字列はローリングハッシュで探す
9/21 CF93-D1C 30 パズル 右上or左上から操作していく。図を描くと分かりやすい
9/21 CF93-D1D 60 数学 ★★ 10^18以下のフィボナッチ数は90ぐらいしかない。
数を貪欲にフィボナッチ数に分解し、更にそれらをDPして分けていく。
9/21 CF91-D1C 30 数学 15! > 1000000000 なので、高々最後から15個のみ考えれば良い
9/22 ARC008-D 30 データ構造 ★★ 座標圧縮して二分木を作る。
(aX+b)c+d=acX+bcdなので更新を親に伝搬できる

ノーカウント

DateProblemStatTimeTagDifficulty解法メモ(ネタバレ注意)
9/7 CF199-D2A 15 実装 有効な組み合わせは(1,2,4), (1,2,6), (1,3,6)のみ。
(1,2,4)と(1,3,6)を先に使い、残りで(1,2,6)の組を作ると考える。
9/14 CF200-D1B 30 読解 回路をほどくとは、隣り合う+か-をなくして、空きを詰める操作に相当。
それさえ分かれば、よくある問題でstackをつかってほげほげで解ける
9/16 CF125-D1A 20 数学 式をこねると、t >= k^{n} + (k^{n-1} + k^{n-2} + .. + 1)b
を満たす最大のnを見つける問題になる。
9/20 CF201-D1A 10 ゲーム 最終的に現れる数字のセットは、操作の仕方に寄らない。
max({a})/gcd({a})個出てくるので、初期の個数を引いてmod2を取る