AtCoder Beginner Contest(ABC) 084 レビュー
今回は12/30のAtCoder Beginner Contest(ABC)084 についてです。
あ、前回のABC083ですが……全然ネタがないので飛ばします……
A - New Year
2日は48時間。48-M
すればOK。
B - Postal Code
ハイフンが見つかる or 文字列の末端まで到達する
まで文字数をカウント。これを二回繰り返す。
最初のカウント数==A and 二回目のカウント数==B
なら条件を満たす。
C - Special Trains
まず思いついたのは、
駅iに到着した時間=arrive[i]
として、arrive[i]<=S[i]+F[i]*n
となるような最小のnを見つける(次に乗る電車の到着時刻を計算)。arrive[i+1]=S[i]+F[i]*n+C[i]
これを終点に到着するまで繰り返す。
というもの。
だけど、このアルゴリズムだと(2)の処理にめちゃくちゃ時間がかかる。
そこで以下のように改良。
駅iに到着した時間=arrive[i]
として、駅iに到着してから次の電車が来るまでの時間=lag[i]
とする。もし
arrive[i]-s[i]<0
なら(まだ最初の電車が動いていなかったら)arrive[i+1]=S[i]+C[i]
、そうでなければarrive[i+1]=S[i]+lag[i]+C[i]
これを終点に到着するまで繰り返す。
で、lag[i]
の計算方法は、
lag[i]=F[i]-((arrive[i]-S[i])%F[i])
もしlag[i]=F[i]
ならlag[i]=0
にする
という感じ。
これなら計算量少なくて済む。
D - 2017-like Number
1つのクエリ(l[i],r[i])
に関して、l[i]<=n<=r[i]
を満たす全ての奇数nをチェックするのは明らかに無駄。同じnに対してチェックを何回も繰り返すことになる。
たとえばクエリが(l,r)=(5,9),(3,11)
なら、5,7,9
は二回チェックしていることになる。時間が足りない。
ということで、累積和を使うことにする。
rui[i] = [1<=n<=i*2+1を満たす奇数nのうち、2017に似た数の個数]
と定義すると、クエリ(l[i],r[i])
に対して
left=l[i]/2 , right=r[i]/2
と定義し
left==0
ならrui[right]
を出力そうでないなら
rui[right]-rui[left-1]
を出力
以上の処理を実行することで解答可能。
で、「2017に似た数」をどうやって判別するかですが……「エラトステネスの篩」でググってみてください。僕は使いませんでした。完全に嘘解法です。
あと、この問題解いている時にコンパイラのバグ(?)に遭遇。プログラム上では書き込んでいないグローバル変数に勝手に値が書き込まれてました。AtCoderのシステムにソースコード投げたらあっさりACしましたが。
まとめ
- 初めてABC4完しました。やったね。
- でもARC上位陣が沢山いたからか、パフォーマンスはそこまで良くもなかったです。自己ベストだけど。
- 茶レートにあがりました。
- デバッグ用の出力はちゃんとコメントアウトしましょう。これのせいで1WA。
- 実戦で累積和使えたので良かったです。
- エラトステネスの篩ぐらい知っておこう……。
それでは皆様、2018年もプログラミング頑張りましょう。良いお年をお迎えください。