hotpepsiの練習帳

SRM 525 Div2

02:35

Easy (250) RainyRoad

問題

• 道路に水溜りがある
• 迂回してゴールできるかどうかを答える

方針

• 同じカラム(上と下の両方)が埋まっているかどうかだけ調べる
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_525/RainyRoad.cpp

Medium (600) DropCoins

問題

• 升目にコインが乗っている
• 盤全体を上下左右いずれかに動かすことにより、乗っているコインを落とせる
• 残ったコインをK枚にするための最小の手数を答える

方針

• 最初に、上と左右または下と左右を削るものを書いたら通らず。
• 考え直したら、削るのではなく、任意の大きさの長方形で評価すればよいという結論に。
• 効率的なのが思いつかなかったので軽い気持ちで6重ループする全探索。
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_525/DropCoins.cpp

Hard (950) MagicalSquare

問題

• 3x3の升目に文字列を記入する。
• 横方向に連結した文字列をrowStrings、縦方向に連結した文字列をcolumnStringsとして
• それらを満たす文字列の組み合わせが何通りなのかを求める。

方針

• capythmさんのを写経
• 全探索
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_525/MagicalSquare.cpp

結果

oo- 243.14+261.63=504.77 rating 1190 -> 1227

easyは、こんな単純で良いのかとは思ったが、反例が思いつかなかったのでsubmit。通った。

mediumは、いったん下に動かしてから上に行くというパターンがサンプルにあり、それが通らないコードを書いていたため、書き直し。結局50分近くかかった。なのであまり見直しせずsubmit。TLEしなかったため通った。

ようやくdiv1に上がった。easyしか解けそうにないがぼちぼちやっていくつもり。

SRM 524 Div2

20:47

Easy (250) ShippingCubes

問題

• N個の立方体をa x b x cの形で隙間なく詰めたい。
• a+b+cの最小値を求める。

方針

• 素因数分解して組み合わせ、と思ったが
• Nが小さいので全探索に切り替え
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_524/ShippingCubes.cpp

Medium (500) MagicDiamonds

問題

• 距離nだけ移動したい
• 素数の移動は不可

方針

• 合成数なら1、素数なら2 (素数の場合、偶数と1の2回に分割できる)
• ただし3の場合は3 つまりn<=3ならnを返せばよい
• 偶数をはじいてから、3から√nまでの奇数で割ってみて素数判定
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_524/MagicDiamonds.cpp

Hard (1000) MultiplesWithLimit

問題

• 0から9のうち、0から9個だけ禁止されている
• 禁止文字を使わずに、与えられたnの倍数の最小値を求める

方針

• 本番で解けず、解きなおし
• 下の桁からBFS
• 1度処理した余りは、2度目は無視してよい
• ただし、見つかったものが最小値か不明なので、解が見つかったら、キューへの追加をやめて、残りのキュー(同じ桁数のキュー)を全て処理する。
• ためしにpriority_queueを使ってみたが遅くて断念
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_524/MultiplesWithLimit.cpp

結果

oo- 224.71+439.48-25.0=639.19 rating 1179 -> 1190

easyは途中で方針を変えた割にはそこそこの時間で書けた。

これは郵便物の送料を最小化する問題ということだろうか。球に近づければ良いのだと思われる。

mediumは前回範囲の判定が甘かったので、今回は1～5くらいまで個別に代入してじっくり見た。

除算での判定もそれなりに速いのはSRM 508のときに調べていたので同じように書いた。一応、submitしてから最大値より少しだけ大きい素数1000000000039でも一瞬で終わることは確かめておいた。ループ判定で乗算しているが、乗算命令は速いのでここが定数でもあまり速度は変わらない。

hardはださい全探索を書いてみたが全く終わらないので諦めた。AnalysisによるとDFAとのこと。

challengeはmediumの3のケースだろうな、と思っていたが開始5秒とかで最初の一人が落とされたのはまいった。√n未満までしか判定してないケースが後まで残っていて気づかなかったのは反省。

SRM 523 Div2

03:36

Easy (250) AlphabetPath

問題

• AからZまでが1文字ずつ書かれた迷路がある。
• AからZまでたどれるかどうかを求める。

方針

• 処理時間は十分あるので、ループで回すことにした
• 次の文字の位置を(x',y')として、|x-x'|+|y-y'|が1かどうか見る
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_523/AlphabetPath.cpp

Medium (500) CountingSeries

問題

• 1以上の数a,b,c,d,upperBoundが与えられる。
• 1からupperBoundまでの間でa+b*xとc*d^yのいずれかを満たす数の個数を求める。

方針

