Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-30SRM356 (Practice)

問題結果ポイントその他
250AverageProblemAccepted129.30DP
550MarriageProblemRevisedRE0.00グラフ
950EscapeTheJailWA0.00一次方程式

SRM 356 AverageProblem

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

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

  • 頭の悪いDPをした
    • DPで解ける余地を残してくれるあたり優しい

続きを読む

SRM 356 MarriageProblemRevised

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

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

  • 二部構造が見え見えになってるが、マッチングでは解けなさそう
    • 制約が緩いしDPしちゃおう
  • でも、少なくとも [男x12が結婚したか][女x12が結婚したか] という状態が必要だから・・・
    • (2^12) ^ 2 = 16M
    • メモリが足りなくなるかも・・・
  • ダイクストラを実装したらサンプル合った。
    • 他に方法が思いつかないのでそのまま出してしまった。

SRM 356 EscapeTheJail

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

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

  • ランダムウォーク。
    • 蟻本のまんま。
  • 練習ではあえて5万移動ぐらいの計算打ち切りDPを書いてみたけどWAした
    • 多分誤差が大きくなって正しい答えがでないんだと思う

続きを読む

2012-03-29SRM357 (Practice)

問題結果ポイントその他
250HotelAccepted248.42DP
500WebsiteRankWA0.00グラフ
1100ChipAreaOpened0.00幾何

SRM 357 Hotel

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

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

  • 制約見てDPだと思った
  • 速度勝負だと思ったのでEgor風に提出してからデバッグを敢行した

続きを読む

SRM 357 WebsiteRank

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

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

  • めちゃくちゃ簡単なのに解けなかった、(自分に対して)訴訟
    • 素直に実装するだけ

続きを読む

SRM 357 ChipArea

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

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

  • 頑張れば解けそう。
    • もうちょい考える
  • できた。
    • x座標の昇順にソートする
    • 各点を長方形の左端に置くことを考え、とりうるyの最小値と最大値を更新しながら見ていく。
      • そのままやると間に合わないけど点がランダムに分布するので枝刈りを仕込んでやると間に合った。やったー

続きを読む

2012-03-27SRM358 (Practice)

問題結果ポイントその他
250BrokenButtonsAccepted224.56ブルートフォース
500BalanceScaleOpened0.00数論、BFS
1000SharksDinnerUnopened0.00最大流

SRM 358 BalanceScale

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

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

  • 複数の数のgcdを取った時、1にする最小の個数を求める
    • 練習ではなぜか最小費用流を適用しようとしてハマる
  • シンプルなBFSで十分間に合う。

続きを読む

SRM 358 SharksDinner

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

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

  • こっちは最大流。
    • 各ノードを食べる側1、食べる側2、食われる側の3つに分割すると2部グラフになる

続きを読む

2012-03-26SRM360, SRM361 (Practice)

SRM360 (Practice)

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

寝落ち。

問題結果ポイントその他
250SumOfSelectedCellsOpened0.00難しい。editorial読んで解いた
500PrinceOfPersiaOpened0.00最大流。BruteForceしてもいいはず
1000ConvexArrayOpened0.00あとでやる

SRM 360 PrinceOfPersia

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

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

  • 最大流っぽい
    • 蟻本を見ながらグラフ構築。
    • この問題は「頂点に流量の制約がある場合」に相当する。
  • 出した。
    • WA。あれ?
    • グラフの作り方が違ってた・・・あとノード最大数は100じゃ足りない。
  • 修正したら通った。
  • ちなみに、Pの周りを#で囲めば必ず到達不可になるので、必要なブロックの数は高々4。
    • このことから、ブロックの置き方をすべて試すBruteForce解もあるんじゃないかと思う
      • 100C1 + 100C2 + 100C3 + 100C4 = 4M+α ぐらい。
      • 未検証

続きを読む

SRM 360 ConvexArray

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

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

  • 幾何っぽい絵が出てきたのでそっと問題を閉じた

SRM361 (Practice)

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

問題結果ポイントその他
250WhiteHatsAccepted225.46矛盾をチェック
500ReverseDistanceAccepted150.00再帰、全探索
1000WeighingScaleOpened0.00全然分からん

SRM 361 WhiteHats

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

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

  • 方針検討しながら行き当たりばったりで書いた
    • まず、各人が報告した数は2種類か1種類のはず
    • 1種類の時
      • 被ってる帽子は全て同じ色
      • 数が0なら全員黒、数が(人数-1)のときは全員白
    • 2種類の時
      • (報告した数の最大) - (最小) = 1 で、最大が白い帽子を被ってる人の数
      • さらに、大きな数を報告した人は全員黒、小さい数を報告した人は全員白
      • 以上を数えて検証する

続きを読む

SRM 361 ReverseDistance

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

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

  • 方針を検討
    • DP?状態の持ち方がわからない・・・
    • よく考えると求めるべき数の左半分が決まれば右半分も自動的に決まるので全探索でよさそう
      • 証明はできないけど求めるべき数の桁数は最大でもdifferenceの2倍程度な気がする
      • なので計算すべき量は O(10^6+α) ぐらいだろう
  • 実装。
    • 文字列インデックス指定ミスでしばらくハマる・・・
    • サンプル通った。
  • 最大ケース(900000?)を突っ込んでみる
    • 0.5sで終わる。答えも正しそう。
    • これは大丈夫だろ、出しちゃえ!
  • 再度戻ってくる。コード見直し
    • 繰り下がり処理ミスってる!
      • 繰り下がりフラグを立てたまま再帰から戻ってくるときに戻してない
    • 修正して再提出。なんでこれでサンプル通ったの・・・?

続きを読む

SRM 361 WeighingScale

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

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

  • 全く分からん・・・
    • 250と500の見直しに戻る

2012-03-25SRM362, SRM363 (Practice)

SRM362 (Practice)

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

問題結果ポイントその他
250MaximizeSquaresAccepted219.66数学
500PartialSeriesOpened0.00DP+経路復元
1000CoolRectanglesOpened0.00英語読めない

SRM 362 MaximizeSquares

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

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

  • 格子状に、なるべく正方形っぽく並べるのが一番いい気がする。
    • 反例があるかも・・・
  • 念のため、長方形を作る場合を全部試す
  • 続きを読む

SRM 362 PartialSeries

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

http://www.topcoder.com/stat?c=problem_statement&pm=8048
  • 経路復元付きDP
    • 状態数は [使った数字の組み合わせ][直前の数字][前回上がったか下がったかそのままか]
      • 2^15 * 11 * 3
  • 経路復元ができなくて死亡。
    • 他の人のコードを見て実装を勉強する
  • 解いた。
    • 辞書順最小で経路復元する必要がある場合はメモ化再帰で書くと見通しが良い
    • 状態も単純に [使った数字の組み合わせ][前回の数字][前々回の数字] として良い
      • その方が極値判定が楽で、バグが少なく実装できる

続きを読む

SRM363 (Practice)

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

問題結果ポイントその他
250HandsShakingAccepted233.21メモ化再帰
500MirrorNumberCompiled0.00再帰、全探索
1000PackageDeliveryUnopened0.00見てない

SRM 363 MirrorNumber

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

http://www.topcoder.com/stat?c=problem_statement&pm=7869
  • 方針を検討
    • DPする?
      • 先頭に2をつけたら後ろに5をつけなきゃいけない。
      • 「オーバーしたかどうか」フラグを管理するのが難しそう
    • 求めるべき数はそんなに大きくないはず。全探索でよさそう
      • 5^9 * 2 = 4Mぐらいだろ、だいじょぶだいじょぶ!
  • 実装
    • 10^18を突っ込むとTLEする
      • あれ!?
      • 文字列操作コストがそれなりに重いのかなぁ
    • やっぱりDPしなきゃダメか?
  • Editorial読むと全探索って書いてある
    • 選んだ数字を配列に入れてけばいいらしい。数字のまま処理するべし
    • 長さを決め打ちするって発想も出てこなかったなぁ

