hotpepsiの練習帳

SRM 562

23:49

Div1 Easy (250) PastingPaintingDivOne

問題

• きゅうり君は絵を描くのが大好きである。
• クリップボードにRGBの点で描かれた絵が格納されている。
• 絵を横1縦1ピクセルずつずらしてキャンバスに貼り付ける。
• 絵の点がある部分は上書きされ、ない部分はそのままである。
• T回ペーストしたときのRGBの点の総数を求める。

方針

• 絵のサイズは最大50×50なので、200回くらいシミュレーションすれば求まりそう
• なんか合わない...
• 考え直す
• 点が左斜め上に存在すれば、重ね塗りされる
• すなわち左斜め上方向のaマス先に点があるとき、最後のa回を除いて上書きされるので、総和にはaを足せばよい
• ただし最大でT回以内(＝min(a,T))
• 提出
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_562/PastingPaintingDivOne.cpp

結果

o-- 95.09pt 380th rating 1268 (unrated)

遅かったがちゃんと解けた。

前回と今回のeasyが通ったのはなかなかいい感じ。

ちゃんと考えるとシンプルだし、モチーフも良いのできゅうりさんは天才だと思う。

SRM 561

01:49

Div1 Easy (250) ICPCBalloons

問題

• コンテストを開催し、M個の問題を出題した。
• 正解者には風船を配る。
• 風船の色は問題毎に全て異なっている必要がある。
• 風船のサイズはMとLの二種類あり、同じ問題では同じサイズの風船を配る必要がある。
• 風船は別の色に塗ることができるが、サイズは変更できない。
• 風船を塗りなおす回数を求める。

方針

• サイズが2種類あるのでメモ化が思いつかない
• 問題に割り当てるサイズをどっちにするか悩む
• 制約条件を見直したら問題数が最大15
• MとLの全パターンは最大32768通りなので列挙できそう
• 塗りなおしを最小化するには...
• どこかに割り当てたあとは、全部塗りなおし
• 個数の多い風船から順番に、回答の多い問題に割り当てれば良いっぽい
• 問題A,B,C、風船P,Q,Rが降順に並んでいるとき、A->P、B->Q、C->Rに割り当てる
• 風船の種類と問題数の少ないほうでループして、余りは全て塗りなおし
• 提出
• デバッグコードが残ってて再提出
• Passed System Test
• (終了後解き直し)
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_561/ICPCBalloons.cpp

結果

o-- 75.05pt 369th rating 1232 -> 1268 (+36)

時間かかりすぎ＆再提出だが、方針が合ってたのは良かった。塗り直し分も分配してしまったがそれは不要だった。

SRM 560

02:47

Div2 Easy (250) TypingDistance

問題

• 指1本でキーボードを打つ
• キーボードの配列が与えられる
• 指の移動距離を求める

方針

• 最初以外の移動距離を足すだけ
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_560/TypingDistance.cpp

Div2 Medium (500) TomekPhone

問題

• 新しいガラケーのキーボードをデザインしたい
• テキストの各文字のカウント、キーの最大数、各キーの最大ストローク数が与えられる
• テキストを入力したときの合計ストローク数を求める

方針

• 最大のカウントの文字から順番に割り振るだけ?
• 反例が思いつかない＆サンプル通ったので提出
• Passed System Test
• (解き直し)
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_560/TomekPhone.cpp

結果

oo- 245.01pt + 382.63pt = 627.64pt 101st rating 1189 -> 1232 (+43)

なんとかdiv1復帰。

mediumのキーの割り振りは、無駄にループしてしまった。

割り当て可能な全てのストローク数を用意しておき、ソートして、小さいものから割り振ればよかった。で、ストローク数でループすると、もっとシンプルになった。

CodeSprint 3

22:30

A. Exchange

問題

• 数列と、交換可能な位置が与えられる
• 辞書順最小になるように交換した数列を求める

方針

• 芋づる式に交換可能と考えて、union findに突っ込む
• 合ってるっぽい

B. Random number generator

問題

• 指定した範囲で実数の乱数が生成できるジェネレータがある
• 乱数xと乱数yの和がC以下になる確率を分数で求める

方針

• わからない...
• とりあえず色んな値で出力してみる
• 台形になっている
• それっぽい値を出力、AC

結果

o-----o 51.0pt 483rd

3時間くらい参加。一番解かれている問題だけ解いた。

このシステム、見るたびに得点が違うのが謎。

SRM 559

21:25

Div1 Easy (250) HyperKnight

問題

• チェス盤の大きさと(±a,±b)で動けるナイトが与えられる。
• 移動可能な先がちょうどk箇所ある升目の総数を求める。

方針

• 「k歩で行ける升目の総数」に誤読
• チャレンジフェーズでやっと理解
• (終了後)
• cafelierさんのを写経
• 5×5に区切って判定、これはわかりやすい＆書きやすい
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_559/HyperKnight.cpp

Div2 Easy (250) BlockTower

問題

• N個のブロックを順番に積む。
• 奇数の高さのブロックの上には偶数の高さのブロックは積めない。
• 最大の高さを求める。

方針

• DP?
• 次に積むのが奇数なら、常に積める
• 次に積むのが偶数なら、最後に偶数で積んだ最大の
• 要は最後に積んだやつだけ覚えておけばいい
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_559/BlockTower.cpp

結果

x-- -1 -25pt 419th rating 1354 -> 1189 (-165)

チャレンジ失敗でdiv2へ...最初に問題文を読み間違うとはまる。

div2 easyのレベルが上がっている気がする。