Pythonで取り組む競プロ典型 90 問 #星3 - ebisukeプログラミング初心者脱出黙示録

競技プログラミングの実力アップのためE869129さんが企画された競プロ典型90問に取り組みました。

難易度が★の数で表示されており、★3問題をPythonで解きました。

競プロ典型90問の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com

002 - Encyclopedia of Parentheses（★3）
007 - CP Classes（★3）
014 - We Used to Sing a Song Together（★3）
016 - Minimum Coins（★3）
018 - Statue of Chokudai（★3）
020 - Log Inequality（★3）
032 - AtCoder Ekiden（★3）
038 - Large LCM（★3）
044 - Shift and Swapping（★3）
046 - I Love 46（★3）
048 - I will not drop out（★3）
050 - Stair Jump（★3）
052 - Dice Product（★3）
064 - Uplift（★3）
069 - Colorful Blocks 2（★3）
075 - Magic For Balls（★3）
079 - Two by Two（★3）
082 - Counting Numbers（★3）
084 - There are two types of characters（★3）

002 - Encyclopedia of Parentheses（★3）

問題文
長さ N の正しいカッコ列をすべて、辞書順に出力してください。

ただし、正しいカッコ列は次のように定義されています :

・() は正しいカッコ列である
・S が正しいカッコ列であるとき、文字列 ( +S+ ) は正しいカッコ列である
・S,T が正しいカッコ列であるとき、文字列 S+T は正しいカッコ列である
・それ以外の文字列はすべて、正しいカッコ列でない
例えば、

・( ) ( )
・( ( ) ( ) ) ( ( ) )
・( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )
は正しいカッコ列ですが、