続きを読む

SRM 363 PackageDelivery

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

http://www.topcoder.com/stat?c=problem_statement&pm=7927
  • 見てない

後で

  • やってみた
  • サンプル通るけどWAする
    • 想定解法と違うっぽいので、あとでやる

続きを読む

2012-03-24SRM364 (Practice)

easyに時間かかったけどmediumがそこそこ速く出せた。2完早解きゲー

問題結果ポイントその他
300PaintballAccepted182.53実装ゲー
500PowerPlantsAccepted405.86ダイクストラ
1000YankeeSwapOpened0.00ゲーム?

SRM 364 Paintball

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

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

  • やるだけっぽい
    • バグらないようにオブジェクト指向っぽく実装
  • サンプル合わない。
    • 仲間を倒した場合得点マイナスになるのか
    • 直した
  • サンプル通った。出した。

続きを読む

SRM 364 PowerPlants

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

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

  • 2^16の状態を持ちながらダイクストラするだけ。
  • numPlants以上のplantsが生きてればいい(丁度でなくてもいい)ので注意

続きを読む

SRM 364 YankeeSwap

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

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

  • シミュレーションするだけ?
    • そんなことはなかった
    • 自分が良いものを手に入れるためには悪いものと交換されてはならない。
      • 誰と交換すべきかは先読みする必要がある
  • 待てよ。よく考えると一番最後の人は必ずベストなものが手に入るはず。
    • 逆から考えていけばいいのかな?
    • いや、それだけじゃ誰と交換すべきかはわからない
      • 最後の人にとって一番いいものを誰が持ってるか分からないので
  • 制約が N <= 20 なのが気になる・・・
    • N! は無理だけど 2^20 なら大丈夫?
    • 各人が欲しい物を手に入れたかどうかで探索?

2012-03-23SRM365 (Practice)

問題結果ポイントその他
300PointsOnCircleAccepted230.66数論
500ArithmeticProgressionsWA0.00???
1000RelabelingOfGraphUnopened0.00グラフ

SRM 365 PointsOnCircle

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

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

  • 好きなパターンの問題(数論ゲー)きた
  • 公式が提示されてるので、それを使うんだろう
    • 最大で 4*10^18 の数の約数を数えなければならない
    • 普通にやるとTLEするので、対策を考える
  • 実験。
    • ある約数と、その二乗の約数を書きだしてみる。
      • 12 = 1, 2, 3, 4, 6, 12
      • 144 = 1, 2, 3, 4, 6, 9, 12, 16, 24, 36, 48, 72, 144
    • 二乗の約数は元の約数の何かと何かをかけ合わせた数になってるんじゃないか?
      • 36 = 6 * 6, 72 = 6 * 12, 144 = 12 * 12
    • きっとそうだ!直感的にも正しいように思える
  • 実装。
    • Setを使って重複しないように気をつけながら数え上げる
  • サンプル通った。
    • 小さめのケースでテストしようとしたがサンプルで網羅されてた
    • 大丈夫っぽい。
  • 提出

続きを読む

SRM 365 ArithmeticProgressions

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

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

  • 方針検討
    • 数列のうち3つを使って等差数列を作る場合を全探索でよさそう
      • 50 ^ 3 = 125,000通り
  • 実装中・・・
    • 数列の個数を求めるのに苦労する
      • Mを超えないdで割ってmod余る数
      • m以上のdで割ってmod余る数
    • ↑の数を求める実装に苦労する。
  • できた。
    • なんかバグっててサンプル合わない・・・
    • そもそも方針合ってるのかな・・・
  • 時間がない(<3分)ので無理やり帳尻をあわせて提出

SRM 365 RelabelingOfGraph

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

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

  • 練習では解く時間なかったけど、1000もやってみよう
  • あんまり難しくはなかった。
    • こっちが500でいいような気がする
  • やりかた。
    • WFして各ノード同士がつながってるか調べる。
    • 先頭から順番に見ていき、
      • まだラベルを付けてない&自身に繋がってるノードがあれば
      • そっちを先にラベリングする
  • これで通ってしまった。

続きを読む

2012-03-22SRM366 (Practice)

問題結果ポイントその他
250ChangingSoundsAccepted239.50DP
500GuitarConcertWA0.00全探索
1000LateForConcertWA0.00ダイクストラ法

SRM 366 ChangingSounds

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

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

  • [現在位置][音量]でDPする
    • 50 * 1000 = 50,000
  • 書いた。サンプル通った。
    • これはスピード勝負な気がするのでそのまま出した。

続きを読む

SRM 366 GuitarConcert

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

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

  • ギターの数が少ないので、全探索するだけに見える
    • 2^10 *10 * 50 = 500,000 ぐらい
  • ゴリゴリ書く。
    • サンプル通った。
    • 特に間違ってない気がするのでそのまま出した
  • WA
    • そうか、比べる前にソートしなきゃいけないのか
    • 直したら通った。
    • 続きを読む

SRM 366 LateForConcert

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

http://www.topcoder.com/stat?c=problem_statement&pm=7827
  • [現在位置][直前の方向][時間]でダイクストラするだけかな?
    • 50 * 50 * 4 * 100 = 1,000,000
  • 書いた。サンプル通った。
    • 見なおしして出した
  • WA
    • あれ?
      • しばらく原因が分からず・・・
    • 問題を読みなおす。
    • Determine the route that will take you to the concert hall in exactly timeLeft seconds.
      • と書いてある。
    • timeLeftだからtimeLeft以内に着けばいいのかと思ってた
    • ゴールとして採用する状態をtimeLeftぴったりのみに直したら通った。

続きを読む

2012-03-21SRM367 (Practice)

0完。

問題結果ポイントその他
250ObtainingDigitKWA0.00陰湿なコーナーケース
500DeviceProgrammingTLE0.00DP
1000WSNParentsAssignmentUnopened0.00見てない

SRM 367 ObtainingDigitK

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

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

  • 方針を検討
    • 一番下の桁だけ見ればいいんじゃないの
    • 書いてサンプル合った
  • いや、待てよ
    • 例えば "15", 2 のとき、最適は 5 を足して十の位を 2 にすべき
    • 危ない危ない。繰り上がりを考慮したコードに書き換える。
  • WA
    • "99999", 1 で死んでた
    • そうか、桁がひとつ増える場合を考慮してなかった
    • 先頭に '0' を付加したら通った
  • 他の人のコード見る
    • みんなBigIntegerでやってる・・・
      • そもそも求める数は高々9だよね。
      • 1〜9までの数字を足して k が含まれてるかどうか見ればいい
    • ライブラリゲーかよ、くそっ

続きを読む

SRM 367 DeviceProgramming

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

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

  • 強烈なDP
    • 座標圧縮して適当にやればいい気がした
    • メモリの位置先頭(末尾)から (maxPacketSize - overhead) 進めた(戻した)位置を記録
      • トータルで 50 * 1000 * 2 = 100,000
    • dp[位置] = 現在位置まででパケットを区切るときの最小バイト数
      • 遷移数は高々1000(どの末尾まで考えるか)でいいはず
      • トータルの計算量は 100,000 * 1,000 = 100,000,000 ちょっと危ないか・・・?
  • 大丈夫大丈夫!
    • 暗示をかけながら提出
  • TLEする
    • やっぱり適当じゃダメか もっと考えなきゃ
  • 通した。そもそも方針が間違ってた
    • i番目からj番目まで(inclusive)を載せるコストを cost[i][j+1]として前計算
    • i番目まで載せるコストをdpで計算する

続きを読む

2012-03-20SRM368, SRM369 (Practice)

SRM368 (Practice)

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

2連続0完 するめ直前なのに・・・

