2013-10-17
SRM 588
Div1 Easy (250) GUMIAndSongsDiv1
問題
- 音程と長さからなる歌がいくつか与えられる
- 連続して歌うとき、音程の差＋曲の長さの時間がかかる
- 時間Tで歌える最大の曲数を求める
方針
- 音程でソートしてDP
- コンテスト中は音程の差の扱いに迷って提出できず
- dp[最後に歌った曲のindex][曲数]=長さ
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_588/GUMIAndSongsDiv1.cpp
結果
- 0pt 451st/696 rating 1205 -> 1183
典型問題なのだがパラメータが二つ出てくると弱い。
コメントを書く
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20131017
2013-10-16
SRM 587
Div1 Easy (250) JumpFurther
問題
- 階段の最下段にいる
- 全部でn回ジャンプできる
- i回目のジャンプの距離はiである
- 特定の段が壊れていて、そこには着地できない
- 到達できる最高位置を求める
方針
- iずつ足していく
- 壊れている段に遭遇しなければそのまま
- 壊れている場合は最初の1段をジャンプしないことにする
- Passed System Test
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_587/JumpFurther.cpp
Div1 Medium (550) TriangleXor
問題
- 高さ1、幅Wの長方形に三角形をXORで塗っていく
- 面積の整数部分を求める
方針
- kojingharangさんのを読む
- 大きいほうから三角形を塗っていく
- 最初のW+1個のは1回分だけ足す
- 次のW個の高さは1.0-(1/(W+1))で、ゼロにするために2倍の面積を引く
- k番目の高さは1.0-(k/(W+k))で、符号を反転していく
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_587/TriangleXor.cpp
結果
o-- +1 142.14pt 443rd/491 rating 1280 -> 1205
easyは、最終段のときはジャンプできないだけで到達できると読んでしまい、再提出。
落ち着けば最後に-1すればいいだけだが、2回計算してしまった。
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20131016
2013-09-08
CodeIQ 最適解を目指せ！！
tomerunさんのマラソンに挑戦。
1回目
- サンプルを見る
- 乱数で埋めるbenchmark1.cppが774点、1-9のうち重複の少ないものを選ぶbenchmark2.cppが11541点。まずはこれを超えるのを目標にする
- 数独を解くプログラムとかをチラ見するが、3x3の制約が違うので使えないかもと思う
- 評価関数をちょっと速くしたりとか、無駄な時間を過ごす。
- 完全ランダムよりbenchmark2のほうが素性が良さそうなのでベースにする
- 範囲を限定してランダムに置換し、評価値がよくなったら更新してみる
- 20000点くらいになりやっとサンプルを超えたのでひとまず提出
- 8/7の中間発表で圧倒的最下位
2回目
- とりあえず10万点は超えるのを目標にする
- 良いパターンで埋める→ランダムで小改善、は基本とする
- discrete_distributionとかは使いこなせなかったので、普通のrand()に戻す
- 縦ラインのみとかより、以下のようなブロック単位で埋めるほうが良さそう。横と縦の点数が稼げる
123456789
456789123
789123456
234567891
567891234
891234567
345678912
678912345
912345678 - ブロックの大きさ(3x3や6x6)、開始位置(456からはじめたり)などをいくつか試す
- ランダムに範囲を選び、新しいパターンで置き換えて、前後の場所を含めてスコアが良くなるのであれば確定、を10万回くらいループ
- 10万点くらいになる
- 縦と横と3x3のスコアを見ると、3x3がかなり低いので、改善を試みる
- 2行目は456/789/234で0点なので、以下のようなブロックにしてみる
123456789
456789123
789123456
231564897
564897231
897231564
312645978
645978312
978312645 - あとランダム置換
- 16万点くらいいったので提出
- 8/22の中間発表で16位、まあまあ
3回目
- 気がつくと締め切り前日
- せっかくなので20万点の壁を超えるのを目標にする
- ブロックの位置をランダムにしてしまうと、ブロックの境界でスコアが伸びないのでいまいち
- なので全体は単一の割と良さそうなパターンでまず埋めて、小改善を試みる
- 固定値になっているためにスコアが失われているところを代替したら改善しそう
- 数値Aを書きたかったが、固定されていて数値Bになっているところを覚えておく
- 固定されていなくて数値Bを書いたところに数値Aを書いてみる
- 横の場合の例として、元データが200000000で223456789と埋めたときは、213456789にするという感じ
- 横、縦、3x3それぞれで、スコアが良くなったら決定する、を32x32の範囲で30ずつスライドさせて全範囲で行う(これで18万点くらい)
- ただし全体の評価値を上げるために、評価は50x50で行う
- それが終わったらランダムに数値を置き換えて良くなったら置換
- パターンを2通り+開始位置をずらすのも試す(2000点くらいしか効果はない)
- 20万点超えた!
- 提出(AM 3:45)
- ちょっと書き直した
- https://github.com/firewood/topcoder/blob/master/codeiq/tomerun.cpp
結果
203711点で14位。
提出の締め切り前後でしかやっていないのが反省点。プログラムより自分のスケジューリングに課題がある。
最初のわからなさ加減からすると相当楽しめた。
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20130908
2013-08-19
SRM 586
Div2 Easy (250) TeamsSelection
問題
- メンバーを2チームにふりわける
- それぞれのキャプテンがメンバーの番号の優先順位を持っている
- 1人ずつ割り当てたときのチーム割りを求める
方針
- 貪欲に割り当て
- Passed System Test
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_586/TeamsSelection.cpp
Div2 Medium (500) PiecewiseLinearFunctionDiv2
問題
- 直線からなる関数が与えられる
- 座標に対する解の個数を求める
方針
- 連続して同じ座標のものは無限に解があるので覚えておく
- 座標が等しいものだけカウントして、開区間だけカウントする
- Passed System Test
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_586/PiecewiseLinearFunctionDiv2.cpp
Div2 Hard (1000) StringWeightDiv2
問題
- 26文字のどれかからなる文字列Sがある
- ある文字についてのスコアは、最も右のものと最も左のものの出現位置の差の絶対値である
- 文字列Sのスコアは、文字のスコアの合計である
- 文字列Sの長さLが与えられる
- その長さにおいて最小のスコアの文字列が何通りあるかを求める
方針
- 異なる文字を使ったほうがスコアが小さい
- それぞれの文字は連続していること
- 長さが26以下のときは、1文字ずつ使う場合が最小
- 長さ1のとき26通り、長さ2のとき26×25通り...長さLのとき26_P_L = (26!)÷((26-L)!)
- 長さが27以上のとき、26種類全て使う
- 26を超えたぶんをどこかに分配する
- 26箇所に0個以上分配する重複組み合わせ
- 26_H_(L-26) = (26+L-26-1)_C_(26-1) = (L-1)_C_25
- それぞれの文字種の並べ方は26!
- つまり26!×(L-1)_C_25
- Passed System Test
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_586/StringWeightDiv2.cpp
結果
ooo 196.67 + 421.80 + 568.00 = 1186.47pt 23rd/1005 rating 1191 -> 1280 (+89)
easyの優先度の見方が間違っていて時間がかかった。
hardも通って良かった。最高順位。
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20130819
2013-08-11
Codeforces Round #192
Div1 A. Purification
問題
- グリッド状の床がある
- 座標を指定すると、列と行が掃除される
- 呪われている座標は指定できない
- 全て掃除するのに必要な最小の手を求める
方針
- 全ての行または全ての列のどちらかが必要
- 両方とも満たせない場合は無理
- ある行全てが埋まっているかどうかを調べる
- ある列全てが埋まっているかどうかを調べる
- 埋まってない方で手を作る
- Passed System Test
Div1 B. Biridian Forest
問題
- 君は○ケモンマスターだ
- 現在地とゴール地点が与えられる
- グリッドで表される地図上に君と他のトレーナーがいる
- 全員1ターンに一歩ずつ進む
- 君と出会うと戦闘が生じる
- ゴール地点までの戦闘回数の最小値を求める
方針
- 通り方によって結果が変わるかどうか考えてみた
- ゴール地点への距離が自分と同じか短いトレーナーとは必ず戦闘になるので、遠回りするメリットはない
- それぞれのトレーナーのゴールまでの距離がわかればよい
- ゴールからの距離をBFSで求めればOK
- Passed System Test
結果
oo--- 462 + 682(+1) = 1144pt 294th/528 rating 1755 -> 1771 (+16)
距離の初期値を0にしていたため、ゴールに到達できないトレーナーの処理が間違っていて+1。
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20130811