Hatena::Grouptopcoder

hama_DU@TopCoderへの道

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

学生の時ほどプログラミングコンテストにかける時間が取れなくなった。

社会人になっても競技プログラミングを続ける(限られた時間の中でもモチベが続くようにする)にはどうしたら良いか色々考えたのだが、

月ごとに解いた問題を何らかの形でまとめておくのが良いかもしれないと思ったので、メモを残しておく

とりあえず8月は試しで

目標

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

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

状況

  • 37/30

解いた問題一覧

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

DateProblemStatTimeTagDifficulty解法メモ(ネタバレ注意)
8/1 anta氏プロコン1-D 60 数学 ★★ 文字列を平方分割。各クエリごとにO(√(文字列の長さ))
8/2 SRM587-D1M >90 幾何 三角形の足し算と引き算で各々の面積が求まる。O(W)
8/2 SRM586-D1M 40 グラフ 各国同士の年号のズレの許容範囲をヒントを元に更新。
最後にWFをして推移関係のつじつまを合わせる
8/4 天下2013予選A-C 60 数学 パターン数は多くなく、全列挙できるレベル。
n,m<100あたりで答えを列挙し、法則を探す
8/5 天下2013予選A-D >120 文字列 ★★ がんばって実装する。うまい実装の仕方を見つけたい。
8/5 Memsql-Round2-B 60 文字列 ★★ 見つけたい回文の半径は高々50なので、
O(S*50*26)のDPができる
8/7 天下2013予選A-E 60 探索 ★★ 実験すると有効解が少ないことに気づく。全探索でOK
8/7 Memsql-Round2-C >120 ゲーム ★★★ 石を置くとゲームが2つの独立した状態に分かれる。
Grundy数を求めて最後にXORする
8/8 SRM576-D1M >120 数え上げ ★★★ 左右に続いた一塊のスポンジの区間を考えると、
少なくともひとつは区間Lの水を受ける。
8/9 SRM576-D1H >120 数学 ★★★★ W<=1,000,000,000と大きいが、
文字が被るwのパターンは少ないことを利用する。
8/10 SRM585-D1M >120 数え上げ ★★★ 0から順番に入れていく。
重複組み合わせを使ってうまくごにょるとO(n^4)になる
8/10 SRM583-D1M >120 グラフ ★★ 既にONになっている辺をOFFにしても得しない
(同じ手数で別解を作れる)
一度の操作でONにする辺の数で貪欲してOK
8/11 SRM583-D1H × 確率 ★★★★ w<12,w<h<21を満たす
wの全パターンについて各rowを使うか使わないかでDP
editorial通りに実装しても正解にならないのでpend
8/11 SRM582-D1M >120 数え上げ ★★★★ 解説記事
8/12 SRM581-D1M 30 グラフ 木Aと木Bから頂点を2つずつ選ぶと閉路が定まる。
8/12 SRM581-D1H 60 探索 ★★ 一番上だけ全部試す。
それ以降は適当に枝刈りしつつ探索するとなぜか間に合う
8/12 CF195-D2D 30 数え上げ 5桁ぐらいまで手で解いて規則を探す
8/17 SRM588-D1M 20 探索 TSP+α
dp[開けたドア][赤い鍵] = 所持中の白い鍵の最大数
8/18 SRM580-D1M >120 グラフ ★★★ 区間で考えるとうまくいく。
各tweetに対して、誰にretweetしてもらえれば
左右遠くまで届けられるかを貪欲に求める
8/18 SRM580-D1H >120 ゲーム ★★★ ゲームの状態は(位置,今いるy座標での壁の区間)で表せる。O(HW^3)
8/18 SRM579-D1M 25 グラフ TSP。事前にWFをして店たちの間を行き来する最短距離を求めておく
8/18 SRM578-D1M 25 数え上げ 現在考えている位置の2つ前までの狼まで覚えておけばいい。
若干反則臭いがBitSet使ってO(N^3)でACできた。
8/19 SRM577-D1M >120 探索 ★★★ 座標系を45度回転(x',y')=(x+y,x-y)させると
マンハッタン距離の式がmax(x1-x2,y1-y2)になる
dp[fx][tx][fy][ty] := 現在の石の配置が覆う範囲から広げた時の最小コスト
8/19 SRM575-D1M 30 確率 ★★ 各数字についてswap操作により変化する値の期待値を求める
各区間でそれを足して(いもす法を使う)、平均をとれば答えが出る
8/19 SRM575-D1H 90 グラフ ★★★ 白マスはy座標が偶数or奇数に分けることができて、
黒マスからは片方ずつに手が伸びる形になる。
よって白マスのy座標の偶奇で2部グラフっぽくなって最大流ができる
8/20 CF188-D1B 40 実装 実装するだけだが制限時間が厳しい
ビット演算やループの展開などを利用して高速化を図る。
8/20 CF188-D1D 60 ゲーム ★★ このゲームは、次のミニゲームが独立し、並行しているとみなせる :
n個の石がある。iの石を取ると倍数の石も取る。手詰まりになったら負け
ミニゲームのgrundy数を前計算し(n<=29)、ゲームを分解してXORする
8/22 CF186-D2D 60 探索 ★★ dp[i][j] := [0,i)までの区間でj個穴を覆う時の最小コスト
次に使う区間はn通りを試せば十分。O(n^3)
8/24 CF183-D1C >120 数学 ★★★
8/24 CF182-D1B 20 グラフ 答えの値で2分探索。
到達可能性はベルマンフォードなどで適当にやればOK
8/25 CF170-D1C 90 ゲーム ★★ 各行・各列の切り込みが入っていない数 でNimになる
先手勝ちの初手は (xor ^ 残り石数) <= 残り石数 である行or列から切り取る
8/25 CF148-D1B 30 数学 (a:ソート済の入力列) 片方のグループは {}, {a[0]}, {a[0], a[x]} しか入り得ない
仮に a[y] (0<y<x)を突っ込んでも最小値が小さくなるだけで損
8/25 CF148-D1C 60 グラフ ★★ 各頂点を根にして木を再構築する。
2つ目の配置の影響はその頂点と根の間にしか発生しないため
どこに置けば反転を多く解消できるか適当にDPする。O(N^2)
8/25 CF124-D1B 60 探索 ★★
8/26 CF149-D2E 40 数学 ★★ クエリ全体をbitごとに処理して、最後に足し合わせる
各bitごとの処理は、0-1列の反転と足し算を考えれば良い
8/26 CF149-D2D 60 グラフ ★★ 解は必ず存在する。count[i] = a[i] な i のボタンを押していけばいい
8/26 CF147-D2E 30 文字列 最小費用流
8/27 SRM589-D1M 20 グラフ ★★ 2つのギアの色の回転方向が同じと考え、2部グラフを作る。
3通りの組み合わせでフローを求め、それらの最小値が答え