問題結果ポイントその他
250JumpingBoardTLE0.00再帰
500PolylineUnionWA0.00幾何+ブルートフォース
1000BinaryCodesOpened0.00グラフ?

SRM 368 JumpingBoard

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

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

  • 方針を検討
    • ダイクストラっぽいことをすればいいよね
    • 同じ所に戻ってきたら-1で
  • いやまて、それじゃダメだ
    • ある場所に到達するのに2つ以上の経路があると詰む
  • 別の方法を考える
    • 幅優先で書いて単純にステップ数が上限(2500ぐらい)を超えたら-1でいいのでは
  • サンプル通ったので出した
    • TLEした
    • ちゃんとメモ化再帰で書かないとダメでした
  • 計算量の見積もりが甘かった・・・

続きを読む

SRM 368 PolylineUnion

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

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

  • 幾何ゲーから逃げない。
    • 点と点が一致するか
      • 単純に全部調べる
    • 点が線分のどこかと一致するか
      • 内積が0以上かつ外積が0かどうか調べる
    • 線分と線分が交差するか
      • 線分交差判定を書く。
      • 2点がもう一方の線分それぞれのどちら側かを外積を使って判定x2 両方共逆側になってたら交差してる
  • サンプル通った。
    • 交差判定とかintで書いちゃったけど大丈夫かな・・・
    • 条件を見ると (座標) <= 10000 みたいなこと書いてある。
      • 最大で(座標^2) <= 100,000,000 だからintでも大丈夫だろう
    • ある折れ線とある折れ線が交差したかどうかはUnionFindで管理
  • 出した。
    • WA食らう
    • よく見ると、線分の交差判定で (外積) * (外積) < 0 という計算をしてる。
      • それじゃintだとダメだよ・・・
        • (座標) ^ 4 になるので
      • longに直したら通った

続きを読む

SRM369 (Practice)

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

1000 > 250 > 500 だが0完 310/584位

全体的に難しい回だったらしい。500は通したかったなー

問題結果ポイントその他
250BeautifulStringOpened0.00貪欲法
500AbsSequenceWA0.00シミュレーション
1000MountainMapOpened0.00グラフ?

SRM 369 BeautifulString

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

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

  • これはダメだ、分からん
    • 適当にやるだけっぽいが明らかにサンプルが弱い
    • 先に500を見よう

続きを読む

SRM 369 AbsSequence

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

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


  • 方針を検討
    • 少し実験してみると、3つ組で考えたとき規則性があることに気づく
    • コーナーケースに注意してシミュレーションする
  • (a, b, c) で aが最大かつcが最小になるまで回す
    • min(a, b) / (c * 2) で規則が変わる瞬間が分かる
    • (min(a, b) / (c * 2)) * 3 が回すターン数を超えていたらその周期の中に答えはある

続きを読む

2012-03-19SRM370 (Practice)

hardは典型っぽい問題だけど好き 293/561位 半分以下爆死

問題結果ポイントその他
250DrawingMarblesAccepted243.30確率
500ConnectTheCitiesWA0.00二分探索+DP
1000NumberOfDivisorsWA0.00数論+DP

SRM 370 DrawingMarbles

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

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

  • 数学。
    • 各色について確率を計算し、足し合わせる。
    • colors[i] < n の場合に注意する。

続きを読む

SRM 370 ConnectTheCities

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

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

  • dp[使った数][前回の位置][最大距離]で考えてみたがWA
    • 距離を決め打ちし二分探索するのが正解らしい
    • あとでちゃんと通す

SRM 370 NumberOfDivisors

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

http://www.topcoder.com/stat?c=problem_statement&pm=7863
  • 約数がちょうどk個の数の中で、最小のものを求める
    • p={2,3,5,7, ... } を素数の列とする。
    • A = p1^a1*p2^a2* ... * pn^an と素因数分解できるとき、約数の個数は (1+a1) * (1+a2) * ... * (1 + an)個
    • [掛け算の結果][素数をどこまで使ったか]の最小値でDPする
    • 素数は47まで考えれば十分 (2*3*5*...*53 > 10^18なので)
  • 練習ではオーバーフローしてWA
    • BigIntegerに書き換えたら通った。

続きを読む

2012-03-17SRM371, SRM372 (Practice)

SRM371 (Practice)

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

(比較的簡単と思われる)hardが解けなかった上easyに時間を食ったので終わってる

160/637位

問題結果ポイントその他
250SpiralRouteAccepted135.90数学、場合分け
500ChessMatchupAccepted478.99最小費用流
900RaceOrderingOpened0.00グラフ

SRM 371 ChessMatchup

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

http://www.topcoder.com/stat?c=problem_statement&pm=7726
  • ソートしてGreedyで行ける気がするけど安全策をとって最小費用流で。
  • 続きを読む

SRM 371 RaceOrdering

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

http://www.topcoder.com/stat?c=problem_statement&pm=7703
  • グラフで考えればいい気がする
    • 制約条件のある頂点をグループ分けして、そのグループの配置位置をnCrしようとした

後で

  • ↑の方針で解いた。

続きを読む

SRM372 (Practice)

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

3完。全問簡単だった 19/589位
問題結果ポイントその他
250RoadConstructionAccepted167.04シミュレーション
500RoundOfElevenAccepted335.61DP
1000RadarGunsAccepted794.95最小費用流

SRM 372 RoadConstruction

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

http://www.topcoder.com/stat?c=problem_statement&pm=8223
  • 問題分の通りに愚直にシミュレーションする
    • それだけなのだが、20分もかかってしまった

続きを読む

SRM 372 RoundOfEleven

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

http://www.topcoder.com/stat?c=problem_statement&pm=8005
  • どの桁をいくつ動かすか選択しながらDPする
    • k(0-indexed)桁目でx数字を増やすと、mod 11が (10^k*x) % 11 ずれる
    • あらかじめ (10^k) % 11 の値を求めておけば計算の手間が減らせそうだ
  • 状態は dp[桁数][残り使えるお金][mod11]

続きを読む

SRM 372 RadarGuns

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

http://www.topcoder.com/stat?c=problem_statement&pm=8143
  • え、何これ
    • 罰金の最小値は最小費用流そのもの。
    • 得られる罰金の最大値は各辺のコストを(適当にでかい数 - 罰金)として、(適当にでかい数) * 車の数 - 最小費用流 とすればいい
  • ライブラリをはっつけゲーでした
    • 今のするめ環境ではこんな見え見えなのは出たりしないはず・・・

続きを読む

2012-03-16SRM373 (Practice)

通せるはずの500を落としてしまった 167/377位

問題結果ポイントその他
250StringFragmentationAccepted187.10二分探索
500RoadCrossingWA0.00ギリギリを考えよ
1000SpiralConstructionOpened0.00幾何+DP

SRM 373 StringFragmentation

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

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

  • 文字を小さくすればフレームに収まらないということはないはず
    • 二分探索しよう

続きを読む

SRM 373 RoadCrossing

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

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

  • こういう問題のコツはギリギリの状況を考えること
    • 車が通れるか通れないかは特定の時間だけ調べればOK
    • 歩行者のペアについて、距離がちょうど車のサイズになった時間を全て列挙する
    • あと念のため、車が到着した時間、各歩行者についても候補に追加する
  • サンプル通った。提出
  • なぜかWA。方針はあってるはずだが・・・
    • 時間を求める計算式が間違っていた・・・
      • こういうのは頭の中で考えずちゃんと紙に書いて定式化すべき
    • 何故サンプルが通ったのか

続きを読む

SRM 373 SpiralConstruction

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

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

  • 点の数が少ないからbitDPするんだろう
    • 状態は dp[使った点の組み合わせ][前回使った点][前々回使った点] でよいはず
      • 2^15*15*15 ≒ 7M
    • 線分が交差するか調べなければならないが、どう書くんだろう
      • 使った点の組み合わせだけでは直線は再現できないはず
    • あらかじめ4点のペアについて2線分が交差するかどうか前計算しておけばいい?

