Hatena::Grouptopcoder

hama_DU@TopCoderへの道

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

9月目標達成できなかったのでやり方を変えてみる

目標

自分にとって、新たな知見が得られた問題をメモ。そのような問題に10問以上出会うこと。

状況

  • 0/10

解いた問題一覧

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

DateProblemStatTime Tag Difficulty解法メモ(ネタバレ注意)
-/- CFXXX-D1X -- -- -- --

ノーカウント

DateProblemStatTimeTagDifficulty解法メモ(ネタバレ注意)
-/- CFXXX-D1X -- -- -- --

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を取る

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 数学 素数列挙+いもす法+二分探索

2012-05-28ARC003

久々にコンテストの参加レポート。 3AC92分で 35位/300人ぐらい

問題結果タイム解法
AGPA計算+02:20実装
Bさかさま辞書+07:51文字列
C暗闇帰り道+262:16(+30)二分探索+BFS
Dシャッフル席替え--モンテカルロ法

ARC003 A GPA計算

|  ARC003 A GPA計算 - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  ARC003 A GPA計算 - hama_DU@TopCoderへの道

  • 一瞬。
    • 足して、平均を取るだけ。

ARC003 B さかさま辞書

|  ARC003 B さかさま辞書 - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  ARC003 B さかさま辞書 - hama_DU@TopCoderへの道

  • List<String> に反転した文字列を突っ込む。
    • new StringBuffer(S).reverse().toString()
  • ソートする。
    • Collections.sort()
  • 順番に出力。
    • 出力するときに反転を元に戻す

ARC003 C 暗闇帰り道

|  ARC003 C 暗闇帰り道 - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  ARC003 C 暗闇帰り道 - hama_DU@TopCoderへの道

  • 方針を考える。
    • ダイクストラする?
      • (現在位置,時間)を状態に持つ
      • 500 * 500 * 1000 ぐらいになっておそらく間に合わない。
  • しばらく考える
    • 二分探索で、通れる明るさの上限を決めてしまおう
      • これだと現在位置だけを状態に持てばいいので、 500 * 500 * (二分探索の回数) で済む。
    • これでよさそう。
  • 実装
    • 特に詰まること無くサクサク。
    • 各明るさの初期値 (i:1〜9) について、n時間たった時の明るさを予め dvalue[i][n] に計算しておく
  • 出してみる。
    • TLEしてしまう。あれ?
    • 二分探索で誤差がe-10ぐらいになったら打ち切るようにしてみる
  • 再提出
    • 今度はWA
    • 到達不可の場合は -1 を出力しなければならないが、その判定がミスってる
      • 二分探索する前に、到達可否を調べるコードを書いた。
  • 提出。やっとACがもらえた。この時点で残り30分。

ARC003 D シャッフル席替え

|  ARC003 D シャッフル席替え - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  ARC003 D シャッフル席替え - hama_DU@TopCoderへの道

  • これは難しそう・・・
  • 制約の小ささから、bitDP的なことができるのではと思ってみる
    • dp[K][P] : K回席替えした時、禁止パターンの出現組合せがPになってる確率
    • でも、更新式が思い浮かばない。
    • 紙に書いてみても、
  • 素直に順列を全探索か?
    • 制限時間10秒あるし・・・
  • 書いてる途中にコンテスト終わった

コンテスト後

  • 答えの誤差が 0.002 まで許されることから、モンテカルロ法が使えるらしい。
    • 実際にランダムにK回席替えをして、禁止パターンになってるかどうか調べるという実験をする。
    • 成功数 / 試行回数 が答え
  • 制限時間ギリギリまで実験するコードを書いたら通った。

2012-05-01SRM336,SRM337,SRM338 (Practice)

SRM336 (Practice)

SRM336 (Practice) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM336 (Practice) - hama_DU@TopCoderへの道

問題結果ポイントその他
250ServiceNamesAccepted196.25実装
500LikelyWordWA0.00実装
1000ShadowOpened0.00幾何

SRM 336 ServiceNames

|  SRM 336 ServiceNames - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 336 ServiceNames - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7313

  • ん?問題の意図するところがわからない・・・
    • サンプルから察するにやるだけっぽい

続きを読む

SRM 336 LikelyWord

|  SRM 336 LikelyWord - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 336 LikelyWord - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7351

  • 辞書順でdictionaries[i]の前に来る、長さkの文字列を数え上げる。
    • 区間は引き算して求められる
      • この時、dictionaries[i]の文字数がkであった場合、あとで数えないようにフラグを立てておく
    • 最後の区間は 26^k から (dictionaries[len-1] の前に来る文字列数) を引いて求める

続きを読む

SRM 336 Shadow

|  SRM 336 Shadow - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 336 Shadow - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7336

  • 問題文をナナメ読みしてそっと閉じた
    • 後でちゃんと解く。

SRM337 (Practice)

SRM337 (Practice) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM337 (Practice) - hama_DU@TopCoderへの道

問題結果ポイントその他
250CardStraightsWA0.00実装
500BuildingAdvertiseOpened0.00データ構造
1000CountPalindromesOpened0.00DP

SRM 337 CardStraights

|  SRM 337 CardStraights - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 337 CardStraights - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7417

  • し、しまった・・・(無能)
    • ジョーカーが余るパターンで、左に配置するパターンを考慮してなかった

続きを読む

SRM 337 BuildingAdvertise

|  SRM 337 BuildingAdvertise - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 337 BuildingAdvertise - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7473

  • 僕の苦手なデータ構造を利用するタイプの問題。
    • やり方がいろいろあるらしい(スタックを使ったり、分割統治法をしたり。)
    • 要復習

続きを読む

SRM 337 CountPalindromes

|  SRM 337 CountPalindromes - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 337 CountPalindromes - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7418

  • 典型的な文字列回文DP
    • 左右どちらかに余る文字列パターンは 15 * 15 * 2 * 50 = 22,500 なので、文字列 -> 数にエンコードして持っておく
    • どの文字列パターンにどの文字列を当てるとどの文字列パターンになるか、という状態遷移関数を前もって作成しておく。
      • これをやらないと多分文字列操作コストが重くてTLEする。
  • 時間はかかったが、一発ACできた。

続きを読む

SRM338 (Practice)

SRM338 (Practice) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM338 (Practice) - hama_DU@TopCoderへの道

問題結果ポイントその他
250ImprovingStatisticsAccepted239.03二分探索
500RandomSwapsAccepted416.29確率
1000CakePartyOpened0.00