• a+b*xの方の数を求めておく
• c*d^yの方は、1回ずつかけて、a+b*xを満たすか調べる
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_523/CountingSeries.cpp

Hard (1000) SmallBricks31

問題

• 1x1x1、1x1x2、1x1x3の3種類のブロックがある。
• ブロックの上には1x1x1のブロックを積むことができる。
• 連続する2ブロックの上には1x1x2のブロックを積むことができる。
• 連続する3ブロック、または、1個あけた2ブロックの上には1x1x3のブロックを積むことができる。
• 幅と高さが与えられる。ブロックの積み方が何通りあるかをmod 1000000007で求める。

方針

• 素晴らしい問題。書けず。
• LayCurseさんのコードでやっと理解。
• 1段上になったときに、どのパターンがいくつになるか、というのをテーブルで持つ
• 一つもおかないやつも1通りと数える
• 置かない場合、それぞれのブロックを置いた場合でテーブルを生成
• H回ループでまわす

結果

ox- 239.30+50 rating 1146 -> 1179

a>upperBoundを考慮しなかったため死亡。甘い。

その後、他の人のを見て気づいてchallenge成功。

SRM 522 Div2

01:21

Easy (250) PointErasingTwo

問題

• y座標の配列が与えられる。
• 2点間を選んだとき、その内部に含まれる最大の個数を求める。

方針

• 範囲をミスらないようにする。
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_522/PointErasingTwo.cpp

Medium (550) RowAndManyCoins

問題

• AliceとBobが交互にコインを置く。
• コインは1つ以上の連続するマスに置ける。
• 全ての場所を埋める置き方はできない。
• 残りのマスが1つになったとき、マスに書いてある文字で勝者が決まる。
• 最適戦略で勝つほうを答える。

方針

• 終了条件を覚えておいて、メモ化再帰
• 両端のどちらかがAのときAlice、その他はBobらしい
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_522/RowAndManyCoins.cpp

Hard (900) CorrectMultiplicationTwo

問題

• a * b = cという形の式があるが、正しくない。
• 値を加算または減算してA * B = Cに値を変更する。
• |A - a| + |B - b| + |C - c|の最小値を求める。

方針

• 範囲をaとbの前後で動かしていったらsystem test failed
• 単純な全探索で、積が巨大なとき打ち切りにすればよかった
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_522/CorrectMultiplicationTwo.cpp

結果

oox 239.43+328.24=567.67 rating 1194 -> 1146

ぼちぼち青くなれるかなーと思ったが甘かった。

ここ5回はmediumまで通っているのでまあ解けるようにはなってきたかと思う。

SRM 521 Div2

22:38

やっと復習が追いついた。

Easy (250) RedAndGreen

問題

• RとGのどちらかで塗られたパネルが1列に並んでいる。
• RをGに、または、GをRに塗る操作により、Gの右側にRがない状態にしたい。
• RをGに、またはGをRにする操作の最小回数を求める。

方針

• R->GとG->Rのどちらが最適かわからない
• ちょっと考えてわからなかったので、メモ化再帰した
• 最終的な配置をR=0個からR=N個まで仮定して、ループでまわせばよかった
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_521/RedAndGreen.cpp

Medium (500) MissingParentheses

問題

• 開き括弧 ( か 閉じ括弧 ) のいずれかからなる文字列がある。
• 括弧が正しく閉じていない個数を求める。

方針

• 左から一個ずつ見ていく
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_521/MissingParentheses.cpp

Hard (1000) SquaredSubsets

問題

• XY平面上に点集合Pがある。
• 整数nが与えられる。
• 大きさnの正方形に収まるPの空でない部分集合がいくつあるかを答える。
• 正方形を動かしてみて、Pの含まれ方が何通りあるかということらしい。

方針

• 本番中には問題文の意味がつかめなかった
• 正方形を点の座標の右下、左上、右上、左下それぞれに、含む場合と含まない場合とで配置してみる
• 整数でループして回すだけだとサンプルが通らない
• 点の中間に配置するパターンがあるので、座標とnを2倍しておく
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_521/SquaredSubsets.cpp

結果

oo- 167.36+474.46=641.82 rating 1169 -> 1194

easyに20分もかかったが、まあ通ったのでよしとする。チャレンジケースを作るまでには至らなかった。システムテストでeasyは部屋内で半分以下しか通っておらず、全体の順位も200位以上あがった。ひっかかりやすい問題だったっぽい。

mediumは、ひっかけがあるんだろうなあと思いながら素朴なコードを書いたがそのまま通った。

hardはAnalysisを参考にしつつも、理解できてないので、単純なループで書いた。なかなか通らず、0.5の意味がやっとわかった。