【AtCoder】ABC280のA,B,C,D における Python解説

ABC280のA,B,C,D問題を解くために考えたこと、ACできるPython3(PyPy3)コードを紹介します。

この記事は @u2dayo さんの記事を参考にしています。見たことのない方はそちらもご覧ください。とても勉強になります。

また、diffは問題の難易度を表す指標です。Atcoder Problems から引用しています。このサイトは勉強した問題を管理するのにとてもオススメです。

質問やご指摘はこちらまで
Twitter : Waaa1471

作者プロフィール
Atcoder ：緑 829
22/1203 現在

目次

はじめに
A.Pawn on a Grid
B.Inverse Prefix Sum
C.Extra Character
D.Factorial and Multiple

はじめに

特にC問題以降になると、競技プログラミングに典型的な前提知識、少し難しい数学的考察が必要になり始めます。
しかし、公式解説ではこの部分の解説があっさりしすぎていて競技プログラミング(Atcoder)を始めたばかりの人にはわかりにくい、難しいと感じるのではないでしょうか。

またC++がわからないと、コードの書き方を勉強することが難しいです。一応、参加者全員のコードを見ること自体は可能ですが、提出コードは必ずしも教育的ではありません(ここで紹介する記事も本番で提出したものとは全く異なります)。そんなものから初学者が解説もなしになにか得ることはとても難しいと思います。実際適当に何人かのコードをみたものの、意味がわからずに終わった経験があるのではないでしょうか。

この記事がそんな方々の勉強の助けになればよいなと思っています。

A.Pawn on a Grid　

問題

灰色 diff 12

考察

全探索

A問題にしては問題文が長く複雑ですが、結局は「入力に含まれる # の数がいくつであるか」を問われています。
したがって、素直に全てのマスを二重ループで見て # であれば カウンタを +1 する処理で解答できそうです。

さて、この方針で解答できるかどうかは H 行 W 列のマス目の大きさに依存します。ここで制約を見ると、1 <= H,W <= 10 なので 高々 100マスしかないことがわかり、余裕で全探索可能だと判断できます。計算量は O(HW)です。

コード

pypy3

H,W=[int(hw) for hw in input().split()]
ans=0
for _ in range(H):
    S=input()
    for s in S:
        if s=="#":
            ans+=1

print(ans)

補足

• 全探索
  競技プログラミングではこの方針のように、すべてに対して条件を満たすかを考える「全探索」と呼ばれるアプローチは基本です。特に A,B 問題では頻出です。

• 計算量
  計算量とは(競技)プログラミングを行う上で重要な概念で、そのコードを全うするためにおよそ何回の処理が必要かを表します。
  実は競技プログラミングは「正しい出力ができるか」に加えて、「制限時間内で処理が終わるか」も評価対象です。したがって、正しく出力できても問題が要求する処理速度を満たさなければ AC することはできず TLE の評価が下されます。
  Atcoder の A ～ E 問題 (作者の解答範囲) でのほとんどは制限時間 2 sec となっています。

また、この 2sec を満たすための計算量は PyPy3 で 10^7 ～ 10^8 となっています。
したがって、例えば H,W < 10^5 だと 2重ループ全探索の方針では TLE してしまいます。 なぜなら計算量 O(HW) が 10^8 を超えて制限時間に間に合わないためです。

A,B 問題は制約が非常に緩いので、どんな処理でも出力が正しければTLEすることなくACしてしまいます。そのため必須の概念ではありません。むしろ全探索になれることの方がよっぽど重要度が高いです。
しかし、C問題以降では計算量が重要なカギになってきます。

B.Inverse Prefix Sum

問題
灰色 diff 22

考察

式変形

「(A1 + A2 + ... + Ak-1)+ Ak = Sk 」から「 Ak = Sk - Sk-1 」を導けるかが問われています。

この関係がわかれば、S の要素を前から探索してA の要素を順に求めることができます。
また、あらかじめ S0 = 0 を S　に追加することで A1 を例外とすることなく処理できるテクニックを使用しています。
もちろん A1 の場合だけ if 分等で例外処理してもOKです。
計算量は O(N)です

また、リストを空白区切りで出力する必要があります。
出力形式に関して曖昧な方は、こちらのサイトがとても参考になるのでご覧ください。

コード

pypy3

N=int(input())
S=[0]+[int(s) for s in input().split()]
A=[]
for i in range(1,N+1):
    A.append(S[i]-S[i-1])

print(*A)

補足

• 累積和
  数列 S は数列A の累積和と呼ばれるものです。
  連続区間の全探索等で高速な処理を行う場合に必須のアルゴリズムです。

• 出力形式
  こちらのサイトが勉強に役立つはずです。(再掲載)

C.Extra Character

問題
灰色 diff 64

考察

基本に忠実に！　前から探索

S,T はひとつの要素を除いてすべての要素が同じです。また、複数の候補が考えられる場合はそれらのうちの任意の位置を答えてよいことになっています。そのため、異なる要素が見つかるまで前から順に S,Tをそれぞれ探索し、異なる要素が見つかった位置を目的の場所とみなすことができます。
例えば S=WaaaWaaa T=WaaaaWaaa では、異なる要素がはじめて見つかる場所は5番目です。この5番目に見つかった T の要素 a が S の4番目までに連続して存在する a のみからなる 区間のいづれかの位置に挿入されたことになります。もちろん5番目に挿入が生じたとしても矛盾がないので、5番目を出力すればよいです。

ただし、S= waaa T=waaaw　のような S の末尾に挿入が生じた場合は注意が必要です。もし、

