2

ABC223 茶色コーダーが解けた所まで

6 min read

AtCoder Beginner Contest 223

https://atcoder.jp/contests/abc223

ABC223の問題を、本番で自分が解けた所までの解説です。

602 → 677 (+75)

4完に戻りました…!!!
+75は大きい。過去最大パフォ。
(昨日のARCで0完やらかしてなければ今頃730位あったんですけどね…)

来週のARC129/ABC223で緑パフォが出せたら、3ヶ月入緑の可能性もまだあります…!

追記: ARC129が無くなったため、3ヶ月で入緑の可能性がほぼほぼなくなりました…。
3ヶ月ちょっとでの入緑を目指します…。

A - Exact Price

Difficulty: 6
https://atcoder.jp/contests/abc223/tasks/abc223_a

条件から、あり得る状態とありえない状態

  • 100円硬貨が1枚以上入っている
    • 高橋くんの財布の中身が一番少ない状態でも100円はあるよね
      • 100円未満(99円以下)の状態はありえないね
  • 100円硬貨以外は何も入っていない
    • 100円、200円、300円………N×100N \times 100円なら、あり得る状態だね

何を聞かれてる?

財布の中の合計金額がX円である可能性はありますか?

  • X円が、上記の「あり得る状態」であるかをif文で判定すればOK



B - String Shifting

Difficulty: 86
https://atcoder.jp/contests/abc223/tasks/abc223_b

左シフトと右シフトについて

  • abcdeを左シフトしていくと、

    • abcdebcdeacdeabdeabceabcdabcde→以下ループ
  • 逆に、abcdeを右シフトしていくと、

    • abcdeeabcddeabccdeabbcdeaabcde→以下ループ
  • 以上の観察を踏まえると、以下の事が分かる

    • 文字列の長さ回数でループしてる(右シフト5回で最初に戻る)
    • 右シフト、左シフトどちら向きに動かしても順番が変わるだけで、成立する文字列は一緒

条件を確認する

  • 文字列の長さは最大1000文字
    • 最大1000回シフトして、全部一覧にしてあげてソートしたら最小(辞書順最小)、最大(辞書順最大)が出てくるね
      • 0回シフトと1000回シフトは同じ文字列が出てくるので、999回(=N-1回)のシフトで良いね。



C - Doukasen

Difficulty: 354 https://atcoder.jp/contests/abc223/tasks/abc223_c

実装面倒くさい系シミュレーション

  • 前回のABCもシミュレーション系の実装だったような…?

  • 導火線の両端に火をつけて、2つの火がぶつかるまでの時間=「導火線の片方に火をつけて、全部燃え尽きるまでの時間」の半分

    • 初手で全部燃え尽きるまでの時間を記録しておくと楽ですね



D - Restricted Permutation

Difficulty: 1069
https://atcoder.jp/contests/abc222/tasks/abc222_d

解説したくない…WAKARANAI…

  • 公式(想定解)は、有向グラフに見立てて、トポロジカルソートした結果として辞書順最小のものが答え
    • 辞書順最小のものに関する問題は、heapqが優秀。全部出して全部入れてもO(NlogN)O(N\log N)
      • 計算量周りの考えは自信がないです…

公式の条件を言い換えてみる

  • AiA_iBiB_iよりも先に現れる
    • 数列において、BiB_iが出てこないとAiA_iが出せない

実装どうしよう…

* heapqで辞書順最小の配列を作る
    * heappopで最小値が出てくる便利
* dictを2種類使って、heapqに追加できる数字、出来ない数字を管理する
    * lock_d_a:キーに数字を入れると、「その数字を使うには、使ってないといけない数字」の一覧(set)
    * lock_d_b:キーに数字を入れると、「その数字を使用すると、使えることに成る数字」の一覧(set)


Discussion

コメントにはログインが必要です。