続きを読む

2012-03-15SRM374 (Practice)

mediumが後で読むと簡単な問題であることがわかりすごく悔しい 417/551位

問題結果ポイントその他
250SyllableSortingAccepted175.97強実装
500PlayerExtractionOpened0.00問題文が読めなかったのでhardに逃げた
1000CommercialPlannerWA0.00hardに逃げた結果がこれだよ!

SRM 374 PlayerExtraction

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

http://www.topcoder.com/stat?c=problem_statement&pm=8225
  • ごちゃごちゃ書いてあるが、要はbfsでthreshold以上の連結エリアを探して中心座標を求めるだけらしい
  • 続きを読む

SRM 374 CommercialPlanner

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

http://www.topcoder.com/stat?c=problem_statement&pm=8284
  • 単純に他のコマーシャルの直後を調べてけばいいんじゃないかと思ったが、0秒目を考慮するのを忘れてた
  • あとで解く

2012-03-13SRM375 (Practice)

mediumが残念な回。easyとhardの問題は割りと好き 49/420位

問題結果ポイントその他
250DivisibleByDigitsAccepted212.39数論
500DateFieldCorrectionAccepted309.38グラフを作る実装ゲー
1000DukeOnLargeChessBoardOpened0.00場合分け?

SRM 375 DivisibleByDigits

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

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

  • 数論ゲーきたこれ
    • 割るべき数は1〜9のどれかだから、まず出現する数字のLCMを求めてしまおう
  • 方針を考える
    • 初期状態で割り切れればそれで終了
    • そうでなければ、数字を1つずつ追加していくとして・・・
      • 10^a倍すると、残り必要な数も自動的に分かるから、それが0〜(10^a-1)に収まってるかで判定すればよさそう
  • 書けた。サンプル通った。
    • 小さめの数で変なことが起こらないか確認する。
    • 大丈夫。
  • 出した

続きを読む

SRM 375 DateFieldCorrection

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

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

  • 要するに、キー配列の編集距離グラフをあげるから候補の中で編集距離が最も短いのを返してねということらしい
    • 実装ゲーすぎる・・・
  • グラフをしこしこ作る。
    • "1234567890", "qwertyuiop" ... みたいな文字列変数を用意してforで回してグラフを作る
    • 各文字同士の編集距離はワーシャルフロイド法で予め求めておく
  • 後は366候補に対して全探索。
  • サンプル通った。
    • コーナーケースチェックする気も起きない。
  • 出した。酷い問題だった
  • 続きを読む

SRM 375 DukeOnLargeChessBoard

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

http://www.topcoder.com/stat?c=problem_statement&pm=8317
  • 余力があるのでhardに挑戦
  • 右 > 上 > 下 > 左 の優先順位でまだ行ってないマスに移動していく時、詰んだ時の位置を返しなさいという問題か
    • 問題名の通りフィールドがでかいのでシミュレーションは無理そう。
  • 4x4マスぐらいのフィールドを紙に書いて、手で実験してみる。
    • 規則っぽいのが見えないが、細かく場合分けしていけばいい気がする。
  • 場合分けコードを書く。
    • 端っこにいる場合は簡単だけど、真ん中にいる場合が難しい・・・
    • 偶奇で最終位置が変わる気がする
  • 分からん・・・
  • 時間切れ

2012-03-12SRM376 (Practice)

0完で大敗北。本番じゃなくてよかった・・・ 317/437位

問題結果ポイントその他
250TrainyardWA0.00幅優先探索
500MarbleMachineWA0.00行列累乗
1000UnjumpersUnopened0.00見てない

SRM 376 Trainyard

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

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

  • 方針を検討
    • ふつーにBFSしてカウントすればいいか
  • 実装
    • 意外と手間どう・・・ 連結であるかどうかの判定など
    • げ、もう10分もかかってる。制約小さいしかんたん実装して出しちゃえ!

システムテスト

  • あっさり落ちた。
    • やっぱ適当じゃダメだね・・・
    • 一度たどり着いた場所は枝刈りするように変更

続きを読む

SRM 376 MarbleMachine

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

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

  • 方針を検討
    • これ一定時間ごとに線形で増えていくんじゃないかな
    • 全体で見ても各machineのactionは30で一巡する
    • とりあえず30ターンごとにやってみて、実験して規則っぽいのを探すか
  • 実装
    • バグりまくってバグの解消に40分消費。
    • できた。
  • 実験
    • 30ターンごとに見ると、サンプルでは見事に線形で増えていってる。
    • 時間がないし、これで出しちゃうか
    • 30 * (t / 30) 実行したことにし、その後 (t % 30) シミュレーションを回す。
  • サンプル通った。
    • 時間ないし提出!

続きを読む

agwagw2012/03/15 15:36はじめまして、いつも楽しみに拝見させていただいております。id:agwと申します。

初学的な質問で大変申し訳ないです。Practice Roomでの過去問に対してシステムテストを行っているとのことですが、どのようにやっていらっしゃるのでしょう?

hama_DUhama_DU2012/03/15 16:02上部メニュー -> practice options -> run system test からできます

agwagw2012/03/15 16:18試してみました。どうもありがとうございます!

本番では一つでも失敗したらシステムテストを落とす、という解釈でよいのでしょうか?

hama_DUhama_DU2012/03/15 16:56もちろんそうです!
一つでも失敗したらポイントの部分が赤く表示されるので、そうなると本番ではfailed system testということになります。

agwagw2012/03/16 03:34なるほど、理解しました。どうもありがとうございます!

2012-03-11SRM377,SRM378,SRM379 (Practice)

SRM377 (Practice)

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

Match Resultがないので自分の相対的な実力は分からないが、2完できたのでそんなに悪くはないはず。

ノーコン回だったのかな?

問題結果ポイントその他
250SquaresInsideLatticeAccepted185.32数え上げ
500GameOnAGraphAccepted351.83行列累乗
950AlienLanguageOpened0.00数学、行列累乗

SRM 377 SquaresInsideLattice

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

  • 方針を検討
    • 正方形カウントして出すだけかな?
  • サンプル合わない。
    • 軸に並行じゃない正方形も数えなきゃなのか
  • 書いて出した

続きを読む

SRM 377 GameOnAGraph

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

  • 方針を検討
    • 行列累乗するだけっぽい
    • whiteの操作の行列をW、blackの操作の行列をBとおく
    • Nターンの操作の行列は (BW)^(N/2)
      • ただしNが奇数の時はWを左からもう一つかける
    • こうしてできた行列に初期値をかければ答えが求まる
  • 特に罠はないっぽい。簡単すぎる・・・

続きを読む

SRM 377 AlienLanguage

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

  • 数式をごにょごにょすると行列累乗の形に持っていける
public class AlienLanguage {

	public long[][] pow(long[][] a, long n, long mod) {
		long i = 1;
		long[][] res = E(a.length);
		long[][] ap = mul(E(a.length), a, mod);
		while (i <= n) {
			if ((n & i) >= 1) {
				res = mul(res, ap, mod);
			}
			i *= 2;
			ap = mul(ap, ap, mod);
		}
		return res;
	}
	
	public long[][] E(int n) {
		long[][] a = new long[n][n];
		for (int i = 0 ; i < n ; i++) {
			a[i][i] = 1;
		}
		return a;
	}
	
	public long[][] mul(long[][] a, long[][] b, long mod) {
		long[][] c = new long[a.length][b[0].length];
		if (a[0].length != b.length) {
			System.err.print("err");
		}
		for (int i = 0 ; i < a.length ; i++) {
			for (int j = 0 ; j < b[0].length ; j++) {
				long sum = 0;
				for (int k = 0 ; k < a[0].length ; k++) {
					sum = (sum + a[i][k] * b[k][j]) % mod;
				}
				c[i][j] = sum;
			}
		}
		return c;
	}
	
