Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-02-29SRM392 (Practice)

Arena復活したので久々に練習。

安定して強い人はやはり二完している・・・

234/614位

問題結果ポイントその他
250TwoStringMasksWA0.00場合分けミス。ちくしょー!
500RoundAboutCircleAccepted268.19グラフ上でDP
1000EquiDigitNumbersUnopened0.00読んでない

SRM 392 TwoStringMasks

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

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

コーディングフェーズ

  • 方針を検討
    • なんとなく前後に Z を追加しておく
    • 文字列を * で区切ると、
PPPPssss * SSSS
PPPP * pppSSSS
    • という形になるから、
      • *の前後部分(PPPP, SSSS)のそれぞれprefix と suffixが一致していなければ impossible としていいだろう
    • 問題は残った部分をどうするか・・・
      • 単純に PPPPsssspppSSSS としても正しいが、サンプルにもあるように最短でない場合がある
    • 文字列長は50と短いから、合わせる位置を全探索しちゃえばいいか
  • サンプル通った。
    • いくつかの追加ケースで確認
    • ・・・バグはなく、大丈夫そうだ。
    • 提出

システムテスト

  • 落ちる。なんで!?
    • ケースを見る。
PPPPssss * ppppSSSS
PPPP * SSSS
    • みたいなケースで落ちてた。つまり、ssss と ppppが同じ側にあるケース。
    • そのような場合は合わせることができないので、そのままつなげて返す。

続きを読む

SRM 392 RoundAboutCircle

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

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


コーディングフェーズ

  • 方針を検討
    • ある位置にいる時の行き先は一意だから、まずそれをすべて求めてしまおう
    • 制約が甘い・・・ N <= 200,000
      • おそらく数学ゲーではないんだろう。
    • 訪問済の位置をマークしながらシミュレーションする
      • 訪問済の位置にぶつかるか、ループになったらストップ
      • ループの場合はループのサイズを計算する
    • 方針はこれでよさそう。
    • 実装
  • サンプル通った。
    • N = 200,000 でテスト。 1.2s ・・・
    • ちょっと危ない気もするけど、高速化手法も思いつかないしこれで出しちゃおう。

システムテスト

  • 通った。よかったー
    • 最大ケースは「199997」で、1.95sかかっていた。
    • これは間違いなくお情け解(この解法でも間に合うように微調整してくれたはず)

続きを読む

2012-02-22SRM393 (Practice)

500が簡単なセット。

293/581位

問題結果ポイントその他
250InstantRunoffVotingAccepted206.59やるだけ
500NSegmentDisplayOpened0.00各segmentごとに独立で考える
1000AirlineInternetOpened0.00 -

SRM 393 InstantRunoffVoting

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

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

  • 方針を検討
    • 毎投票ラウンドの結果は
      • 勝者が決まる
      • 少なくとも1人が脱落する
      • 引き分けになる
    • のどれかになるはずだ。
    • 制約甘いしシミュレーションするだけでは。
  • 実装
    • 過半数以上に気をつけて実装
    • サンプル通った。
  • 見直しフェーズ
    • 配列の添字チェック
    • 念のため最大ケースでテスト
  • 提出

続きを読む

SRM 393 NSegmentDisplay

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

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


コーディングフェーズ

  • 英語読めなくて眠くて寝落ち

その後

  • 英語を読む
    • これは各segmentごとに独立で処理できるのでは?
  • 方針を検討
    • patternsの配列で '1' になっている箇所は確実に壊れていない
    • その他の箇所について
      • '動いている' と仮定して問題なければ '?'
      • 問題あれば 'N' にすればよい
  • 実装
    • 特に問題なくサクサク
  • サンプル合わない。
    • pattern[] で distinctだっけ?
      • 特にそのようなことは書いてない
    • ロジックを修正。
  • 提出

続きを読む

2012-02-21SRM394 (Practice)

mediumは幾何ゲー。投げた

253/605位

問題結果ポイントその他
250RoughStringsAccepted170弱ぐらいDP
600 CentersOfSymmetryOpened0.00
1000 PseudoRandomKingdomOpened0.00記念Open