for i in range(len(T)):
    if S[i] == T[i] 

のように要素同士の比較を進めると、S に範囲外アクセスすることになってしまいエラーが生じます。そのため B問題でも用いたテクニックであらかじめ、Sの要素としてありえない要素を末尾に追加して S,Tの長さを揃えることにします。

また、この問題はC問題では極めて簡単な部類なので、ぜひACできるようになりましょう。
計算量はO(|S|)です。

コード

pypy3

S=input()+"W"
T=input()
for i in range(len(T)):
    if S[i]==T[i]:
        continue
    print(i+1)
    exit()

補足

なし

D.Factorial and Multiple

問題
緑色 880

考察

K が非常に大きな ( 10^8を超える ) 素数を取りうることを考えると、N を全探索して N! % K で倍数判定する処理では制限時間に間に合わなそうです。

方針がすぐに思い付かないときは、簡単な例で実験してみましょう。

ステップ1 - 素因数に注目

例えば、K = 12 を考えます。

1! = 1
2! = 1 * 2 = 2
3! = 1 * 2 * 3 = 6
4! = 1 * 2 * 3 * 4 = 24

よって N=4 が条件を満たす最小の N であることがわかりました。これは素因数に注目するとより明確です。

3! = 2 * 3
4! = 2^3 * 3 　⊂　2^2 * 3 = K　　[⊂ は包含関係を表す記号]

この例から、「N! が K で割り切れること」と「K の全ての素因数が N! に不足なく含まれること」が等しいことがわかります。
また、素因数ごとに、条件をはじめて満たす N が異なりそうだと観察できます。実際、素因数 3　だけを考えると N = 3 の時点ですでに条件を満たしています。

ここまでの考察をまとめると、次のことが言えます。

K = p1^a1 * p2^a2 ....pn^an において、p1 が a1個 含まれるための最小値を N1 , p2 が a2 個含まれるための最小値をN2 , .... pn が an 個含まれるための最小値を Nn とした場合、求める N は N = max(N1,N2,....Nn) である。

以上、N1,N2...Nn を求めることができればこの問題を答えられる! というところまで来れました。

ステップ 2 - 素因数で何回割れるかでNを愚直に求めてみる

では N1 を求めます。
ここで N1 は p1 の倍数です。もしそうでないのなら、(N1　 -1)! に含まれる素因数 p1 の総数と、N1 ! に含まれる素因数 p1 の総数が一致してしまうので、条件を満たす最小値として少なくとも N1 はふさわしくないことになってしまうからです。

このことより、p1 の倍数を p1 から順に p1 で割っていき、割った回数(含まれる数) が初めて a1 以上になる値が N1 になります。
例えば K = 2^4 とすると、 p1 = 2 , a1 =4 であるので、2 を2で 1回、4 を2で 2回、6 を2で 1回割ったところで累計の割った回数が4 になって 初めて a1 以上となり N1 は 6 となります。

計算量考察

さて、あとはこの処理が時間内に実行できるかどうかです。
ここで制約を確認すると、K <= 10^12 なので、O(√N) で素因数分解を行うことは可能です

また、K <= 10^12 = 2^40 より、K の素因数はそれぞれ高々40個であることがわかります。(40>=a1,a2,...an)
さらに、ある整数X において素因数どうしの組み合わせである「 約数 」であっても高々 2√X　個しか存在しないことを考えると、素因数の種類はそれ以下であると推定できます。
つまり、素因数の総数 < 40 * 2 * √ K < 10^8 より、N1 ～ Nn を求めるために繰り返し素因数で割る処理は十分高速に実行できると判断できました。

※ 難しい数学なしで考える方法の一例として、この推定法を紹介しました。補足にて計算量 O(√N + logK) について数学的に議論しています。

実装では、素因数 px において　Nx が px * ax 以下であることに注目して、ループ範囲を設定しています。高々 40 個以下の倍数を調べればよいと考えて、in (x,x*50,x) などとしてもよいと思います。

コード

def prime_factorize(N):
    res = []
    for p in range(2, N):
        if p * p > N:
            break
        if N % p != 0:
            continue
        e = 0
        while N % p == 0:
            e += 1
            N //= p
        res.append((p, e))

    if N != 1:
        res.append((N, 1))

    return res

if __name__ == "__main__":
    K=int(input())
    X=prime_factorize(K)
    ans=0
    # 素因数 x が num 個
    for x,num in X:
        rem=num
        # x ～ num*x の範囲に Nx は存在する
        for Nx in range(x,x*(num+1),x):
            j=Nx
            # jは何回 xで割れるか
            while j%x==0:
                j//=x
                rem-=1
                if rem<=0:
                    break
            if rem<=0:
                break

        ans=max(Nx,ans)

    print(ans)

補足

• 素因数分解 O(√N)
  アルゴ式から関数を引用しました。素因数分解の仕組みから、コードの説明まで詳しく説明があるので、ぜひご覧ください。

• 素因数の総数　と計算量
  K = p1^a1 * p2^a2 ... とする。(p1<p2<...)
  両辺に対数を取ると
  logK = a1 * logp1 + a2 * logp2 +...
  logK >= (a1+a2+...) * logp1
  ⇔ logp1K (底の変換) = a1 + a2+...
  ここで、右辺は素因数の総数を表していて、K=10^12 = 2^40 p1=2 より
  40 >= 素因数の総数 を導くことができた。
  したがって、計算量は O( √N + 40 (logK最大値) ) となる。
  参考 : 素因数 wiki

終わり

E問題解けそうで解けないまま終了しました。今後追加するかも？？