mery's Notes

めりーがプログラミングしたりします。

MENU

AtCoder Beginner Contest (ABC) 220 PythonでC問題解いてみた

前回解いたやつ

mery-kirokudayo.hateblo.jp

f:id:mery_poke:20211101224247p:plain

こんにちは。メリーです。

最高気温が10℃前後になって数日。
ようやく気温が低い状況に体が慣れて参りました。
ただ、朝起きると寒すぎて頭が痛くなる問題を今度はどうにかしたいと考えております。

ということで今日も元気を出してAtCoder Beginner Contest (ABC) 220のC問題を解いていきました。

今日は簡単めな問題だったので解説を見ずに行けました。
ちょっとバグちゃってそれの解消に10分くらいかかったけど・・・

というわけで目次

C問題 解答編

問題文

C - Long Sequence

数列Aが与えられます。
その数列Aを10100回連結した数列が数列Bです。
数列Bの各項の和を取っていくとき、和が初めてXを超えるのは第何項でしょうか?
という、一見、大学入試の問題っぽい問題。

f:id:mery_poke:20211021135506p:plain
数列A、Bのイメージ図

というわけで、問題文に書いてある通りに実装すれば全然問題なさそうっすね!

方針は、
1. 各項までの和を求める。
2. 和がxを超えたらその時の項を出力する。

という感じでやっていきましょう!!

実装したコードは以下の通り。

n = int(input())
a = list(map(int,input().split()))
x = int(input())

wa = 0

for i in range(n*(10**100)):
    wa += a[i%n]
    if wa > x:
        print(i+1)
        break

さあ、実行だ!!

f:id:mery_poke:20211021140133p:plain

はい、そうです。制限時間エラーですね。
ループ回数がn×10100だもんね。
108くらいに抑えないとね。

C問題 解答編(真)

というわけで本当の解答編。

愚直にやるとTLEなので、愚直にやらない方法を。

感覚としてはこんな感じに。

f:id:mery_poke:20211021141712p:plain
数列Bを簡略化したのが数列B’

そうすると、数列B’が単純な数列となる。
これであれば、数列B'の第何項が初めてxを超えるのかが簡単に求められる。(xを数列Aの和(数列B'の項)で割れば、数列B'の第何項が初めてxを超えるのかが求められる。)

そうして求めた項に数列Aの項数nをかけると、数列Bの第何項から第何項までの間でxを超えたのかがわかる。

f:id:mery_poke:20211021143119p:plain
イメージ図

あとは、その区間でいつ超えたのかをfor文でチェックすればok。

まとめると、方針として、
1. 数列Aの和を求める
2. 1の和でxを割った商と余りを求める。
3. 数列Aの各項を足し、初めて2の余りを超えた第i項を記録する。
4. 2で求めた商×n + iが求める答え

ということになります。

実装したのがこれ↓

n = int(input())
a = list(map(int,input().split()))
x = int(input())
wa = 0

for i in range(n):
    wa += a[i]


shou = (x//wa)*n
nokori = x%wa

for j in range(n):
    nokori -= a[j]
    if nokori < 0:
        shou += j+1
        break

print(shou)

waで数列Aの和を求めて、shou、nokoriをそれぞれ出しました。
shouで求めた次の数列Aの繰り返しの中に求める項があります。
nokoriが0を下回る = xを超える
なので、その時のj+1(+1しているのはjが0始まりだから)をshouに足せば答えが出ます。

僕は break を忘れたせいで、結果がおかしくなりました。見落としがちなので気を付けてください。

それでは。