Arc's blog

競プロなど

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

ソースコード

まず思いついたのは、


  1. 駅iに到着した時間=arrive[i] として、

  2. arrive[i]<=S[i]+F[i]*n となるような最小のnを見つける(次に乗る電車の到着時刻を計算)。

  3. arrive[i+1]=S[i]+F[i]*n+C[i]

これを終点に到着するまで繰り返す。


というもの。

だけど、このアルゴリズムだと(2)の処理にめちゃくちゃ時間がかかる。

そこで以下のように改良。


  1. 駅iに到着した時間=arrive[i] として、

  2. 駅iに到着してから次の電車が来るまでの時間=lag[i]とする。

  3. もし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年もプログラミング頑張りましょう。良いお年をお迎えください。