その他

DateProblemStatTimeTagDifficulty解法メモ(ネタバレ注意)
8/9 SRM586-D2H 10 数え上げ minimum weightな文字列は、
文字の種類数が最大で同じ文字が連続する。
8/11 SRM582-D1E 10 探索 答えを決め打ちして二分探索。
なるべく強い敵から貪欲に倒す
8/12 SRM581-D1E 20 探索 ある位置について、カメラが置かれる可能性があるか、
必ず置かなければならないかをBruteForceする
8/12 SRM580-D1E 10 探索 うなぎの頭と尻尾が通過する時間だけを考慮すればよい
8/12 CF195-D2C 20 探索 普通にやる。 O(nlogk), k<=10^9
8/18 SRM579-D1E 10 探索 履歴にたまる文字列は履歴の利用の仕方に関係しない
8/18 SRM578-D1E 25 数え上げ 距離の制約からduckとgooseの塊がいくつかできるので、
それらを使いgeeseの総数が1以上かつ偶数になる組み合わせの数をDPする
8/20 CF188-D1A 20 数学 大きい方を小さい方に足すことを繰り返せばOK。
x>0&&y<0、x<=0&&y<=0のケースに注意する
8/20 CF187-D1A 20 数学 低い順位の人が抜けても、それ以上の順位のratingには影響しない
なので、1位から順番に処理すればOK
8/25 CF148-D1A 20 数学 dp[i] = dp[i-1] * (2^m - i), dp[0] = 1
1つずつ選択肢が減っていくと考える
8/25 CF124-D1A 10 文字列
8/26 CF147-D2C 15 数学 素数列挙+いもす法+二分探索