	public int getNumberOfWords(int P, int Q, int N, int M) {
		long[][] p3 = {
			{P, P, 1},
			{0, P, 1},
			{0, 0, 1}
		};
		p3 = pow(p3, N, M);
		
		long[][] q3 = {
				{Q, Q, 1},
				{0, Q, 1},
				{0, 0, 1}
			};
		q3 = pow(q3, N, M);
		
		
		long p = (p3[0][0] + p3[0][1] + p3[0][2]) % M;
		long q = (q3[0][0] + q3[0][1] + q3[0][2]) % M;
		long pq1 = ((p * q) - 1 + M) % M;
		
		
		return (int)pq1;
	}
}

SRM378 (Practice)

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

数学回。またもや2完できず。easy早解きゲーだった模様 226/540位

問題結果ポイントその他
250TrueStatementsAccepted244.45速攻
500SolvePolynomialOpened0.00方針立たず。
1000TwistyPassagesOpened0.00無理

SRM 378 TrueStatements

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

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

  • 方針を検討
    • 「真実を言ってる人の数」と同じ事を言ってる人の数を数えて一致してたらそれの最大値でOK
  • 速攻で実装、サンプルを通す
    • 早解き勝負な気がするのでノーチェックで出す

続きを読む

SRM 378 SolvePolynomial

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

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

  • 方針を検討
    • 2分探索?
      • いや、多分無理・・・
    • 解の候補を幾つか出してそれを試していけばいいのかなぁ
    • 分からん・・・

その後

  • 他の人のコードを読む。
    • なんか約数をとって候補としてる
      • なぜ?
    • あ、そっか
      • (多項式) = (x-a1)(x-a2)(x-a3) .... (x-an) と因数分解できるとする。
      • すると一番次数の小さい項は a1 * a2 * ... * an になってるはずだから・・・ということか
    • 定数項が0だったら候補を0に追加
    • 一番次数の小さい項xについて、x % i == 0 な i に対し i, -i, x/i, -x/i を候補に追加
  • 求めた候補に対して式を実際に計算し、0になるかどうか確かめる。
    • BigInteger使えばいいのかな・・・TLEしそうな気もするが
      • やっぱりダメだった
    • 他の人のコードを読むと、でかい素数のMODを2つぐらい取って0だったらOKとしてる
      • そんな適当でいいのか・・・?
  • そう書いたら通った。腑に落ちない・・・

続きを読む

SRM379 (Practice)

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

197/391位

問題結果ポイントその他
250SellingProductsAccepted224.31簡単
500FillBoxWA0.00素で間違えた 猛省
1000TVGameUnopened0.00-

SRM 379 FillBox

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

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

  • 使えるCube数が無限大と仮定した時、各大きさのCubeが何個必要か求めておく
  • 大きいCubeから貪欲に使っていってOK
    • n段階小さいCubeで大きいCubeを代用するには pow(8, n)個必要
    • オーバーフローに注意する

続きを読む

utmathutmath2012/03/26 13:34SRM378 Medium 落としておきました。

hama_DUhama_DU2012/03/26 17:27うっ、嘘解法でしたからね・・・
どんなケースで落としたのか教えていただけるとうれしいです。

utmathutmath2012/03/27 15:563552*x^25 + 730*x^20 + 886*x^15 + 68*x^10 + 160*x^5 + 62*x + 4 です。x = 4 を代入すると、4 * (10^9+9) * (10^9 +7) になり、どちらで mod をとっても 0 になってしまいます。

hama_DUhama_DU2012/03/29 16:19なるほど、ありがとうございます。
というかこんなケースよく見つけましたね・・・

2012-03-10SRM380,SRM381,SRM382 (Practice)

SRM380 (Practice)

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

1完爆死 225/465位

問題結果ポイントその他
250LameKnightAccepted175.79数学ゲー
500CompilingDecksWithJokersOpened0.00数学ゲー?
1000NestedDiamondsUnopened0.00見てない

SRM 380 CompilingDecksWithJokers

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

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

  • 圧倒的数学ゲー
    • いい問題
  • カードの残り数でソート
    • 一番小さな数 a が n個あって、その次に大きな数がb個あったら・・・
    • aとbが等しくなるには何枚ジョーカーを使う必要があるかで式を立ててゴニョゴニョ
  • n=1かつa=0のときに注意する

続きを読む

SRM381 (Practice)

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

2本目。そこそこの速さで2完できた 47/577位

問題結果ポイントその他
250TheDiceGameAccepted210.09動的計画法
500TheHomeworkAccepted313.22メモ化再帰
1000TheSquaresOpened0.00-

SRM 381 TheDiceGame

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

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

  • あ、Theの人だ(Vasyl回)
  • 方針を検討
    • 数学ゲーと思いきや、制約ゆるい(N <= 1,000,000)のでDPしようかな
    • メモ化再起で書くとStack Overflowしそうなのでループで書く
  • 実装
    • もらうDPをループで書くのに慣れてなくてしばらく戸惑う・・・
      • メモ化再帰で書けるなら直感的にかけて好きなのに
  • サンプル通った
    • 最大ケースでチェック。提出

続きを読む

SRM 381 TheHomework

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

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

  • 方針を検討
    • うーむ
    • まず、サンプルが理解出来ない
      • 例えばsample3。これ挿入が9回と削除が2回必要で、どう考えても4回の操作でできるはずがないのだが
    • 問題文に戻ってみる。しばらく理解できなくて悩む
  • あっ
    • 複数回の挿入・削除・変更をまとめて1回と数えるのか
    • sample3なら
{12,13}
{12,13,1,1}
{12,13,1,1,1,1,1,1}
{12,13,1,1,1,1,1,1,1,1,1}
{1,1,1,1,1,1,1,1,1}
    • で4回
    • そうと分かれば話は簡単。
    • 「現在の長さ」「余分な物の数」「必要なものの数」を状態に持って探索してやればいい
  • 実装
    • dfsでメモ化再帰を実装
    • 必要なものの数以上に数を足すと、余分なものが増えるが・・・
      • 余分なものを増やしたほうが得する場合はあるのだろうか
      • 逆に、必要なものを削ったほうが得する場合はあるのだろうか
    • とりあえずない気がするのでそのケースは考えないでおく
  • サンプル通った。
    • 配列サイズチェック
    • 追加テスト
      • {1}, {2}x50
      • {2}x50, {1}
      • {1}x50, {2}x50
  • 多分大丈夫。提出
    • 提出後、余分な操作について考える
    • 余計なことをすると、余計なことをした分の埋め合わせ操作が必要になる気がするなぁ
    • ということで多分今のコードで大丈夫だ。

続きを読む

SRM382 (Practice)

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

2完ならず。mediumは難しくなかったが解けなかった・・・ 173/438位

問題結果ポイントその他
250CollectingRidersAccepted150.17前計算して全探索
500PointsOnACircleOpened0.00グラフ
1000CharmingTicketsUnopened0.00見てない

SRM 382 CollectingRiders

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

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

  • 方針を検討
    • とりあえず、dx,dy進むのにかかる手数を前計算してしまおう
  • 実装
    • BFSで実装。OFFSET = 15, MAX = 30 ぐらいでゴリゴリ書く
  • いや待て、壁があるからそう単純にはできない
    • やはり、(a,b)から(c,d)に進む最小手数を全部計算する必要が有りそうだ。
      • だが、最大サイズは10なので十分間に合うだろう。
  • 実装
    • 書いてしまったBFSの部分を使いまわす
    • 境界判定に番兵用意したいけど、最大2マス進めるし配列番号の扱いも面倒になりそうなので、愚直にif文で判定することにした
  • できた。サンプル通った。
  • コーナーケース確認して提出。

