hotpepsiの練習帳

SRM 608

math, ソート | 00:38

Div1 Easy (300) MysticAndCandies

問題

• N個の箱がある
• それぞれの箱にはキャンディーがlow[i]～high[i]個入っている
• キャンディーは全部でC個
• X個以上食べるには何箱あければよいか

方針

• 謎コードを提出
• Failed System Test
• (終了後)
• 最大値はN
• 十分条件その1: lowを足していってX以上になる場合
• 十分条件その2: Cからhighを引いていってX以上になる場合
• 候補の最小値が答え
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_608/MysticAndCandies.cpp

結果

x-- 0pt 389th/741 rating 1242 -> 1227 (-15)

十分条件ではさむのって典型ぽいけど割と解けない。

http://togetter.com/li/626507

SRM 607

DP, palindrome | 01:32

Div1 Easy (250) PalindromicSubstringsDiv1

問題

• a-zと?からなる文字列が与えられる
• ?はa-zのどれかに置換される
• 左右対称な部分文字列の個数の期待値を求める

方針

• O(N^3)でがんばって計算
• Challenge Succeeded
• (終了後)
• 奇数と偶数で、1つずつ左右に幅を広げながら数えるとO(N^2)
• 左右のどちらかが?のとき、確率が1/26になるが、1個だけのときは必ず左右対称
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_607/PalindromicSubstringsDiv1.cpp

結果

x-- -1 -25pt 700th/719 rating 1405 -> 1242 (-163)

単純だけど思いつかなかった。

http://togetter.com/li/624676

SRM 606

着想 | 23:55

Div1 Easy (250) EllysNumberGuessing

問題

• 数当てゲーム
• 1～1,000,000,000までの数を思い浮かべる
• 予想値と、絶対値の差のペアが配列で与えられる
• 数が一意ならその値、不定なら-1、嘘なら-2

方針

• 情報が正しい場合、guesses[i]-answers[i]かguesses[i]+answers[i]の2択
• answersを加味した数が1～1,000,000,000に収まらない場合は無視する
• guessesとanswersの範囲により、情報が正しい場合には、プラスかマイナスのどちらかに必ず答えが含まれている
• 一つの数だけN個を満たすとき、それが答え
• 二つの数がN個を満たすとき、不定
• それ以外の場合は嘘
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_606/EllysNumberGuessing.cpp

結果

o-- +2 153.58 + 100 = 253.58pt 135th/509 rating 1294 -> 1405 (+111)

最初に場合わけしたりすると意外とバグらせやすい問題。写経がんばった。

http://togetter.com/li/622772

SRM 605

greedy, ソート | 02:36

Div1 Easy (250) AlienAndHamburgers

問題

• エイリアンのFredは地球を滅ぼす前にハンバーガーを食べておくことにした
• 種類とおいしさの配列が与えられる
• 満足度は種類の数×おいしさの合計である
• 満足度の最大値を求める

方針

• 貪欲っぽい
• (種類,おいしさの降順)でソート
• ひとつずつ見ていき、同じ種類かつおいしさが正ならまとめる
• まとめたあと、おいしさでソート
• おいしさが正なら必ず増加する
• おいしさが負で、総量が増加しないなら、次のを食べても増加することはない
• おいしい順に食べて、食べても増えないならやめる
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_605/AlienAndHamburgers.cpp

結果

o-- 180.04pt 303rd/658 rating 1228 -> 1294 (+66)

ちゃんと解けた。

http://togetter.com/li/618981

SRM 604

math | 23:39

Div1 Easy (250) PowerOfThree

問題

• 4方向の移動を受け付けるロボットがいる
• ターンkに距離3^k移動できる
• 与えられた座標に移動可能かどうかを求める

方針

• 各桁が-1か+1の3進数みたいな感じ。平衡三進法というらしい。
• xとyを平衡三進法で表したとき、各桁がxとyどちらかだけに属すること
• x方向とy方向の移動をそれぞれビット化
• xとyが排他で、下位から全てのビットが連続していること
• Failed System Test
• 書き直し
• 一番下の桁から見ていく
• xとyを3で割った余りを調べる
• 片方だけ余りがあるならOK、そうでなければ不能
• 余りを加えて3で割っていく(余りが2のときは繰り下がりがあるので、そのぶんを加える)
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_604/PowerOfThree.cpp

結果

x-- 0pt 513rd/843 rating 1247 -> 1228 (-19)

余りの処理を間違って死。

Cの場合余りが数の正負に影響されるので、absで正にしておいたほうが楽。

http://togetter.com/li/614555