hotpepsiの練習帳

SRM 554

07:36

Div1 Easy (250) TheBrickTowerEasyDivOne

問題

• 二種類のブロックを交互に積む。
• 各ブロックの高さと個数が与えられる。
• 何通りの高さが作れるか求める。

方針

• 個数の少ない方の種類をA、多いほうをB、個数をaとbとする
• ABとBAで積んだときは同じ高さ
• ABAとBABは、AとBの高さが異なる場合には異なる
• 使用する個数は最大でa*2+1個
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_554/TheBrickTowerEasyDivOne.cpp

Div1 Medium (500) TheBrickTowerMediumDivOne

問題

• 0からN-1までのN本の塔があり、高さはばらばらである。
• 塔と塔の間を、それらの高いほうだけ離して一直線上に並べる。
• 全体の距離が最小で、塔の番号が辞書順最小の並べ方を求める。

方針

• ソートして並べるとだいたい最小解になる
• 単純に並べると、辞書順最小にならない
• 何か違うけど、とりあえずswapしてみるか
• Challenge Succeeded
• (終了後)
• どれを先頭にしても最小解は作れるっぽい
• つまり先頭はindex 0に固定してよい
• 置ける中で最小のものを貪欲に置いていけばよいらしい
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_554/TheBrickTowerMediumDivOne.cpp

結果

ox- +1 198.86+0+50.0=248.86 302nd rating 1344 -> 1421 (+77)

easyは、考え方は合っていたのだが、自分の手書きの例がぐちゃぐちゃで混乱した。twitterでみなさんがアップロードしていた図と比べてだいぶ汚いので反省した。

a*2+b>aと書いたら1になってしまい焦った。やはりいつもくくったほうが安全。

三項演算子のミス a > b ? a+1 : b を撃墜できたのは良かった。

mediumは、ほぼ全員が提出＆赤い人だけ通って面白かった。みんな提出するけど間違いがちというのは良い問題だと思う。

SRM 553

03:05

Div1 Easy (250) Suminator

問題

• Suminatorは加算だけ可能なスタックマシンである。
• プログラムとして非負の整数の配列が与えられ、順番に実行する。
• スタックへは、プログラムが0なら2値を足して格納し、0以外ならそのまま格納する。
• 最後にスタックの先頭を表示して終了する。
• 一箇所だけ書き換えて結果をwantedResultにするための最小の数値を求める。

方針

• 書き換える場所をPOSとする
• POSを0に書き換えてシミュレーションし、結果がwantedResultなら0を返す(最小ケース)
• POSを1に書き換えてシミュレーションした結果をXとする
• XがwantedResultなら1を返す
• XがwantedResultより小さくて、かつ、Xを求めるためにPOSのデータを使っているなら、可能なのでwantedResult-X+1を返す
• それ以外は不能(-1)
• あらかじめスタックにはサイズの2倍だけ0を積んでおいた
• POSを使っているかどうかは、std::pairのsecondに入れておいた
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_553/Suminator.cpp

結果

o-- 164.13pt 206th rating 1251 -> 1344 (+93)

素直に考えて普通に書いたら通った。良い感じ。

longにしてないコードがたくさんあったようで結構落ちていた。

SRM 552

02:02

Div1 Easy (250) FoxPaintingBalls

問題

• ボールが3角形状に積み上げられている。
• 無色のボールをR、G、Bの3色に塗る。
• 隣り合うボールは異なる色で塗る。
• R、G、Bの塗布可能回数と、塗るボールの段数が与えられる。
• 塗れるセット数を求める。

方針

• なかなか題意がつかめない
• 最初の例が1なのをようやく理解する
• 塗り方じゃなくていくつ作れるかということか(遅い)
• 75分終了
• 3角形状に異なる色に塗るので、最初の2色を決めると全部決まる
• それぞれ同じ数だけ使う場合と、1個目に置いたやつが1個だけ多い場合(=最下段の両端が同じ色)がある
• 後者はNを3で割ると1余る
• 1セットに必要な塗布数T=N*(N+1)/2
• 総塗布可能回数をC=R+G+Bとして、セット数の最大はC÷T個
• 一方、各色は少なくとも(T÷3)=t個ずつ必要
• 答えはmin(min(R,G,B)÷t,C÷T)
• ただしN=1のときはR+G+B
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_552/FoxPaintingBalls.cpp

結果

--- 0pt 237th rating 1233 -> 1251 (+18)

0点なのにレートが上がった。反省しなければ。

SRM 551

02:08

Div1 Easy (250) ColorfulChocolates

問題

• 何色かのチョコレートが横一列に並んでいる。
• 交換して同じ色ができるだけ連続で並べたい。
• 交換回数が与えられる。最大の連続数を求める。

方針

• ある色Xを揃えるとき、XかX以外かを考えればよい
• すでに連続しているXは動かさない
• 連続していないXは、交換により1マスだけ動くのと等しい
• つまり追い越さない場合、交換回数=移動距離とみなせる
• 不動点を決める
• 近い距離のやつから集めていく
• 全ての点を不動点にしてみる全探索
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_551/ColorfulChocolates.cpp

Div1 Medium (450) ColorfulWolves

問題

• 毎晩毎に1回、色が変化する狼がいる。
• 各色にはインデックス値が与えられており、その晩に可能な変化のうち最小のインデックス値の色に変化する。
• 色Aから色Bへ変化するテーブルが与えられる。このテーブルは遺伝子操作により、特定の変化をしないようにすることができる。
• 色インデックスゼロからN-1に変化するための最小の遺伝子操作の回数を求める。

方針

• Warshall-Floydでいけるらしい
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_551/ColorfulWolves.cpp

結果

o-- 173.03 + 0 = 173.03pt 446th rating 1202 -> 1233 (+31)

easyは謎コードを書いてしまった。もっと単純な全探索で書けるべき。

mediumは400人くらいAC。さすがdiv1

SRM 550

02:46

Div1 Easy (250) RotatingBot

問題

• 直進と左90℃ターンを交互に行うロボットがW×Hの升目を移動する。
• ロボットは初期状態で東を向いていて、壁か一度でも通ったところの手前でターンする。
• ターンしても進めなくなるか、途中で停止したログが与えられる。
• W×Hを求める。不正なログの場合は-1を返す。

方針

• 1ターンずつシミュレーションして不正な状態かどうか調べる
• 提出、コーナーケースで死亡
• 解きなおし
• 最初に最大範囲だけ求めておく
• そのあと1ターンずつ進めて、不正な状態をチェック
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_550/RotatingBot.cpp

結果

x-- -1 151.03*0-25.0 = -25.0pt 681st rating 1339 -> 1202

チェックは分離すべきだった。

チャレンジ失敗はよいとして、システムテストでいっぱい落ちていたので反省。