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

AtCoder Beginner Contest 223

https://atcoder.jp/contests/abc223

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

602 → 677 (+75)

4完に戻りました…！！！
+75は大きい。過去最大パフォ。
(昨日のARCで０完やらかしてなければ今頃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円硬貨以外は何も入っていない
  • １００円、２００円、３００円………$N \times 100$円なら、あり得る状態だね

何を聞かれてる？

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

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

B - String Shifting

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

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

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

  • abcde→bcdea→cdeab→deabc→eabcd→abcde→以下ループ

• 逆に、abcdeを右シフトしていくと、

  • abcde→eabcd→deabc→cdeab→bcdea→abcde→以下ループ

• 以上の観察を踏まえると、以下の事が分かる

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

条件を確認する

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

C - Doukasen

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

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

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

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

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

D - Restricted Permutation

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

解説したくない…WAKARANAI…

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

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

• $A_i$は$B_i$よりも先に現れる
  • 数列において、$B_i$が出てこないと$A_i$が出せない

実装どうしよう…

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