SRM 394 RoughStrings

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

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

  • 文字列から最大n文字を削除した時、roughnessを最小化する
    • ある文字列のroughnessは、文字の最大出現回数 - 文字の最小出現回数 で計算する
  • 方針を検討
    • 貪欲で良さそう
    • たくさん出現する文字を順番に削っていけばいいんじゃない?
    • サンプルを見る。あれ?
      • レアな文字を削ったほうがいい場合もあるのか。
    • うーむ
  • そうだ、DPしよう
    • 貪欲かDPで迷ったら即DP
    • 各文字(26種)の数をカウントし、何文字ずつ削るかで探索しよう
    • 最大と最小をメモしておけばいいよね・・・
      • いやいや、最大を覚えさせておけばそれの最小を取っていけばいいはず
    • 状態数は dp[26][51][51] 余裕ですね
    • 問題の答えは j - dp[26][i][j] を全探索する
  • 実装
    • 元から存在しない文字に気をつけて場合分け
    • できた。
    • サンプル合わない。全部0ってどういうことなの・・・
      • 初期値が間違ってた。
    • 直したらサンプル通った。
  • 見直しフェーズ(5分)
    • あせるな、まだ提出しない。
    • 実装に問題はなさそう。
    • テスト
      • "aaaaa", 10 -> 0
      • "aaaaab", 3 -> 0
      • "aaabbbcd", 2 -> 0
      • "abcdefgg", 1 -> 0
    • ・・・大丈夫かな?
    • 出しちゃえ!
  • resubmit will result in 10% penalty...
    • えーっ、解いたことあったのか
    • 別に既視感はなかったけど・・・ これじゃポイントが分からない
    • 20分位経ってるから170点ぐらいかな・・・

続きを読む

2012-02-20SRM395 (Practice)

正解率30%以上のmediumが解けなかった。

309/420位 過去最低順位・・・

問題結果ポイントその他
250StreetWalkingAccepted156.52慎重にやった
500SkyscrapersOpened0.00解けなかった
1000 PubTriviaUnopened0.00見てない

SRM 395 StreetWalking

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

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

コーディングフェーズ

  • 縦横ナナメに進める。
  • 方針検討
    • 以下の2パターン検証する
      • 斜めにmin(X, Y)進み、その後で直進する
      • 全部直進する
  • サンプル合わない。
    • んー?
    • 斜めにmin(X, Y)進んだ後でも、斜めに進んだほうが得なケースがある
    • 上記3パターンの最小値を返すよう実装。
      • コーディングに手間取る・・・
  • サンプル通った
    • 自分ルールであと5分は提出しない。
    • プログラムを見直す。
      • コーディングのミスを発見。気付いてよかった・・・
  • 出した

続きを読む

SRM 395 Skyscrapers

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

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

コーディングフェーズ

  • あからさまに漂うDP
  • 方針検討
    • 一番高い塔をどこに立てるか決めれば、その左と右にあといくつ建てればいいか決まる
    • その次に高い塔から順番に左か右か、何れかの位置に建ててゆく
    • dp[leftPos][rightPos][leftTower][rightTower] みたいなDPができるはず。
    • O(N^4), N<=100 でメモリ足りなくない?
      • leftPos + rightPos <= 100 だし、 leftTower + rightTower <= 101 だから大丈夫。
      • 最大で 50^4+αぐらいで済むはず
  • 実装
    • 最後、余る塔に関してはどうしようか。
    • 途中すっ飛ばした塔の数は固定だから、(余る塔の数)! で予め計算できる
    • 実装できた。とりあえずメモ化は後回し
  • 残り10分、サンプル合わない。
    • あれ?
    • testCase2が18を返すべきところが9を返している
      • 数え漏らし?
    • プログラムを見直す。
      • 特に間違っているところはない・・・
    • 手で書いてみる
      • あっ
      • 僕の方針だと[2, 4, 5, 1, 3] みたいなケースは作れるが [1, 3, 5, 2, 4] みたいなケースは作れない
    • 絶望
      • そのまま時間切れ。

続きを読む

2012-02-18SRM396 (Practice)

easyが早めに出せたのは良かった

279/547位

問題結果ポイントその他
250DNAStringAccepted232.23全探索
500FixImageTLE0.00方針は正しかったが実装がまずかった
1000 MoreNimOpened0.00斜め読みしただけ

SRM 396 DNAString

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

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

コーディングフェーズ

  • 最大で周期pにするとき、最小で何文字変える必要があるか
  • 方針を検討
    • 周期pで作る時、最初のp文字が決まれば生成すべき文字列は決まる
      • これだと最大で 4^p (p <= 2500)の検証が必要になり、間に合わない
    • 周期pにするとき、{a, a+p, a+2p , ...} (0 <= a <= p-1) で文字の登場回数を数え、一番多いものを採用する
      • 必要な変更回数は ∑(count({a, a+p, a+2p, ...}) - max(登場回数))
    • すべての周期を確かめ、一番小さいものを採用する。
    • 計算量はO(n^4+α) (n <= 50)
  • テスト
    • 通った。念のためランダム文字列2500, p=2500で確かめる
    • 間に合った(1.2s)。ちょっと不安だけどこれで提出

