hotpepsiの練習帳

SRM 514 Div2

01:47

不参加なので後追い。

Easy (250) MagicalGirlLevelOneDivTwo

問題

• 魔女をやっつけるために移動する
• 魔法は2d×2dの大きさの正方形
• 最小の移動距離を返す

方針

• すでに射程内なら移動しない
• x,yが負のときを考慮する
• 水平移動距離min(0, |x|-d)
• 垂直移動距離min(0, |y|-d)

実装

• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_514/MagicalGirlLevelOneDivTwo.cpp

Medium (500)

問題

• 魔女をやっつけるために移動する
• チェスのナイトみたいな動きしかできない (n歩+1歩)

方針

• TLEしたのでAnalysisを読む。
• 奇数の移動(nが偶数)ができればどこでも移動できる
• そうでなければ、(x+y)が偶数ならYES

実装

• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_514/MagicalGirlLevelTwoDivTwo.cpp

Hard (1000)

問題

• 魔法少女が、悪い魔女を倒すために応用呪文を唱えようとしている
• 応用呪文はK個の基本呪文の組み合わせからなる
• 応用呪文A[i]は、A[i-1] + A[i-K-1] + A[i-2*K-1] + ...という和である
• 呪文の強さは、呪文を唱える範囲のビットが立っている数の和である
• 応用呪文A[n][lo..hi]の強さSを求める

方針

• 題意がわからなかった
• kusanoさんのを写経して理解
• A[x]の長さを求めておいて、どのindexに入っているのかを再帰で求める

実装

• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_514/MagicalGirlLevelThreeDivTwo.cpp

SRM 515 Div2

02:19

Easy (250) FortunateNumbers

問題

• 5と8がラッキーナンバー
• 3つの数の和がラッキーナンバーだけでできている値の個数を数える

方針

• 二重ループでaとbの和をsetに突っ込んでおく
• (aとbの和)とcの和をsetに突っ込む
• 最後の集合がラッキーナンバーか判定

実装

• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_515/FortunateNumbers.cpp

Medium (500) RotatedClock

問題

• 数字が書いていない時計の時刻を当てる

方針

• 短針が30度を超えていたら30度戻す (最小値を求めるためだが、一意に求まるので不要だった)
• 短針を30度ずつ加えていき、時刻として成立しているかどうか調べる

実装

• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_515/RotatedClock.cpp

Hard (1000) NewItemShopTwo

問題

• アイテムショップに商品が1つだけある。
• 客が2人いて、それぞれの客は一日に一回だけ来る。
• それぞれの客が来る時刻、購入価格、確率が与えられる。
• アイテムショップの最大の利益を求める。

方針

• 遅い時刻からDP
• 他の方の回答を読んでも理解できないので、二つに分離
• 客が一人しかいない場合の期待値earnを計算しておく
• どちらかの客が来る時刻の期待値は、(客が来る確率×(価格ともう一方の客のearnとの大きいほう))＋(客が来ない確率×(次の時刻の期待値))となる

実装

• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_515/NewItemShopTwo.cpp

結果

oo- 181.90+390.79 rating 999→1116 easyに時間がかかりすぎたが、mediumが早めだったので大幅up。

easyは蟻本のくじの問題に似ていたので、二重ループ→ループにしてみたが、三重ループでも十分間に合ったかも。

513と514を飛ばしてしまったので、あとで解く。

SRM 510 Div2

00:25

Easy (250) TheAlmostLuckyNumbersDivTwo

問題

• 4と7が超ラッキーナンバー
• ある整数nの各桁において、4と7以外の数値が合計1個以下ならラッキーナンバーとする
• 整数の範囲[a,b]のラッキーナンバーの総数を求める

方針

• 1000000しかないのでループして数える

実装

• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_510/TheAlmostLuckyNumbersDivTwo.cpp

Medium (500) TheLuckyGameDivTwo

問題

• 4と7がラッキーナンバー
• 整数の範囲[a,b]のうち、Johnがその一部を選び、Brusがさらにその一部を選ぶというゲーム
• Brusが選んだ範囲にあるラッキーナンバーの総数が最終スコア
• Johnは最終スコアを高くするための戦略をとる
• Brusは最終スコアを低くするための戦略をとる
• 最終スコアXを答える

解釈

• Johnが選択した時点ではスコアにならない
• Brusの選択結果がスコアになる
• という前提でのJohnの最適化戦略を求める

方針

• Johnの各手に対するBrusのminimumを求めてみる
• Brusのminimumのうちで最大のものが答え

実装

• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_510/TheLuckyGameDivTwo.cpp

Hard (1000) TheLuckyBasesDivTwo

