1

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

5 min read

AtCoder Beginner Contest 220

https://atcoder.jp/contests/abc220

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

無事レート微増。 このペースをちゃんと維持できれば、年内800=入緑はなんとか達成できそうです。

A - Find Multiple

https://atcoder.jp/contests/abc220/tasks/abc220_a

数学的解決法(想定解)

  • X=B//CX = B//C (Bを割ってあまりを捨てた値)
  • Y=X×CY = X\times C
    • この時点でのY:B以下で一番大きいCの倍数
      • YがA以上であれば、答え:Yとして出力
      • YがA未満であれば、答え:-1として出力



ループによる力技

  • Cの倍数を1つずつ順に呼び出していく
    • もし呼び出した倍数が、A以上B以下である場合、それが答え
    • もし呼び出した倍数が、Bを超えた場合、ループを終了する





B - Base K

https://atcoder.jp/contests/abc220/tasks/abc220_b

n進数表記で書かれた文字列Sを、10進数表記で表すには…

  • ans=0とする

  • Sの先頭の桁から見ていき、順番に以下の操作を行う

    1. ansをn倍する
    2. ansに今見ている桁の数字を加える
  • Sの最後の桁まで見終わった時、ansが求めたい値になる

  • 具体例として、

  • 5進数で書かれた'123'を、10進数表記で表したい

    • ans=0と置く
      • 1桁目を見る=1
        • ansを5倍する→ans=0
        • ansに今見ている桁の数字を加える→ans=1
      • 2桁目を見る=2
        • ansを5倍する→ans=5
        • ansに今見ている桁の数字を加える→ans=7
      • 3桁目を見る=3
        • ansを5倍する→ans=35
        • ansに今見ている桁の数字を加える→ans=38
  • 「n進数 変換」などで検索して、ツールで確認してみると確かに正しい。

  • 後は入力A、Bを、K進数から10進数表記に戻して、積を求めると答えになる




Python限定?裏技解法:int関数

  • 公式ドキュメントより

https://docs.python.org/ja/3/library/functions.html?highlight=int#int

  • int(文字列,n)
    • n進数表記で書かれた文字列sを、一発で10進数表記に変換してくれる優れもの。
    • これを使えばわざわざ関数を作成しなくてもヨシ!



C - Long Sequence

https://atcoder.jp/contests/abc220/tasks/abc220_c

制約から裏道を考えて…

  • 数列AAの長さNNが最大10510^5、このAA1010010^100回連結したものをBBと置く
    • 数列和とかループとか、真面目にやる問題じゃなさそう
  • Xまでに、数列Aがまるごと入る個数を考える
    • 数列A全体の総和を先に取得しておけば、XまでにAが入る個数*総和でショートカットできそう
    • 後は実装の問題
    • あまりを切り捨てた除算から考えるのはA問題と近いかもしれない



D - FG operation

https://atcoder.jp/contests/abc220/tasks/abc220_d

2次元DP

  • DはDPのD(らしい)
  • dpを考える。
    • iとjの設定で少し躓いた。
    • dp[i][j]dp[i][j]
      • iAii \dots A_iまで操作が終わった
      • jj \dots 数列の先頭がjjである
      • dp[i][j]dp[i][j]の中身\dotsその状態になるような操作手順は何通りあるか?
  • 添字の取り扱い注意
    • もうちょっと2次元DPをさらさらーっと組めるようになりたいですね
  • mod忘れ注意
    • あまりを出す、大事(本番にmod忘れて1WA)



Discussion

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