[AtCoder]ABC174個人的メモ[Python]

はじめに

この記事は以下の事についての個人的メモ

• コンテスト中に考えてたこと
• 公式解説PDF,放送を噛み砕いたもの
• 提出したコード

E，F問題は手を付けてないのでメモも無い．
コードはコンテスト中に書いたのもあれば，後から書いたのもある．ACすることは確認済み．

環境

• Windows10
• VSCode : 1.47.3
• Python3.8.3
• online-judge-tools : 10.0.5
• atcoder-cli : 2.1.0

ABC174 A - Air Conditioner

AC
問題文通りに実装

ABC174A

#!/usr/bin/env python3
def main():
    import sys

    input = sys.stdin.readline

    X = int(input())
    if X >= 30:
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main()

ABC174 B - Distance

AC
最初は原点からの距離をnumpy.sqrt(x ** 2 + y ** 2)で計算したが，sampleの計算時間が遅かった．
なので，判定式の両辺を2乗してx ** 2 + y ** 2 <= D ** 2とした．
sqrtは誤差の原因になったり計算が遅かったりするから，避けられるなら避けたほうが良いらしい．

ABC174B

#!/usr/bin/env python3
def main():
    import sys

    input = sys.stdin.readline

    N, D = map(int, input().split())
    res = 0
    for _ in [0] * N:
        x, y = map(int, input().split())
        if x ** 2 + y ** 2 <= D ** 2:
            res += 1
    print(res)


if __name__ == '__main__':
    main()

ABC174 C - Repsept

WA．全然分からんかった．
最初は愚直にKに1，2，3，．．．，10 ** 7と順に掛けていって，それぞれの計算結果で全ての桁が7かを判定するコードを書いた．
10 ** 7は出力例3が6桁だったので，7桁ぐらい探索すればいいかなと考えて設定．
上記のコードで思いついた問題点は以下の2点

• 計算結果の桁が大きい(最大で10 ** 13とか)
• O(10 ** 7)でPythonだと速度が厳しい？
• 上限10 ** 7では，探索範囲が狭すぎる

2つ目はコンテスト中に気づいたけど，1つ目は気づかなかった．3つ目はコメントで指摘してもらって気づいた．出力例3はKの倍数となる数が999982桁であるということなので，探索範囲は10 ** 1000000ぐらい必要．
結局，修正案も思い浮かばず，飛ばした．
下のコードは解説放送見て実装した．以下の2点の特徴により，上記2点の問題点を克服してる．

• 計算結果xをK*nではなくmod K(剰余演算，モジュロ)とすることで，0<=x<Kとしている
• O(K)なので計算量は最大で10 ** 6

正直分かったような分からんような感じ．

ABC174C

#!/usr/bin/env python3
def main():
    import sys

    input = sys.stdin.readline

    K = int(input())

    x = 7 % K
    for i in range(1, K + 1):
        if x == 0:
            print(i)
            return
        # 1つ上の桁に7を追加してmod K
        x = (x * 10 + 7) % K
    print(-1)


if __name__ == '__main__':
    main()

ABC174 D - Alter Altar

WA．全然分からんかった．
どっかで見たような気がすると感じたけど，それだけで良い案は思いつかなかった．
これも解説放送見て書いたコード．
以下，問題とコードの解説
問題文より，与えられた石の列が2種の操作により以下の3通りのいずれかの状態になればおｋ

• 全部白色の石
• 全部赤色の石
• 赤色の石のみが連続した後，白色の石のみが連続する

左端の石を0番目，右端の石をN-1番目の石とする．
i（0<=i<=N-1）番目の石の後ろに仕切りを入れる．
仕切りの前の全ての白石を赤石に，仕切りの後の全ての赤石を白石にする操作を考える．
仕切りの前の白石の個数，後の赤石の個数の最大値がその仕切り時の最小操作数である．
というのも，石の色を変える方法は問題文より2種類ある．

• 2つの石を入れ替える
• 1つの石の色を変える

1つ目の方法は仕切りの前の白石と後の赤石を交換すれば，1操作で2つの石の色を変更でき，効率的．よって，1つ目の方法をできる限り多く使うのが良い．
しかし，この方法は仕切りの前後の石を入れ替えるため，仕切りの前か後のどちらかが操作完了した時点で使えなくなる．すると，残りは全て2つ目の方法を使うことになる．この時の操作回数は仕切り前の白石，後の赤石の個数の最大値となる．従って，両者の最大値が最小操作数となる．
これでi番目の仕切りの探索が終了．
仕切りをiが取り得る全ての場合で試し，その最小値がこの問題の解となる．
以上のコードで解は得られると思うが，計算量に問題がある．N個の石を走査して石の色を数える操作をN回行うので，O(N*N)となる．Nは2 * 10 ** 5以下だからO(10 ** 10)となり，TLEしそう．よって，計算量を減らす必要がある．
仕切りは左端の石の後ろから入れていくが，仕切りを1つ右に動かした時，仕切りの前後の石の数の遷移は以下の2通り．

• 新しい仕切り前の石が白の時，仕切り前の白石の個数が1つ増える
• 新しい仕切り前の石が赤の時，仕切り後の赤石がの個数が1つ減る

よって，事前に仕切りが左端の石の前(i=-1)の時の赤石の数を数えておき，仕切りを動かす度に仕切りの直前の石だけを確認することにする．これで走査する石は1つで済むため，計算量をO(N)になり，O(10 ** 5)となる．

ABC174D

#!/usr/bin/env python3
def main():
    import sys

    input = sys.stdin.readline

    N = int(input())
    c = input()

    white, red = 0, c.count('R')
    ans = max(white, red)
    for i in range(N):
        if c[i] == 'W':
            white += 1
        else:
            red -= 1
        res = max(white, red)
        ans = min(ans, res)
    print(ans)


if __name__ == '__main__':
    main()