Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2011-09-25KISSの原則 その3

KISSの原則 その3

| 22:27 | KISSの原則 その3 - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - KISSの原則 その3 - SRM diary(Sigmar) KISSの原則 その3 - SRM diary(Sigmar) のブックマークコメント

の続き。考え方をシンプルにすることで楽に解くための考察。


少し趣向を変えますがコーディング時間を短くする工夫について。


SRM421 Div2 1000 FloorIndicator

Problem Statement

1階から10^N-1階までの階があるビルがある。エレベータ内の階の表示は丁度N桁の数で表される。(0で始まる表示でも良い)

各数字は5×3のランプで表示される。0~9の表示を以下に示す。(#が点灯)

###...#.###.###.#.#.###.###.###.###.###
#.#...#...#...#.#.#.#...#.....#.#.#.#.#
#.#...#.###.###.###.###.###...#.###.###
#.#...#.#.....#...#...#.#.#...#.#.#...#
###...#.###.###...#.###.###...#.###.###

数字の境界は1列の消灯ランプで表される。

なお、いくつかのランプが壊れており、常に消灯されている。(どれが壊れているか分からない)

あるランプ表示のパターンが与えられるので、可能性のある全ての階の平均を取ったものがいくつになるか答えよ。

可能な階が一つもない場合は-1を返せ。

double averageFloor(int N, vector <string> indicator);

1<=N<=9

indicator.size()=5

indicatorの要素は4*N-1文字

indicatorの要素は'#'と'.'のみで構成される

indicatorの中で各数字の区切り線となるはずの列の要素は全て'.'


indicatorの例は以下のようなの。

{"###.###",
 "#.#.#.#",
 "#.#.###",
 "#.#...#",
 "###.###"}

この場合、1文字目は0もしくは8、2文字目は9もしくは8となる。

解は09,08,89,88の平均を取って48.5


以下、僕の考える解答例です。

続きを読む

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110925

2011-09-20SRM519 Div1

  • 250:222.67, 600:Opened, score:222.67, rank:169, rating:2084(-15)
  • 単純化だ・・・単純化・・・

SRM519 Div1 250 BinaryCards

| 00:43 | SRM519 Div1 250 BinaryCards - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM519 Div1 250 BinaryCards - SRM diary(Sigmar) SRM519 Div1 250 BinaryCards - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

AとBをビット単位で上の桁から見ていき、最初にAとBのビットが異なるところより下位のビットを全て1にすれば良さそう

何となくビットをvectorに落としたらコードが汚くなった。。。

普通にビット演算すれば良かった


ソースコード

続きを読む

SRM519 Div1 600 RequiredSubstrings

| 00:43 | SRM519 Div1 600 RequiredSubstrings - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM519 Div1 600 RequiredSubstrings - SRM diary(Sigmar) SRM519 Div1 600 RequiredSubstrings - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

DPぽい

n文字目まで進んだところで、ビットマスクでwordsの要素のうち登場したものを覚えておけば良さそう

しかしその時点で未登場のwordsのprefixが末尾に出てきている場合はそれを状態として持たなければならない・・・

当然26文字^50乗では爆発する。各wordsのprefix文字数で何文字目まで一致するか覚えると50文字^6乗でやはり無理。

・・・

・・・

よく考えると各wordsの一致prefix文字数を覚える必要はない。最長の一致prefix文字数を持つwordsだけ覚えておけば、後は自動的に決まる。

しかしこれはコーディングが・・・きつそう・・・

他に思いつかないのでとりあえず書いてみる。やっぱり時間内に書ける内容ではなかった。

もっと単純に書けるように思考の転換が必要です。


ソースコード

とりあえず上記方針でpractice通ったもの

prefixが一致しなくなった時点で何文字目まで一致するか調べるためkmp法とか導入していてややこしいです

続きを読む

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110920

2011-09-14SRM518 Div1

  • 250:229.92, 500:212.60, score:442.52, rank:417, rating:2099(-86)
  • リーチかかると失敗するといういつものパターン
  • とはいえ500は本来もっと難しい問題であると思うので、正しいと思える解法に行き着いたことには満足している

SRM518 Div1 250 LargestSubsequence

| 01:22 | SRM518 Div1 250 LargestSubsequence - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM518 Div1 250 LargestSubsequence - SRM diary(Sigmar) SRM518 Div1 250 LargestSubsequence - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

やるだけ

のはずがないと思って余計なことを考えすぎて遅くなった

ダメダメ。。


ソースコード

続きを読む

SRM518 Div1 500 ConvexSequence

| 01:22 | SRM518 Div1 500 ConvexSequence - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM518 Div1 500 ConvexSequence - SRM diary(Sigmar) SRM518 Div1 500 ConvexSequence - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

全然分からん

・・・とりあえずconvex sequenceというのは最小値を中心として、そこから離れるにつれて値が大きくなるようだ

そしてその傾きは前と同じか大きくないといけない

・・・

・・・

最小値から左右に向かって、Greedyに傾きを増やしていけば良いのでは?

これは2分探索で最大の傾きを判定可能なので、できそう

あとは最小値は入力配列の最小値でいいのかというところだが・・・

入力配列の最小値をマイナスしても何もいいことがないので問題なさそう

計算量も問題ない

書いた

通った

提出


チャレンジで部屋内のコード見たらほとんどがナイーブなGreedy解法。何じゃこりゃ。

これは絶対TLEWAだな。と思ったら普通に皆通っていた。writer想定外解法だったようで・・

自分もそんな方法でいけるとは全く思いもしませんでしたが。


ソースコード

続きを読む

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110914

2011-09-11SRM517 Div1

  • 250:224.27(+50), 600:Opened, score:274.27, rank:99, rating:2185(+35)
  • 600がいつ以来だっていうくらいに方針が立たなかった。ダメすぎる。
  • また寸止め。実はcodeforcesも結構寸止め状態。こうなったら次は2199でも目指すか。。。

SRM517 Div1 250 CompositeSmash

| 17:24 | SRM517 Div1 250 CompositeSmash - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM517 Div1 250 CompositeSmash - SRM diary(Sigmar) SRM517 Div1 250 CompositeSmash - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

サンプルを見て、N%target==0かつtargetが素数か、N==targetか、Nを1回smashしたら必ずtargetが出ればYesかなと想像したがつい最近KISSの原則なる記事を書いたことを思い出しメモ化で全探索することにした。

書いた。サンプル合った。提出。

サンプルにないパターンでコーナーケースを探してみる。

適当に32,4とかやってみたらYesだった。確かに手計算してみてもYesになる・・・

ということでチャレンジで50点ゲットした。ラッキー。


ソースコード

続きを読む

SRM517 Div1 600 AdjacentSwaps

| 17:24 | SRM517 Div1 600 AdjacentSwaps - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM517 Div1 600 AdjacentSwaps - SRM diary(Sigmar) SRM517 Div1 600 AdjacentSwaps - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

とりあえず逆順に考えたほうが楽なので逆順に考える。つまりpをソートすると考える。

色々考えていると法則性がありすぎてどれを使えばいいか分からなくなった

  • 解が0でない条件は、permutationが2グループに分けられないこと({1,0,3,2}は×、{3,0,1,2}は○)
  • ある時点でswapができる条件は、左の要素が本来の位置より左にあり、右の要素が本来の位置より右にあること
  • ある時点でswapができる条件は、左の要素が右の要素より大きいこと(恐らく上の条件と同じ意味)
  • 各要素は本来の位置へ向かう方向にのみ動き、逆方向に動くことはない(戻れないから)
  • ある時点でswapができる要素は同時に複数存在しうる

何となくDAGっぽくなりそうなのでDAGにしようとしてみたらえらいことになった

結局何か違うなと思いつつタイムオーバー・・・


後で

考えてみれば2番目の法則を使ってメモ化再帰が可能だった

pのある範囲[b,e)の解を再帰的に計算する

pをswap可能なindexで分割し、両側を再帰計算した結果を掛けあわせ、さらに両側の残りswap数を使ってコンビネーションを取る

これだけだった・・・

何か解けそうで解けない方針が色々出てくる問題なので上の解法も思いつくかどうかが全てな気がする。。。

(普通の500だともっとWrong Attemptを枝刈りしやすいイメージ)


ソースコード

続きを読む

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110911

2011-09-02KISSの原則 その2

KISSの原則 その2

| 17:45 | KISSの原則 その2 - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - KISSの原則 その2 - SRM diary(Sigmar) KISSの原則 その2 - SRM diary(Sigmar) のブックマークコメント

の続き。考え方をシンプルにすることで楽に解くための考察。


突然ですが、以下のような問題について、どう解くべきでしょうか?


SRM481 Div1 250 ChickenOracle

Problem Statement

卵が先か、鶏が先か?どちらが先に存在したのか、神様に聞くことにした。

ところが神様はこれまでn人に対してその回答をしたので、答えを教えてくれない。

しかも、n人のうちlieCount人に対しては嘘の回答をしたとのこと。

そのn人に尋ねたところ、eggCount人は卵が先だと言い、n-eggCount人は鶏が先だと言う。

しかし、n人のうちliarCount人は嘘を付いているらしい。

以上の状況で、真実が導き出せるだろうか?

この問題を解く以下の関数を書くこと。

string theTruth(int n, int eggCount, int lieCount, int liarCount);

真実が導き出せて、卵が先なら"The egg"、鶏が先なら"The chicken"を返せ。

両方の解があり得るなら、"Ambiguous"、両方あり得ないなら、"The oracle is a lie"を返せ。

制約条件は以下の通り。

1<=n<=1000000

0<=eggCount, lieCount, liarCount<=n


以下、僕の考える解答例です。

続きを読む

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110902