・) (
・) ) ) ( ) ( ( (
・( ( ( ( a ) ) ) )
は正しいカッコ列ではありません。

また、 ( の方が ) よりも辞書順で早いものとします。

制約
・1≤N≤20
・N は整数

解答例

n = int(input())

ans = []
for bit in range(2**n):
    res = ""
    tmp = 0
    for i in range(n):
        if (bit >> i) & 1:
            res += "("
            tmp += 1
        else:
            res += ")"
            tmp -= 1
        if tmp < 0:
            break
    if tmp == 0:
        ans.append(res)

ans.sort()

for i in range(len(ans)):
    print(ans[i])

解説
問題文にある正しい括弧列をすべて出力する問題です。

制約をみるとNが20以下と小さいのでbit全探索で正しい括弧列を調べていきます。

候補となる括弧列をresとしてbitが1なら"("、0なら")"を加えていきます。

あわせて正しい括弧列の条件は"("と")"の数が同じで、左から見ていって"("の数が")”の数以上であることが挙げられます。
したがって、"("ときtmpに1を足し、")"のとき1を引いて上記の条件を見ていきました。

ループの途中でtmpが0より小さくなれば正しい括弧列にならないのでbreakして次の探索を行います。
Ｎ文字の追加が終わったあとでtmpが0なら"("と")"の数が等しいのでansにresを追加しました。

この探索が終わったあとでansをソートして、改行区切で出力すればＯＫでした。

007 - CP Classes（★3）

問題文
ABC 競技プログラミング塾には N 個のクラスがあり、番号 i (1≤i≤N) のクラスはレーティング Ai の生徒を対象としています。

今、Q 人の生徒がこの塾に入塾しようとしています。番号 j (1≤j≤Q) の生徒のレーティングは Bj です。各生徒は自分に合わないレベルのクラスに行くと不満になります。各生徒について、その不満度は次のように定義されます。

・対象レーティング a と自分のレーティング b の差の絶対値、すなわち |a−b|
j=1,2,3,…,Q それぞれについて、番号 j の生徒の不満度として考えられる最小値を求めてください。ただし、1 人も入らないクラス、複数人から成るクラスがあっても良いものとします。

制約
・1≤N≤300000
・1≤Q≤300000
・0≤Ai≤10^9
・0≤Bj≤10^9
・入力はすべて整数

解答例

import bisect

n = int(input())

A = list(map(int, input().split()))

q = int(input())

B = []
for i in range(q):
    B.append(int(input()))

A.sort()

for i in range(q):
    tmp1 = int(1e9)
    tmp2 = int(1e9)
    num = bisect.bisect_left(A, B[i])
    if num >= 1:
        tmp1 = abs(A[num-1] - B[i])
    if num <= n-1:
        tmp2 = abs(A[num] - B[i])
    ans = min(tmp1, tmp2)
    print(ans)

解説
レーティングB[i]の生徒がレーティングA[i]を対象としたクラスに通ったときの不満度|A[i] - B[i]|の最小値を答える問題です。

クラスのレーティングAをソートして二分探索を行い、生徒に対して最適なクラスを求めます。

各生徒のレーティングB[i]で二分探索したときのAへの挿入位置をnumとして、numのクラスと1個下のクラスとの不満度を求めました。
このうち小さいほうが不満度の最小値となるので、その値を出力していけばＯＫでした。

014 - We Used to Sing a Song Together（★3）

問題文
AGC 街道には N 人の小学生が住んでおり、小学生 i (1≤i≤N) の家は位置 Ai にあります。
また、小学校は N 校建てられており、小学校 j (1≤j≤N) は位置 Bj にあります。
AGC 街道に住む小学生は性格が悪く、どの人同士も険悪な関係になっているため、全員が別の学校に通うようにしたいです。

また、不便さは次のように定義されます。

・小学生 i にとっての家から学校までの距離を Ei とするとき、不便さは距離の総和、すなわち E1+E2+...+EN である。
・ただし、位置 u から位置 v までの距離は |u−v|
どの生徒も別の学校に通うという条件下における、不便さとして考えられる最小値を求めてください。

制約
・1≤N≤100000
・0≤Ai≤10^9
・0≤Bj≤10^9
・A1,A2,…,AN は相異なる
・B1,B2,…,BN は相異なる
・入力はすべて整数

解答例

n = int(input())

A = list(map(int, input().split()))
B = list(map(int, input().split()))

A.sort()
B.sort()

ans = 0
for i in range(n):
    ans += abs(A[i] - B[i])

print(ans)

解説
N人の小学生とN個の小学校があり、どの生徒も別の学校に通うとき、小学生の家から学校までの距離の最小値を答える問題です。

一番左に住む小学生を一番左の学校に、2番目の生徒を2番目の学校に・・・と通学させると生徒の家と学校までの距離の総和を最小にできます。

まず、小学生の家の位置リストAと小学校の位置リストBをそれぞれソートします。

求める距離の総和をansとして、ループで家の位置A[i]から小学校の位置B[i]を引いた値の絶対値を足しあわせました。

ループを抜けたあとでansを出力すればACでした！

016 - Minimum Coins（★3）

問題文
A 円硬貨、B 円硬貨、C 円硬貨をそれぞれ 0 枚以上使ってちょうど N 円を支払うとき、使う硬貨の枚数として考えられる最小値を求めてください。

ただし、それぞれの硬貨は無数にあるものとします。

制約
・1≤A,B,C,N≤10^9
・A,B,C はすべて異なる
・合計 9999 枚以下の硬貨でちょうど N 円を支払うことができる
・入力はすべて整数

解答例

n = int(input())

a, b, c = map(int,input().split())

num = 9999
for i in range(num):
    for j in range(num - i):
        k = (n - a*i - b*j) // c
        if a*i + b*j + c*k == n and k >= 0:
            num = min(num, i+j+k)

print(num)

解説
A,B,C円硬貨でN円ちょうどを支払うときの最小枚数を答える問題です。

3重ループの全探索では間に合わないので工夫して探索数を減らす問題です。

A,Bの枚数が決まるとCの枚数は計算で求まるので2重ループで全探索しました。
i , j , kから金額を計算しちょうどN円になれば候補となります。
ちょうどN円になる組み合わせから最小の枚数をnumとしました。

最後にnumを出力すればACでした。

018 - Statue of Chokudai（★3）

問題文
平面 x=0 上に、高さ L の T 分で一周する観覧車があります。観覧車は円形になっており、次のように一定の速さで動きます。ただし、xy 平面が水平方向、z 軸が垂直方向です。

・乗ってから 0 分後には、座標 (0,0,0) にある
・乗ってから T/4 分後には、座標 (0,−L2,L2) にある
・乗ってから T/2 分後には、座標 (0,0,L) にある
・乗ってから 3T/4 分後には、座標 (0,L2,L2) にある
観覧車の名物である「高橋直大像」は、座標 (X,Y,0) に存在します。以下の形式の質問が Q 個与えられるので、順に答えてください。

・i 個目の質問では、E869120 君が観覧車に乗ってから Ei 分後における、E869120 君から見た高橋直大像の俯角を求めよ。

制約
・2≤T≤10^9
・1≤L,X,Y≤10^9
・1≤Q≤1000
・0≤Ei解答例

import math

t = int(input())

l, x, y = map(int,input().split())
r = l / 2

q = int(input())

p = math.pi

for i in range(q):
    e = int(input())
    # 観覧車の回転角度
    angle = 2 * p * e / t
    # e分の観覧車の位置
    ye = - r * math.sin(angle)
    ze = r - r * math.cos(angle)
    # 観覧車とXY平面上の距離
    tmp = x**2 + (y - ye)**2
    dist = pow(tmp, 0.5)
    # 俯角
    dep = math.atan2(ze, dist)

    print(math.degrees(dep))

解説
高さLの観覧車に乗ってEi分後に座標（X,Y,0）にある像を見たときの俯角を答える問題です。

T分で一周するので、スタート位置を0°とするとEi分後の回転角度はangleの式で求まります。

このときのyは-r×sin(angle)で、zはr - r×cos(angle)で求めました。

観覧車と像のxy平面上の距離をdistに求め、それを元に俯角をatanで計算します。

最後に角度を度数に戻して出力すればOKでした。

020 - Log Inequality（★3）

問題文
log2a < blog2c ですか？

制約
・1≤a≤9×10^18
・1≤b≤17
・1≤c≤13
・入力は全て整数

解答例

a, b, c = map(int,input().split())

k = pow(c, b)

if a < k:
    print("Yes")
else:
    print("No")

解説
問題文の通り大小を比較し、答える問題です。

誤差を回避するためすべて整数で処理を行います。
a < c^bを判定し、この結果にあわせて答えを出力すればACでした。

032 - AtCoder Ekiden（★3）

問題文
ABC 陸上部には N 人の駅伝選手がいます。駅伝では 1 人の選手が 1 つの区を担当して走ります。複数の選手が 1 つの区を担当することや 1 人の選手が複数の区を担当することはできません。駅伝コースは第 1 区から第 N 区まであり、選手 i が第 j 区を走るのにかかる時間は Ai,j です。

駅伝は第 1 区、第 2 区、……、第 N 区の順にその区間を担当する選手が走ります。第 j 区 (1≤j≤N−1) を走り終わった選手は第 j+1 区を走る選手にタスキを渡さなければいけません。このとき、タスキの受け渡しにかかる時間は十分短いため無視できます。最後にタスキを受けとった選手が第 N 区を走りゴールとなります。

さて、ABC 陸上部には M 個の噂があります。
i 番目の噂は「選手 Xi と選手 Yi は仲が悪い」というものです。噂をされている選手同士ではタスキの受け渡しができません。つまり、選手 Xi の直後に選手 Yi が走ることも選手 Yi の直後に選手 Xi が走ることもできません。

ABC 陸上部が駅伝でゴールするまでにかかる時間の最小値を求めてください。ただし、各選手が走る区間をどのように決めてもゴールできない場合、代わりに -1 を出力してください。

制約
・1 ≤ N ≤ 10
・1 ≤ Ai,j ≤ 1000 (1 ≤ i ≤ N , 1 ≤ j ≤ N)
・0 ≤ M ≤ N ( N − 1 ) / 2
・1 ≤ Xi < Yi ≤ N ( 1 ≤ i ≤ M )
・( Xi , Yi ) ≠ ( Xj , Yj ) ( i ≠ j )
・入力は全て整数

解答例

import itertools

n = int(input())

A = []
for i in range(n):
    array = list(map(int, input().split()))
    A.append(array)

m = int(input())

disc = [[0 for _ in range(n)] for _ in range(n)]
for i in range(m):
    x, y = map(int,input().split())
    disc[x-1][y-1] = 1
    disc[y-1][x-1] = 1

# nまでの順列を作成
per_list = list(itertools.permutations(range(n)))

ans = int(1e9)
flag = False
for i in per_list:
    tmp = 0
    for j in range(n):
        if j < n-1 and disc[i[j]][i[j+1]] == 1:
            break
        tmp += A[i[j]][j]
    else:
        ans = min(ans, tmp)
        flag = True

if flag:
    print(ans)
else:
    print(-1)

解説
N区ある駅伝の最短ゴール時間を答える問題です。

区間は10個までなので順列で走る順番を決めて、ゴールまでにかかる時間を全探索しました。

discリストには不仲の選手関係を記憶していきました。

per_listにNまでの順列のリストを作成します。
あとはper_listの要素の順番に選手が走り、各区間のタイムをtmpに足しあわせていきました。
このとき不仲リストも参照し、もし不仲な選手間が連続したら次の探索にスキップしています。

この探索結果を出力すればOKでした。

038 - Large LCM（★3）

問題文
正整数 A, B が与えられます。
A と B の最小公倍数を求めてください。ただし、答えが 10^18 を超える場合は Large と出力してください。

制約
・1≤A,B≤10^18
・入力は全て整数

解答例

import math

a, b = map(int,input().split())

ans = a * b // math.gcd(a, b)

if ans > pow(10,18):
    print("Large")
else:
    print(ans)

解説
A,Bの最小公倍数について、その値が10^18以下ならその値を、10^18を超える場合はLargeを出力する問題です。

ansに最小公倍数を計算し、10^18とansを比較して結果にあわせて答えを出力したらOKでした。

C言語とかならオーバーフローを考慮する必要があるらしいですが、Pythonなら簡単にできました。

044 - Shift and Swapping（★3）

問題文
長さ N の整数列 {An} が与えられます。以下の Q 個のクエリを順に処理してください。

・Ti=1 のとき: 数列の第 x 項 (=Ax) の値と第 y 項 (=Ay) の値を入れ替える。
・Ti=2 のとき: 数列を右方向にシフトする。すなわち、{An}=AN,A1,A2,⋯,AN−1 とする。
・Ti=3 のとき: 数列の第 x 項 (=Ax) の値を求める。

制約
・2≤N≤2×10^5
・1≤Q≤2×10^5
・1≤An≤10^9 (1≤n≤N)
・1≤Ti≤3 (1≤i≤Q)
・Ti=1 ならば 1≤xi,yi≤N かつ xi≠yi
・Ti=2 ならば xi=yi=0
・Ti=3 ならば 1≤xi≤N かつ yi=0
・入力中の値はすべて整数である

解答例

n, q = map(int,input().split())

A = list(map(int, input().split()))

shift = 0
for i in range(q):
    t, x, y = map(int,input().split())
    num_x = (x - shift - 1) % n
    num_y = (y - shift - 1) % n
    if t == 1:
        tmp = A[num_x]
        A[num_x] = A[num_y]
        A[num_y] = tmp
    elif t == 2:
        shift += 1
    elif t == 3:
        print(A[num_x])

解説
長さNの整数列Anに対してQ個のクエリを実行する問題です。

t = 2のとき、数列を右方向にシフトする必要がありますが、実際にシフトしているとTLEとなります。
したがって、シフトしなければならない量（t = 2の回数）を数えておいて、配列の参照する位置を変更するようにしました。

シフト量を考慮したときのx,yはnum_x、num_yのように求められます。
t = 1や3の場合はシフト量を考慮した値でクエリを実行することで、この問題が解けました。

046 - I Love 46（★3）

問題文
3 つの長さ N の数列 A=(A1,A2,⋯,AN),B=(B1,B2,⋯,BN),C=(C1,C2,⋯,CN) が与えられます。

Ai+Bj+Ck が 46 の倍数となるような ( i , j , k ) (1 ≤ i , j , k ≤ N) の選び方の総数を出力してください。

制約
・1≤N≤10^5
・0≤Ai,Bj,Ck≤10^9
・入力は全て整数

解答例

n = int(input())

A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A_num = [0 for _ in range(46)]
B_num = [0 for _ in range(46)]
C_num = [0 for _ in range(46)]
for i in range(n):
    tmp_A = A[i] % 46
    tmp_B = B[i] % 46
    tmp_C = C[i] % 46
    A_num[tmp_A] += 1
    B_num[tmp_B] += 1
    C_num[tmp_C] += 1

ans = 0
for i in range(len(A_num)):
    for j in range(len(B_num)):
        for k in range(len(C_num)):
            if (i+j+k) % 46 == 0:
                ans += A_num[i] * B_num[j] * C_num[k]

print(ans)

解説
Ai +Bj +Ckを46で割った余りは、Ai,Bj,Ckをそれぞれ46で割った余りの合計をさらに46で割った余りに等しくなります。

Ai,Bj,Ckをそれぞれ46で割った余りは0～45になり、この個数をA_num,B_num,C_numに記憶しておきます。

この3つの配列に対して3重ループで全探索を行いました。
i + j + k を46で割った余りが0のとき、Ai + Bj + Ckが46の倍数といえるので、その組み合わせの数A_num[i] * B_num[j] * C_num[k]を答えに足していきます。

ループを抜けたあとでansを出力すればOKでした。

048 - I will not drop out（★3）

問題文
N 問からなる試験があります。
i 番目の問題は満点が Ai 点、部分点が Bi 点です。ここで、部分点は満点より小さく満点の半分より大きいです。つまり Ai2 < Bi < Ai を満たします。

E869120 君はどの問題についても 1 分かけると部分点を取ることができ、さらに 1 分かけると満点を取ることができます。

試験時間 K 分間で E869120 君が得られる合計得点の最大値を求めてください。

制約
・1 ≤ N ≤ 2×10^5
・1 ≤ K ≤ 2N
・3 ≤ A i ≤ 10^9 ( 1 ≤ i ≤ N )
・Ai / 2 < Bi < Ai ( 1 ≤ i ≤ N )
・入力は全て整数

解答例

n, k = map(int,input().split())

score = []
for i in range(n):
    a, b = map(int,input().split())
    score.append(a-b)
    score.append(b)

score.sort(reverse=True)

ans = 0
for i in range(k):
    ans += score[i]

print(ans)

解説
K分で得られる合計得点の最大値を求めるため、部分点Biと、満点と部分点の差Ai -Biをscore配列にいれていきます。

このscoreを降順にソートして、k個の値を足し合わせれば求める答えとなりました。

部分点は満点の半分より大きいという条件があるため、Ai - BiがBiより大きいことがあり得ません。
したがって、上記のようにソートして単純に足し合わせるだけでも矛盾が起こらず、正しい答えを求めることができました。

050 - Stair Jump（★3）

問題文
E869120 君は、N 段の階段を上ろうとしています。彼は一歩で 1 段か L 段上ることができます。

0 段目から出発し、N 段目にたどり着くまでの移動方法が何通りあるかを求め、10^9+7 で割った余りを出力してください。

制約
・2≤N≤100000
・2≤L≤100000
・入力は全て整数

解答例

n, l = map(int,input().split())

dp = [0 for _ in range(n+1)]
dp[0] = 1

for i in range(n):
    if i+1 < l: dp[i+1] = dp[i]
    else:
        dp[i+1] = (dp[i] + dp[i-l+1]) % 1000000007

print(dp[n])

解説
N段の階段の登り方が何通りあるかを動的計画法で解きました。

dp[i]：i段目にいるときの登り方の組み合わせの数を更新していきます。

i+1がL段より少ないときは1段づつ登るしかありませんので、dp[i+1]はdp[i]と同じです。
それ以外のときは、i段目から1段登るか、i - l - 1段目からL段飛ばしで登る2パターンがあります。
dp[i+1]は1段登る場合のdp[i]とL段飛ばしのdp[i-l+1]を足し合わせた数になります。

上記のようにN段まで更新していくことで、求める答えが求まりました。

052 - Dice Product（★3）

問題文
N 個の 6 面体サイコロがあり、1,2,3,⋯,N と番号付けられています。サイコロ i の j (1≤j≤6) 番目の面には整数 Ai,j が書かれています。ここで、それぞれのサイコロについて、書かれている整数は相異なります。

さて、サイコロの出目に対して、次のように得点を定義します。

得点は N 個のサイコロの出目の総積である。つまり、サイコロ i の出目を Ri としたとき、得点は R1×R2×⋯×RN と計算される。

N 個のサイコロの出目の結果としては 6N 通り考えられますが、これら全てにおける得点の総和 S を 10^9+7 で割った余りを求めてください。ただし、それぞれのサイコロは互いに区別できるものとします。

制約
・1 ≤ N ≤ 100
・1 ≤ Ai,1 < Ai,2 < Ai,3 < Ai,4 < Ai,5 < Ai,6 ≤ 100
・入力はすべて整数である

解答例

n = int(input())

A_sum = []
for i in range(n):
    array = list(map(int, input().split()))
    tmp = 0
    for j in range(len(array)):
        tmp += array[j]
    A_sum.append(tmp)

ans = 1

for k in range(n):
    ans =ans * A_sum[k] % 1000000007

print(ans)

解説
N個のサイコロの出目の積を、すべての出目に対して足し合わせた結果を答える問題です。

出目は6^N通り考えられるので全探索では間に合いませんので工夫して答えを求めます。

ひとつ目のサイコロA1 = (1,2,3,4,5,6)、ふたつ目のサイコロA2 = (7,8,9,10,11,12)の場合を考えます。
A2 = 7のときの出目の積の総和は7×(1+2+3+4+5+6)、A2 = 8のとき8×(1+2+3+4+5+6)、A2 = 9のとき…となります。
これをまとめると(1+2+3+4+5+6)×(7+8+9+10+11+12)となり、A1の総和×A2の総和で答えが求まります。

Nが増えても同様に求まるので、求める得点の総和は i個目のサイコロの出目の総和を掛け合わせることで求まることがわかりました。

あとは10^9+7の余りを求めることを忘れずに計算をしていけばOKでした。

064 - Uplift（★3）

問題文
日本は N 個の区画に分けられており、西から i 番目の区画（以下、区画 i とする）の標高は Ai です。

これから Q 回の地殻変動が起こります。
i 回目の地殻変動では、区画 Li,Li+1,⋯,Ri の標高が Vi だけ変化します。（Vi≥0 のとき標高が |Vi| 上がり、Vi<0 のとき標高が |Vi| 下がることを意味します）

さて、区画 1 から N へ行く際の不便さは次のように定義されます。

区画 i の標高を Ei とするとき、不便さは

E1−E2

E2−E3

+⋯+

EN−1−EN

各地殻変動後の不便さをそれぞれ求めてください。

制約
・1≤N,Q≤10^5
・−10^9≤Ai,Vi≤10^9
・1≤Li≤Ri≤N
・入力は全て整数

解答例

n, q = map(int,input().split())

A = list(map(int, input().split()))

L = []
R = []
V = []
for i in range(q):
    l, r, v = map(int,input().split())
    l -= 1
    r -= 1
    L.append(l)
    R.append(r)
    V.append(v)

ans = 0
B = []
for i in range(n-1):
    B.append(A[i+1] - A[i])
    ans += abs(B[i])
else:
    B.append(0)

for i in range(q):
    before = abs(B[L[i]-1]) + abs(B[R[i]])
    if L[i] >= 2:
        B[L[i]-1] += V[i]
    if R[i] <= n-1:
        B[R[i]] -= V[i]
    after = abs(B[L[i]-1]) + abs(B[R[i]])

    ans += after - before

    print(ans)

解説
区画を超えるときの標高差分の総和が不便さとなる条件で、区間LからRまで標高が変わる地殻変動が起こったときの不便さを答える問題です。

地殻変動前の不便さをまずansとして求めます。
このとき、あわせて区画i+1の標高から区画iの標高を引いた値を配列Bに記録しておきました。

地殻変動が起こった場合、区間LからRまで一様に標高が変化するのでLからRまでの不便さは地殻変動前と変わりありません。
地殻変動でVだけ標高が増えたとき変化する不便さはB[L -1]がV増加するのと、B[R]がV減少するだけです。

したがって、この二つの不便さの変化量を計算して、もとの不便さから増減させることで地殻変動後の不便さを求めることができました。

069 - Colorful Blocks 2（★3）

問題文
N 個のブロックが横一列に並んでおり、左から順に 1 から N までの番号が付けられています。

これらのブロックそれぞれを、K 種類の色のうちいずれか一色で塗ることを考えます。ここで、次の条件を満たすように塗らなければなりません。

・1≤|i−j|≤2 ならば、ブロック i とブロック j に塗られている色は異なる。
・ただし、使わない色があってもよい。
このようなブロックの塗り方が何通りあるかを、10^9+7 で割った余りを出力してください。ただし、2 つのブロックの列の塗り方が異なるとは、ある 1 以上 N 以下の整数 i が存在して、ブロック i について異なる色で塗られていることとします。

制約
・1≤N≤10^18
・1≤K≤10^9
・入力は全て整数である

解答例

def Pow(a,b):
    res = 1
    while b != 0:
        if b % 2 == 1:
            res = res * a % mod
        a = a * a % mod
        b = b // 2
    return res


n, k = map(int,input().split())

mod = 10**9 + 7

if k == 1:
    if n == 1:
        print(1)
    else:
        print(0)
elif n == 1:
    print(k % mod)
elif n == 2:
    print(k*(k-1) % mod)
else:
    print(k * (k-1) % mod * Pow(k-2, n-2) % mod)

解説
N個のブロックがあり、ふたつとなりのブロックまでと同じ色で塗らないようにしたとき、色の塗り方が何通りあるか答える問題です。

K種類の色とN個のブロックについて次のように条件分けを行いました。

色が1種類だけの場合、N=1なら塗れますのでansは1です。
それ以外のNが2以上の場合なら、1種類しか色がないので条件通りに塗ることができないので0通りです。

ブロックが1個だけなら、色の種類だけ塗り方があるのでk % mod（10^9 + 7 で割った余り）通りです。

ブロックが2個なら、ひとつめのブロックはk通りの色の選び方があり、ふたつめのブロックがk-1通りの色の選び方があるので、k×(k-1) % mod 通りが答えです。

それ以外のブロックが3個以上のときは、ひとつめのブロックがk通りの色、ふたつめのブロックがk-1通りの色、3つ目以降のブロックはそれぞれk-2通りの色の選び方があります。
3つ目以降の選び方はブロックと色の数の制約が大きいため、繰り返し2乗法で積に分解して求めます。

このように求めた答えを出力すればOKでした。

075 - Magic For Balls（★3）

問題文
整数 x が書かれたボールに対し、そのボールを叩くことによって以下の操作が行われます。

・x が素数でない場合：叩かれたボールを消滅させ、整数 a が書かれたボールと整数 b が書かれたボールを追加する。a,b は ab=x かつ a≥2, b≥2 を満たす整数から自由に選ぶことができる。
・x が素数である場合：なにも起こらない。
また、魔法を 1 回使うと、現在あるすべてのボールを同時に叩くことができます。一方、魔法を使う以外の手段でボールを叩くことはできません。

さて、整数 N が書かれたボールが 1 個だけあります。あなたは何回か魔法を使うことで、すべてのボールに書かれている数を素数にしたいです。最小で何回の操作を行う必要がありますか？

制約
・2≤N≤10^12
・N は整数

解答例

N = int(input())

num = int(pow(N, 0.5))

res = 0
for i in range(2,num+1):
    while N % i == 0:
        N = N // i
        res += 1
else:
    if N != 1:
        res += 1

ans = 0
tmp = 1
while tmp < res:
    tmp *= 2
    ans += 1

print(ans)

解説
整数xを素因数分解することで、最小操作回数を求めました。

整数xの素因数を求めるときは割る値は√xを超えない整数までで十分です。
この値を超えない範囲でxを割り切れる間はずっと割り続けます。
あわせて、割った回数をresとして記録しました。

最後に2の何乗がresを超えるか計算することでansを求めて、出力すればOKでした。

079 - Two by Two（★3）

問題文
H×W の 2 次元配列 A が与えられます。あなたは以下の 2 種類の操作を好きな順番で何度でも行うことが出来ます。

・整数 x,y (1≤x制約
・2≤H,W≤100
・0≤Ai,j,Bi,j≤10^5
・入力は全て整数

解答例

h, w = map(int,input().split())

A = []
for i in range(h):
    array = list(map(int, input().split()))
    A.append(array)

B = []
for i in range(h):
    array = list(map(int, input().split()))
    B.append(array)

ans = 0
flag = True
for y in range(h):
    if flag == False:
        break
    for x in range(w):
        if x == w-1 and B[y][x] != A[y][x]:
            flag = False
            break
        elif x == w-1 and B[y][x] == A[y][x]:
            break
        elif y == h-1 and B[y][x] != A[y][x]:
            flag = False
            break
        elif y == h-1 and B[y][x] == A[y][x]:
            break
        else:
            tmp = B[y][x] - A[y][x]
            A[y][x] += tmp
            A[y+1][x] += tmp
            A[y][x+1] += tmp
            A[y+1][x+1] += tmp
            ans += abs(tmp)

if flag:
    print("Yes")
    print(ans)
else:
    print("No")

解説
H×Wのおなじサイズの2次元配列AとBが与えられます。
配列Aの縦横2マスずつの範囲の値を+1あるいは-1してBと一致させることができるか答える問題です。

( 1 , 1 )から順番にＡとＢの値を合わせていきます。
Ａ1,1をあわせたあとはA1,2、次はA1,3と順番にマス目の値をあわせました。
同時に操作した回数をansに足しあわせていきます。

あわせることができないマス目はH行目とW列目の値なので、Bと一致しているか判定しました。

この結果を最後に出力すればOKでした。

082 - Counting Numbers（★3）

問題文
何も書かれていない黒板があります。 x=L, L+1, …, R の順に、以下の操作を行います。

・黒板に、整数 x を x 回書く。
全ての操作が終了した後、黒板に書かれている文字の個数を 10^9+7 で割った余りを求めてください。

ただし、数えるのは整数ではなく文字である事に注意してください。例えば、整数 15 は 2 個の文字として数えます。

制約
・1≤L≤R≤10^18
・入力は全て整数

解答例

def cnt(x):
    res = 0
    while x > 0:
        x = x // 10
        res += 1
    return res-1

L, R = map(int,input().split())

mod = 10 ** 9 + 7

digit_L = cnt(L)
digit_R = cnt(R)

ans = 0
for i in range(digit_L,digit_R+1):
    l = max(10**i, L)
    r = min(10**(i+1)-1, R)
    tmp = ((i+1)*(r+l)*(r-l+1)//2) % mod
    ans = (ans + tmp) % mod

print(ans)

解説
LからRの間の整数において、整数xをx回、x+1をx+1回…と書いていくとき、書かれる文字の個数を答える問題です。

LとRの桁数をdigit_Lとdigit_Rとおいて、cnt関数で桁数を計算しました。

digit_Lからdigit_R+1の範囲でループさせます。
ループさせる桁で書かれる文字の数は等差数列の和で求め、ループ後にansを出力すればACでした。

084 - There are two types of characters（★3）

問題文
o と x からなる長さ N の文字列 S が与えられます。

以下の条件をすべて満たす整数の組 (l,r) の個数を求めてください。

・1 ≤ l ≤ r ≤ N
・S の l 文字目から r 文字目までの区間に、o と x 両方が含まれる

制約
・1≤N≤10^6
・S は o, x からなる長さ N の文字列である

解答例

n = int(input())

s = input()

block = []
num = 0
for i in range(n):
    num += 1
    if i < n-1 and s[i] != s[i+1]:
        block.append(num)
        num = 0
else:
    block.append(num)


tmp = 0
for i in range(len(block)):
    tmp += block[i]*(block[i]+1) // 2

ans = n*(n+1) // 2 - tmp

print(ans)