システムテスト

  • 最大ケースで1.9sかかる。あぶない!

続きを読む

SRM 396 FixImage

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

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

コーディングフェーズ

  • 方針を検討
    • 同じグループに属する#に対して、縦or横で # と # に挟まれた部分を塗りつぶしていけばよさそう
  • 実装開始
    • whileループでマスの状態に変化がない間以下を繰り返す
      • 同じグループに属する#を調べ、map[y][x] に保存
        • その際、各グループに対して、同じrow or column で#の出現位置の最大最小を覚えておく
      • 各row or column で、覚えさせておいた最大最小の間を # で塗りつぶす
    • しばらく配列外アクセスなどでハマる
  • テスト
    • サンプル通った。
    • ランダムに 50x50 を配置したケースでテスト
    • 1.4sかかる。不安・・・
      • 改善方法を考える。思い浮かばない
    • まあいいや、とりあえず提出

システムテスト後

  • TLEを食らう
    • そう単純ではなかったか。
    • グループの併合に多くのステップを要するケースでTLEしている模様
    • 何か効率的な方法がある?グループをunion-findかなんかで管理して探索コスト(ループ回数)を減らすのか?
  • Javaで書かれた他の人のコードを見る
    • 基本的な方針は正しいっぽい
    • そういえば塗りつぶす操作を全グループの処理が終わった後にしてるけど内側にしても挙動は変わらんよね。あわよくばループ回数減らせるかも
      • あ、それっぽい
      • メモリの節約にもなるし・・・
    • 修正したら通った
      • 最大ケースで0.2s。劇的に変わるもんだなー
      • 続きを読む

2012-02-17SRM397 (Practice)

ぐぬぬ・・・

205/560位

問題結果ポイントその他
250SortingGameAccepted200.66全探索
500SumOfPowersOpened0.00数学ゲー?漸化式に落としこむ?
1000 HouseProtectionUnopened0.00見てない

SRM 397 SortingGame

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

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


コーディングフェーズ

  • 連続する k 個の数字を選び、ひっくり返す
    • {1, 2, ..., n} にする最小手数を求めよ
  • 1から順番に固定する?
    • うーん最適かどうか怪しい気がする。でも合ってるような気もする
  • 神にすがる思いで制約を見る
    • n <= 8 !! これなら全探索できる!
  • 幅優先探索する
    • 状態は数列で、高々 8! <= 40,320
    • ある状態から可能な操作をしたあとの数列を全部キューに突っ込む
    • 一度見た状態はメモしておいてパスする
    • ループを抜けた時、メモに目的の数列が入ってればそのターン数、無ければ-1
  • できた。
    • サンプル通った。
    • 念のため制約を確認
      • k>=2 だし大丈夫
    • 最大ケースを確認
      • ({8,7,6,5,4,3,2,1}, 2)で0.2s。OK
    • forの条件を1つ緩くして配列外アクセスエラーが出るか確かめる
      • ちゃんとエラーになってくれた。OK
  • おそらく大丈夫でしょう。提出

続きを読む

SRM 398 SumOfPowers

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

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


コーディングフェーズ

  • うわー、数学ゲーだ
    • f(n,k) = 1^k + 2^k + ... + n^k とおく
  • 式をこねくり回してみる・・・
    • f(n,k+1) = n * f(n,k) + f(n-1,k+1) - n * f(n-1, k) を得た
      • うーん、kが一方的に減っていかないと嬉しくない・・・
  • 気を取り直してとりあえず常套手段、f(n,k) を紙に書き出してみる

n\k1234567
11111111
2359173365129
361436982767942316
4103010035413004890・・・
  • うーむ、全然見えてこない
  • 詰んだ
    • MODの性質を利用するのかな?全然分からん
  • 時間切れ。

その後

  • editorialを読む。
  • 言われてみれば自然な発想だ・・・
    • 行列の形に持ち込めば累乗はlognで計算できるもんね

続きを読む

2012-02-16SRM398 (Practice)

2問早解きセット。

問題結果ポイントその他
250CountExpressionsAccepted160.83問題を難しく勘違いする
500CountPathsAccepted214.89方針ミスで時間を食う
1000 MyFriendsUnopened0.00見てない