続きを読む

SRM 382 PointsOnACircle

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

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

  • 方針を検討
    • とりあえず、1度から359度回してみて一番いいのを選べばいいだろう
    • グラフにしてみるとフローで解けるかな?
      • 0〜359までのノードを考え、赤と青のノードに分割して考える
  • サンプル合わない・・・
    • 同じノードを2回使ってしまっていることに気づく。
    • フローじゃ解けない
    • いやそもそもフローなんて高等なもの使わなくていい気がする。
      • 一つの点からは高々一つの点にしかいかないんだし・・・
  • しばらく唸って時間切れ。

その後

  • 単純に、連結してるノードを数えてやればいいだけだった
    • ノードは単純に分割せず考える
    • ループが発生する場合に注意する
    • 続きを読む

2012-03-09SRM383,384,385 (Practice)

SRM383 (Practice)

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

三本目。 Mediumが既視だったのでノーコン。

問題結果ポイントその他
250PlanksAccepted219.42全探索
500FloorBoardsAccepted262.13最強最速アルゴリズマー
1000PyramidPuzzleOpened0.00解ける気がしない

SRM 383 Planks

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

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

  • 方針を検討
    • 切る長さを決め打ちして全探索でいこう
  • 実装
    • 切る長さでちょうど割り切れる場合に注意する。うなうな
  • 最後のサンプルだけ通らない。
    • 切らないほうが得する場合もあるのか
    • サンプル親切だなぁ
    • ある板について、切断コストが得られる利益を上回ってればパスするよう変更
  • 提出

続きを読む

SRM 383 FloorBoards

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

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

  • 既視感がある問題。
  • 方針を検討
    • 解説ではO((2^W)^2 * H)の動的計画法(ループ)で解いてるが、今回はメモ化再帰で解いてみよう
    • dfs(i, j, ptn) i行目j列目において、直前W個の縦横線のパターンptnについて考える
      • 縦棒を使うか横棒を使うかという選択は直前W個さえ知ってれば十分
      • 計算量 O(W*H*(2^W))
  • 実装
  • サンプル全然合わない。なぜだー
    • 次の状態を見る時 dfs(i, j+1, ptn*2) ではなく dfs(i+1, j, ptn*2)としてた・・・
    • その他にもいろいろ間違ってた
  • サンプル通った。最大ケース確認して提出
    • 見たことある問題の割に解くのが遅い・・・

続きを読む

SRM384 (Practice)

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

本日二本目。 57/390位

問題結果ポイントその他
250LibraryAccepted243.87早解きを意識
500SchoolTripAccepted258.80非常に小さい確率は無視出来る
1000ChessTrainingOpened0.00問題を見てそっと閉じた

SRM 384 Library

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

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

  • 方針を検討
    • 条件に合うDocumentを数えればいいらしい
    • 同じDocumentを数えてしまわないようにSetで管理する

続きを読む

SRM 384 SchoolTrip

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

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

  • 方針を検討
    • また制約甘い系か・・・
    • ボールを持ってる人、生き残ってる人のビットパターンでDPしちゃおう
    • dfsで書くのが楽だよね
  • 実装
    • これ一周誰もヒットせずに同じ人に戻って来ちゃう場合もあるのか。
      • どうしよう・・・ これだとdfsが終わらない
    • しばらく考える。数式に落としてみたりとか。
      • うまくいかない・・・
  • 制約を見る。
    • ヒット率は最低でも0.1以上
    • 0.9 ^ 200 < 10^-9 だから、200回以上連続でヒットしなかった場合の確率はほぼ0で、答えの要求する精度に対して無視出来る
    • 計算量的に余裕あるし、500回以上ヒットしなかったら0を返すようにしよう
  • サンプル通った。
    • 最大ケース {10, 10, 10, 10, 10, 10} で確認
      • 0.1sで通った。余裕
  • 出した

続きを読む

SRM385 (Practice)

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

Petr回 153/563位

問題結果ポイントその他
250UnderscoreJustificationAccepted167.30相変わらず素早く解けない
500TurningMazeAccepted262.97実装重めダイクストラ
1100InfiniteAdditionUnopened0.00辿りつけなかった

SRM 385 UnderscoreJustification

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

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

  • 方針を検討
    • コーナーケースとかこわいし、各文字列の間にアンダースコアを何個配るかでDPしちゃおう
    • 計算量は O(文字列数 * アンダースコアの数 ^ 2) まぁ余裕
  • 実装
  • サンプル通らない。
    • なんで!?自分の解が間違ってるとは思えない。
    • 問題を読みなおしてみる
      • なるほど・・・、なるべくアンダースコアを均等に配らなきゃなのか
    • これひょっとしてDPしなくてもいけたんじゃ・・・
  • アンダースコアを使う数を2つに制限するようにDPを書き換える
    • サンプル通った。
  • 出した

続きを読む

SRM 385 TurningMaze

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

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

  • 方針を検討
    • 制約甘い・・・またbitDPか
    • どの行と列が反転してるかのフラグを持ちながらダイクストラすればよさそうだ
      • 状態数は 2^14 * 7 * 7
    • 今いる位置(nx, ny, 0-indexed)で反転操作を行うと、nx桁目とny+7桁目のbitを入れ替える
    • 今いる位置が反転してるかどうかは、nx桁目とny+7桁目のXORをとって確認する
  • 実装
    • 重い・・・
    • 各部屋の状態について、ドアが使えるかどうか配列を用意するなど工夫した
  • 最後のサンプルだけが通らない 正解「6」に対して「4」を返した
    • 手で確認してみる
    • あれ、これ4手(下、右、右、下)でいけるのでは・・・
  • 問題を読みなおす
    • そうか、ドアがつながってなきゃ通れないのか
      • 南に行くときは南の部屋の北のドアがないと通れない
  • 行き先のドアについても調べる実装を追加
    • サンプル通った。
  • 念のため最大ケース(7x7, ABCDランダム)で確認
    • TCサーバで0.4s 大丈夫だろう。
  • 提出
  • editorial曰くただのBFSで通るらしい
  • 続きを読む

2012-03-08SRM386 (Practice)

また解けるはずの問題を落としてしまった。 211/598位

問題結果ポイントその他
250CandidateKeysAccepted188.97ブルートフォース
500PolygonCoverWA0.00誤差死
1000EscapeArtistOpened0.00実装間に合わず

SRM 386 CandidateKeys

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

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

  • 方針を検討
    • column <= 10か・・・ 普通にsuperkeyかどうかを全探索かな
      • 全探索後、各superkeyについてcandidateかどうかsubsetを取りながら調べる
    • 計算量は 2^10 * 50 * 10 + (2^10)^2 = 1,500,000ぐらい 意外と大丈夫だ
  • 実装
  • サンプル通らない。
    • あれ
    • 最大値の更新が間違ってた・・・ ここで5分ほどロスする
  • 念のため、50x10の最大ケースでテスト。
    • OK
  • 提出

続きを読む

SRM 386 PolygonCover

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

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

  • げぇっ、幾何ゲーだ
  • 方針を検討
    • よく読むと幾何要素はそこまででもない
    • 全ての点を最低1つの多角形に使う時、面積の最小値を求める問題のようだ
    • 2分探索?いや違う。
    • 点の数が15しかないから・・・ それを使うんだろう
      • bitDPかな
    • でも計算量がヤバイ気がする
      • 三角形だけでも 2^15*(15^3) = 90,000,000ぐらい。
      • 四角形以上だと全然間に合わないだろう
  • うーん
    • 待てよ、これ作る多角形は全部三角形と仮定していいんじゃないか?
      • 任意の4点について、四角形の面積と三角形の面積x2 を比べた時、必ず 三角形x2 の面積が小さくなる作り方がある
        • 長方形の場合は特殊で、両者の面積がイコールになる
      • 5点以上についても多分同様なはず・・・
    • 三角形だけなら計算量的に余裕だろう。
  • 実装
    • dfsをゴリゴリ作る。
    • 任意の3点の三角形の面積を前計算しておこう
  • できた。サンプル通った。
    • 最大ケース(ランダム15点)でテスト。
    • OK
  • 提出
    • 直後、三点が一直線上に並ぶ場合を考慮してないことに気づく。
    • 大丈夫な気もするけど、念のため確認したい・・・
    • でも制約見ると、
      • No three points represented by x and y will lie on a common line.
    • と書いてある。よかった