残り時間がなかったので問題見ただけ。解きなおし

問題

• 数Nが与えられる。
• 全ての桁が4か7だけで表せるのがラッキーナンバーである。
• NをB進数で表したとき、ラッキーナンバーになるBの総数を求める。

方針

• 1 <= B < Nだと多すぎて間に合わない
• 1桁と2桁と、3桁以上で場合わけすればよいらしい
• Nが4か7なら無限にある
• 2桁で表せる場合は、4か7で割って判定可能
• 3桁以上の場合、ループして判定するが、最大でもsqrt(N)なので間に合う
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_510/TheLuckyBasesDivTwo.cpp

結果

oo- 238.62+259.97

EasyとMediumが通りratingが908→1004へ。

Mediumをゆっくり解きすぎて260点しかもらえなかったが、当面は解けるほうが重要。

SRM 509 Div2

00:20

Easy (250) PalindromizationDiv2

問題

• 0から100000までの数が与えられる
• 加算または減算で、左右対称にするための最小コストを求める

方針

• 10で割った余りで判定するのをループ

実装

• 本番: 数の範囲が小さいので場合わけして解いた
• 解きなおし: 正順と逆順で格納してから、半分の長さでmemcmp
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_509/PalindromizationDiv2.cpp

Medium (500) LuckyRemainder

問題

• n個の数値が与えられる
• その数を組み合わせてできる全ての数の合計を9で割った余りを求める

方針

• 9の余りは、どの桁にあっても同じ
• それぞれの桁の数を足してから余りを求めればよい
• それぞれの値は、使うか使わないかで2^(n-1)回出現する

実装

• 本番: 総数を数え間違えてsubmitまで至らず
• 解きなおし: それぞれの数を合計してから2^(n-1)倍して、最後にmod 9を求める
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_509/LuckyRemainder.cpp

Hard (1000) NumberLabyrinthDiv2

問題

• 縦R×横Cのマス目があり、空または数字が書いてある。
• 数字が書いてあるコマからは、その数値だけ縦または横にジャンプできる。
• 空のマスには全体でK個だけ数字を書くことができる。
• 始点と終点が与えられるとき、最小のジャンプ回数を求める。

方針

• 基本はBFSで探索
• 数字がない場所は、書けば行ける
• 書いた場合は、次のレベルのキューに突っ込むようにする
• 書かずに行ける場所を全部処理してから、次のレベルを処理する
• 書くことによって最小値が更新されることがあるので、常にK個書く
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_509/NumberLabyrinthDiv2.cpp

結果

o-- 158.15 955 -> 908

Easyしか通らなかったのでrateが微減...

SRM 508 Div2

01:58

Easy (250) CandyShop

問題

• キャンディー屋の候補が座標で与えられる
• 可能性のある座標の数を求める

方針

• 本番: 配列で持つ(範囲が間違っていて失敗)
• 解きなおし: 1番目の座標(x0,y0)の範囲内に対して、全(xn,yn)が条件を満たすかどうかを調べる

実装

• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_508/CandyShop.cpp

反省点

• きちんと最大範囲を確認すること

Medium (500) DivideAndShift

問題

• N個の駒と、M番目が与えられる
• 素数による除算か、左右いずれかのシフト(ローテート)が可能
• M番目の駒をいちばん左端に移動するための最小コストを求める

方針

• 除算して位置が大きくなることはないので、シフトは最後にやればよい。
• 本番: 素因数分解して総当り(間に合わずに失敗)
• 解きなおし: 2からNまでの全ての除算可能な数で割ってみて、それらの最小コスト(素因数の数+シフトの数)を求める

実装

• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_508/DivideAndShift.cpp

Hard (1000) YetAnotherORProblem2

問題

• R以下のN個の数値において、和と論理和が等しい組み合わせの数を求める。

方針

• 途方に暮れる
• 写経!
• j以下について、bitの部分集合のうちR以下のものを加算、というループでいける
• 和はRを超えるケースがあることに留意する
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_508/YetAnotherORProblem2.cpp

感想など

x-- 142.02 1028 -> 955

• Mediumむずい。
• 素数テーブルが手元になかったので、エラトステネスのふるいと、試行除算で実装して速度を比較したりしてみた。エラトステネスのふるいが想像したよりも速かった。
• MediumではM番目が与えられるが、mod演算するため、0-based indexにしておく。
• 右シフトでのコストは、最も右のN-1にあるときに1なので、indexをmとすると、(N-1 - m)+1つまりN-mになる。
• 素数表は1000000まで作っておく必要あり。System Testには最大の素数(999983)が入っている。