hotpepsiの練習帳

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点しかもらえなかったが、当面は解けるほうが重要。