システムテスト

  • WAを食らう。あれ!?
    • 誤差死してるっぽい
  • 三角形の面積の求め方。
    • ヘロンの公式を使ったが、座標が整数で与えられるときはもっと精度がいい方法が存在する!当たり前だね
    • てか |a| <= 1000 でも誤差死してしまうのか・・・
      • これは今後challengeに使えそうなので覚えておこう

続きを読む

SRM 386 EscapeArtist

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

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

  • 余裕を持って1000オープン
  • 方針を検討
    • まず、エージェントが1体だけの単純な場合で考えてみよう
    • エージェントが行く各部屋番号について確率を求めておいて、最短ルートかつ確率が少ない方を選んでいけばいいか
      • 問題はその確率の求め方だ
    • (経路数) / (総経路数) でいいか
      • 最短ルートの総経路数を求め、逆にたどりながら各地点における経路数を求めていく
  • 考える
    • しかし、実際はエージェントが複数あり、しかも廊下で鉢合わせる可能性も考慮しなければならない
    • 廊下で鉢合わせるパターンは廊下もひとつのノードとして処理すればいいか
      • ノード数が結構増えてしまうけど・・・ 無理そうだったら別の方法を考えよう
    • エージェントが複数の時は?
      • 単純に確率の掛け算?
    • いや、実際はORを求めたいんだし・・・
  • 制約を見る
    • エージェント数は高々10ということに気づく。
    • それならば、蟻本に載ってた包除原理というのが使えるはずだ
    • これで大体の不安要素が解消した
  • よし、いける気がする。
  • 実装。ひたすら書く。
    • 実装量が多くて間に合う気がしない・・・
    • 時間切れ。

2012-03-07SRM387 (Practice)

500が正解率4割あるのに解けなかった 193/439位

問題結果ポイントその他
300MarblesRegroupingEasyAccepted233.62貪欲法
500IntervalSubsetsOpened0.00DP?
950StrangeArrayUnopened0.00読んでない

SRM 387 MarblesRegroupingEasy

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

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

  • 方針を検討
    • joker boxを決め打ちして探索
    • joker box以外で2種類以上のmarbleが入っていたらjoker boxに突っ込む
    • marbleが1種類だけならその種類ごとにカウント
    • カウントが2以上なら(カウント - 1)をjoker boxに突っ込む

続きを読む

SRM 387 IntervalSubsets

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

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

  • 方針を検討
    • DPっぽい
    • startとfinishが100以下なのがポイントになりそうだ
    • とりあえず区間の昇順にソートしておく。
  • 状態を考える
    • 今考えている区間と、最後に使った区間とで状態を持つのはどうか
    • 状態遷移は、最後に使った区間(の終わり)に交わらない区間を選択していく。
      • でもこれだけだと複数の区間を飛び越えて選択してしまいそうだ。これをどう処理しよう・・・
  • 発想を変えてみる
    • グラフに落としこんでみる
      • 各区間をノードとして、区間が交わっていればノードをエッジでつなぐ
    • 頂点彩色問題っぽい?
      • 効率的な解き方あったっけ
  • 時間切れ。

その後

  • 他の人のコードを見るといろんな解き方があって面白い。
    • グラフで考えてる人もいる
  • DP解はこれ以上区間を選択できなかったら答えを足し算する
    • 当たり前のようだがその発想には至らなかった・・・

続きを読む

2012-03-06SRM388 (Practice)

SRM389に引き続き簡単回 89/627位

問題結果ポイントその他
250SmoothNumbersAccepted229.09
500InformFriendsAccepted366.11bitDP
1000TelephoneNumbersOpened0.00規則ゲーのような気がする

SRM 388 SmoothNumbers

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

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

  • 方針を検討
    • 最大kまでの素因数が使えるのか
    • k+1以上の素因数を持つ数をエラトステネスの篩みたいな感じで除外していけばよさそう
      • 念のため、予め素数を列挙しておこう
  • 実装
    • 午前中emacsでAOJやってたのでeclipseでのコーディングに戸惑う
  • サンプル通る。
  • 疑心暗鬼フェーズ
    • 自明なケース (k=1) などでテスト
    • 問題分を読みなおす
      • 最大の素因数がkっていうところが妙に引っかかる
      • 本当にこのやり方で合ってるのか?
    • いや、大丈夫なはず。k+1以上の素因数を持つ数が全部除外されてるのだから
  • 提出

続きを読む

SRM 388 InformFriends

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

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

  • グラフゲーきた
  • 方針を検討
    • ふむ。あるノードを選んだ時、それと直接つながっているノードに話が行き渡るのか
    • ノードを複数選んで、全員に話を行き渡らせる。一度使ったノードは使えないとすると、それが最大何回できるか・・ということか
      • なんとなく最大流っぽい
    • 制約を読む。Nが15以下と小さめだ
    • まず、全パターン(2^15)に話をしたとき、全員に行き渡るかどうかチェックしよう
  • 前計算実装
    • んー、これ 2^15 * 15 *15 = 7M もかかる・・・
      • 前計算フェーズでこんなに時間使いたくない
    • とりあえず、(一度全員に話が伝わったパターン) | (なんとか) なパターンを全部trueにしてみる
      • これで多少計算量が落ちてることを祈る
  • さて、パターンは求まった。
    • これ、あとはsubset同士の和の最大を取っていくだけか。
      • いつぞやのKiwiJiceを思い出した。
  • DP実装
    • できた。
  • サンプル通った。
  • 疑心暗鬼フェーズ
    • 念のため最大ケースでテスト。時間は問題なし
    • 自明なケース(友達いない場合など)をテスト。OK
  • 提出

続きを読む

2012-03-03SRM389 (Practice)

149/552位。全体的に簡単な回

問題結果ポイントその他
250ApproximateDivisionAccepted220.45拍子抜け
500GuitarChordsAccepted287.96全探索
1000LittleSquaresOpened0.00Grundy数

SRM 389 ApproximateDivision

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

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

  • 方針を検討
    • 何やら数式が書いてある・・・
    • 読む。b以上の2の乗数tを使い計算せよ、と。
    • やるだけ?
  • 実装
  • サンプル通る。
    • こんなに簡単なわけがない
      • きっと何か罠があるに違いない。
    • しばらく変なケースを探す。
      • 特に見つからない。
  • 出した

続きを読む

SRM 389 GuitarChords

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

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

  • 方針を検討
    • ギターを鳴らす問題
    • 難易度の一番低い引き方をする時、その難易度を求めろ、か
    • よく見ると制約が甘い N <= 6  これは全探索しろということか
  • 実装
    • 予め、音と音に関するフレットのマップを作っておく。
    • next_permutationをして、string を chord にマッピングする
    • その対応を全部調べ、一番難易度が低いのを返す
  • サンプルが全然通らない。
    • 問題に戻る
      • そうか、stringは全部鳴らさなきゃいけないのか。
      • そして鳴らした結果chordのうちのどれかにならなければならない。
      • その上で、chordは最低でも一つのstringによって鳴らされる必要がある。
  • 実装
    • じゃあ、6^6の全パターンを調べてしまおう
    • 書き換え。
  • サンプル3だけが通らない。
    • 詳しく見る。
    • なるほど、あえて1オクターブ高い音にしたほうが簡単な場合もあるのか
      • サンプルが親切。
    • それなら、2^6パターン(高いのを鳴らすかどうか)をすべて調べてしまおう
  • サンプル通った。
    • 特殊な場合でテスト。1音しか鳴らさない場合とか
    • 問題なし。
  • 出した