SRM 398 CountExpressions

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

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


コーディングフェーズ

  • (サンプルを斜め読みして)げ、めんどくさい系だ
    • 掛け算は先に計算しなきゃいけないし・・・(←間違い)
  • 数字とオペランドの配列を与えると計算結果を返す関数をつくろう
    • 掛け算はどう処理しよう?
      • スタックに積んでいって、掛け算が来たらスタックから一個取り出して掛け算して積もう
    • で、最後にスタックの残りを全部足す。と
    • マイナスが来たらどうする?
      • * -1 してスタックに積もう。-aの足し算をしたことと同じになる
  • 数字の列は4つだから、next_permutationしよう
    • ライブラリを貼り付ける
    • 同じ数列が生成されるから、List<Integer>をマップに突っ込んで既に処理したかどうか調べよう
  • できた。
    • サンプル1が合わない・・・
    • 5 - 3 * 5 - 3 ←このケースが生成されていない。でもこれって 7 じゃなくて -13 じゃん。
      • 何か見落としがあるのか・・・?(ここではじめて問題を斜め読みする)
  • 前から先に計算すればいいだけだった・・・
    • 泣く泣くロジックを修正。提出

続きを読む

SRM 398 CountPaths

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

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


コーディングフェーズ

  • さて、あまり時間がないぞ。
  • あるspecial field(以下SF)からあるSFまで行く時、何個SFを通過するか、というDPでどうだろうか
    • つまり dp[from][to][count] を再帰かなんかで計算する
    • スタート地点とゴール地点もSF扱いにしてしまえば後々都合がよさそうだ
    • 更新式を考える
      • dp[x][x+1][1] は (dx+dy)C(dx) を計算すればよさそう
        • nCrを前計算するコードを書く
      • 複数またがる場合(dp[x][x+n][k])は?うまく思い浮かばない。
      • そもそもこれだとspecial fieldを通過しない場合を考慮できない
  • もっとシンプルに考えられないか。
    • 普通に現在地(x,y)に対して通過したSFの数と最後に通過したSFなら
      • dp[count][last used][x][y]
      • 50^4 = 6,250,000 いける!更新も縦と横の一歩分でいい
    • よさげな方針が立った。この時点で残り10分
    • まてよ、移動先(x+1, y) or (x, y+1) がどのSFと一致するか検索しなきゃいけないのか
      • あらかじめ (x, y)が何番目(1-indexed)のSFかを記録するmapを作ることで対処
    • 答えは、各k (0〜n)に対して dp[k][i][c][r] (i=0〜n) の足し算を計算する
  • できた。
    • サンプル3だけ合わない・・・
    • 最後足す時MODを忘れてた・・・修正し提出

続きを読む

2012-02-15SRM399 (Practice)

練習。


問題結果ポイントその他
250AvoidingProductWA0.00いくらなんでもこれは通さなきゃダメだろ!
500BinarySumAccepted211.27方針が二転三転するうちにDP(探索)を思いつく
1000DancingPartyUnopened0.00見てない

SRM 399 AvoidingProduct

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

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


コーディングフェーズ

  • とりあえず {x, y, z} = {1〜n+1} での全探索を実装(←ここでもう間違ってる)
    • zのループに入る前に x * y が (n + 差の絶対値) を超えてたら探索しない(continue)という謎枝刈りをする
    • 配列aがたくさん埋まってたら間に合わないかもという考えつつも気にせず提出

  • 500を提出し250に戻ってくる
    • ちょっと気になったので配列aを1〜50で全埋めした場合をテスト
      • ローカルで1.7s。これはTLEする!
    • よく考えると枝刈りのとこcontinueじゃなくてbreakでいいよね なにやってんだ
    • 再提出

システムテスト後

  • あっさり落ちる。なんで!?
    • {1〜n+1}ではなく、最大の{1〜1001}で回すべき。それでも間に合うんだから
      • 念のため{1〜1501}で再実装。通した

続きを読む

SRM 399 BinarySum

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

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

コーディングフェーズ

  • はじめは数学的に解こうとした
    • 1のビットをどう動かせば最小になるかを考えるなどした
    • 難しい・・・
  • 30分後、ふと探索という考えが頭をよぎった
    • これ[桁][Aで使った1の数][Bで使った1の数][足した結果の1の数][繰上げフラグ] のDPでいけるじゃん
    • 実装

続きを読む