続きを読む

SRM 389 LittleSquares

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

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

  • 珍しく時間が余った(25分)ので、hardをオープン。
  • 方針を検討
    • ゲームでDPする系か
    • でかいブロックは置ける場所が予め決まっている
    • でかいブロックが置けない場合は、残りのマスの偶奇で勝敗が決まる。
    • 「でかいブロックが後いくつ置けるか」「残りマス数」でdfsできそう・・・
bool dfs(int big, int left) {
  if (big == 0) {
    return (left % 2);
  }
  dfs(big, left-1)
  dfs(big-1, left-4)
}
    • なんとなくこんな(↑)雰囲気で計算できそう
    • 問題は、でかいブロックの置き方によって、残り置けるでかいブロックの数が変わってくるところだ
      • 例えば、
□□□□
□□□□
      • このようなマスでは、でかいブロックはあと2個置けるが
□■■□
□■■□
      • でかいブロックを真ん中に配置するとこれ以上置けなくなる。
    • この状態をどう処理するかがミソな気がする・・・
      • うーん
  • 方針立たずに時間切れ。

その後

  • 解説を読む。
    • どうやら盤面を Nx2 マスずつに区切って、Grundy数というのを求めるといいらしい
    • Grundy数については要学習。蟻本に載ってた気がするので理解を深める。

2012-03-02SRM390 (Practice)

2完ならず。 234/588位

問題結果ポイントその他
250ConcatenateNumberAccepted220.52数論ゲー
500PaintingBoardsOpened0.00DP
1000BuildCircuitUnopened0.00見てない

SRM 390 ConcatenateNumber

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

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

  • わぁい数論ゲー あかり数論ゲー大好き
  • 方針を検討
    • 同じ数を繋げるということは、10^桁数 * (元の数) を足すということだ
      • 愚直にシミュレーションし、0にならず同じ状態にたどり着いたら -1
      • 0になったらその数を返せばいい
    • kは最大でも100,000だから、シミュレーション回数も高々100,000のはず
      • 自信はないが、なんとなくそんな気がする
  • 実装
    • 特に問題なくサクサク
  • サンプル通った。
  • 追加ケーステスト。
  • 大丈夫だろう。提出

続きを読む

SRM 390 PaintingBoards

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

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

  • 方針を検討
    • painterの人数が高々15ってところにbitDP臭がする
    • 次のような区間DPを考えた。
      • dp[a][b][ptn] = 板aから板bまでをptnたちが塗るときの最小時間
      • これだと 50 * 50 * (2^15) >= 26Mで、そもそもメモリ確保できない。却下
    • 前から順番に塗っていくことを考える。
      • dp[a][ptn] = 板aまで塗り、残り使える人がptnのときの最小時間
    • ・・・よさそう。
  • 実装
    • 途中。板と使った人のループ内部で、 (次に使う人 = 15) x (どこまで塗るか = 50) のループが発生することに気づく。
    • 嫌な予感。これ間に合わないんじゃないか・・・?
  • 実装終わり。サンプル通った。
    • 定数倍が効いて間に合うことを祈りつつ、最大ケースでテスト
      • やっぱりTLEした・・・ 500だしそんなに単純じゃないか
  • 更新の仕方を変えてみよう。
    • 蟻本の個数制限ナップザックの話みたいに、余計な更新を減らせばいいのでは
    • 板aに関するループの中では、板a+1についてしか考えない。
    • 最後に使った人をメモしておけば・・・
    • dp[a][b][ptn] = (板aまで塗り終わり、最後に使った人はbで、あとptnが使える時の最小時間)
      • 普通にやるとメモリが足りないので、板に関する部分は使いまわす。
  • 実装
    • あ・・・
      • 同じ人が連続で塗る時、幾つ前から塗っているかを知らないと更新ができない
    • これだとさっきの実装と本質的に変わらず、今度はメモリが足りなくなってしまう
  • 時間切れ。
    • いったいどうやるんだ・・・
    • ヒューリスティクス的な枝刈りが出来るとか?(この時間を超えることはない、というのを予め求めておくとか)
      • コーナーケース用意されて落ちそうだな

その後

  • しばらく自力で考える。
    • ひょっとして二分探索かも
    • mid秒で塗れるかという条件の判定ならばDPの部分で「時間の許す限り塗る」というGreedyな手法が使える
      • これなら探索すべき状態数を大幅に減らせる。
  • 実装
    • 最大ケースでテスト。手元で0.4s、本番サーバで1.0s これはいけるんじゃないか!?
    • TLE食らった・・・まだダメなのか
  • 降参して他の人のコードを読む。
    • maxでmid秒作業できる時、各人がどこまで塗れるか、というのを前計算しておくといいらしい
    • 二分探索までたどり着いておいてそこに気づかないとは・・・
  • 一筋縄ではいかない、いい問題。
  • 続きを読む

2012-03-01SRM391 (Practice)

172/440位 2完最下位

問題結果ポイントその他
250IsomorphicWordsAccepted230.74サンプルに助けられる
500KeysInBoxesAccepted188.65デバッグに時間かかった・・・
1000TransformationUnopened0.00見てない

SRM 391 IsomorphicWords

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

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

  • 方針を検討
    • 各文字列ペアに対して、Isomorphicかどうか確認する
    • 先頭から1文字ずつ比較してmapに突っ込んで、矛盾(既に他の文字にマップ済)しなければOKでよさそう
  • サンプル通らない。なんで・・・
    • 問題文に戻る。
    • 同じ文字にマップしちゃいけないのか、アブナイアブナイ
    • マップ済の文字をメモしておき、2度出現したら false を返すように変更
  • サンプル通った。
    • 自明なケース {a, b}などを確認
    • !?このサンプル文字列長が全部同じじゃないか!?
      • All elements of words will have the same length. あ、そうですか・・・よかった
  • 提出

続きを読む

SRM 391 KeysInBoxes

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

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

  • 方針を検討
    • 答えを分数で返さなきゃいけないのか。むずくね・・・
      • 分子分母で共通する因数を計算中ずっとメモしておくのかな・・・
    • とりあえず分子分母がlongに収まる場合を考えよう
  • 箱と鍵の対応は、グラフで表せるはず
    • 爆破する箱の番号は常に若いものを選ぶとして・・・
<1> -> [2] -> [3]  <4> -> [5] 
   ↑─────┘  ↑──┘
    • 例えば上のようなグラフの場合、爆弾が2個必要だ
    • グラフの形の場合の数を得られるようなDPを考える
      • dp[残りノード数][残り使える爆弾の数]
    • 1個爆弾を使う時、x個連続して箱が開けられた場合、
      • dp[N-x][M-1] * (得られる鍵の選び方 = ncr[N-1][x-1]) * (その鍵の並び順 = (x-1)!)
    • だよね。
    • これらの合計が dp[N][M] の答えになる
    • 実装・・・
  • サンプル通った。
  • さて、問題は N= 20, M = 19などのでかいケース
    • 20! > 10^18 なので、longじゃ収まらないかな・・・(←?)
    • 計算量自体は大したことないし、BigInteger使っちゃおう
      • DPをBigIntegerに置き換え。
  • N = 20, M = 19 でテスト
    • あれ、答えが違う気がする
      • N - M = 1 の場合、答えは (分母) - (分子) = 1 の形になってるはず。だがそうなってない
    • ひたすらデバッグ。
    • ncr[0][0] = 1 とするのを忘れてた
  • 今度こそOK。実行時間も問題ない。提出

続きを読む