Pythonで取り組む 競プロ典型 90 問 #星2
競技プログラミングの実力アップのためE869129さんが企画された競プロ典型90問に取り組みました。
難易度が★の数で表示されており、AtCoderのC問題レベルの★2問題をPythonで解きました。
競プロ典型90問の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
- 004 - Cross Sum(★2)
- 010 - Score Sum Queries(★2)
- 022 - Cubic Cake(★2)
- 024 - Select +/- One(★2)
- 027 - Sign Up Requests (★2)
- 033 - Not Too Bright(★2)
- 055 - Select 5(★2)
- 061 - Deck(★2)
- 067 - Base 8 to 9(★2)
- 078 - Easy Graph Problem(★2)
004 - Cross Sum(★2)
問題文
H 行 W 列のマス目があります。上から i (1≤i≤H) 行目、左から j (1≤j≤W) 列目にあるマス (i,j) には、整数 Ai,j が書かれています。 すべてのマス (i,j) (1≤i≤H,1≤j≤W) について、以下の値を求めてください。
・マス (i,j) と同じ行または同じ列にあるマス(自分自身を含む)に書かれている整数をすべて合計した値
制約
・2≤H,W≤2000
・1≤Ai,j≤99
・入力は全て整数
解答例
h, w = map(int,input().split()) A = [] for i in range(h): array = list(map(int, input().split())) A.append(array) row = [] col = [] # 行の合計 for i in range(h): tmp = 0 for j in range(w): tmp += A[i][j] row.append(tmp) # 列の合計 for j in range(w): tmp = 0 for i in range(h): tmp += A[i][j] col.append(tmp) # Bijの計算 for i in range(h): B = [] for j in range(w): num = row[i] + col[j] - A[i][j] B.append(str(num)) ans = " ".join(B) print(ans)
解説
H行W列のマス目があり、すべてのマスにおいて次の値を答える問題です。
・マス(i , j)と同じ行と列のマスに書かれている整数の合計
行のリストrowを用意して、i行目のすべてのマスに書かれた数字を足し合わせ値を追加していきます。
同様に列のリストcolも作成し、j列目の数字を足し合わせ、その値を追加しました。
row[i]とcol[j]を足すと、A[i][j]が2回足されることになるのでrow[i] + col[j] - A[i][j]の値がBijとなります。
このBijの計算を2重ループで各マス目で行い、出力するとOKでした。
010 - Score Sum Queries(★2)
問題文
ABC 大学には N 人の一年生が在籍しています。クラスは 2 つあり、学籍番号 i 番の生徒のクラスは Ci 組です。今日は期末試験が返却され、学籍番号 i 番の生徒の点数は Pi 点でした。
以下の形式の質問が Q 個与えられます。
j=1,2,…,Q それぞれについて答えてください。
・学籍番号 Lj∼Rj 番の 1 組生徒における、期末試験点数の合計
・学籍番号 Lj∼Rj 番の 2 組生徒における、期末試験点数の合計
・これら 2 つの値をそれぞれ求めよ。
制約
・1≤N≤100000
・1≤Ci≤2
・0≤Pi≤100
・1≤Q≤100000
・1≤Lj≤Rj≤N
・入力は全て整数
解答例
n = int(input()) C = [] P = [] for i in range(n): c, p = map(int,input().split()) C.append(c) P.append(p) q = int(input()) L = [] R = [] for i in range(q): l, r = map(int,input().split()) L.append(l-1) R.append(r) tmp1 = 0 tmp2 = 0 sum_score = [[0, 0]] for i in range(n): if C[i] == 1: tmp1 += P[i] else: tmp2 += P[i] sum_score.append([tmp1, tmp2]) for k in range(q): A = sum_score[R[k]][0] - sum_score[L[k]][0] B = sum_score[R[k]][1] - sum_score[L[k]][1] print(str(A) + " " + str(B))
解説
Q個のクエリで与えられる学籍番号の範囲において、1組・2組生徒の合計点をそれぞれ答える問題です。
累積和を用いて解きました。
sum_socreにはi+1番目の生徒までの1組および2組の点数の累積和をtmp1、tmp2として追加していきました。
与えられたクエリごとに学籍番号LからRまでの合計得点をsum_score[R[k]]○ - sum_score[L[k]]○で求め出力していけばOKでした。
022 - Cubic Cake(★2)
問題文
幅 A、奥行き B、高さ C の直方体の形をしたケーキがあります。
あなたはケーキに対して、次の操作を行うことができます。
・ある面に平行な方向に切断する
・ただし、ケーキは動かしてはならない(複数のケーキに分割されている場合、これらを変形したり、別々に切ることはできない)
最小何回の操作で、全てのピースを立方体にすることができますか?
制約
・1≤A,B,C≤10^18
・入力はすべて整数
解答例
import math a, b, c = map(int,input().split()) tmp = math.gcd(a, math.gcd(b, c)) ans = (a + b + c) // tmp - 3 print(ans)
解説
直方体のケーキを何回切るとすべて同じ大きさの立方体にすることができるか答える問題です。
最小の操作回数で同じ大きさの立方体になるには、A,B,Cの最大公約数の大きさに切りそろえる必要があります。
tmpにA,B,Cの最大公約数を計算します。
切る回数はA + B + Cをtmpで割り、さらに3を引いた値です。
この値をansとして、ansを出力すればOKでした。
024 - Select +/- One(★2)
問題文
長さ N の正整数列 A=(A1,A2,…,AN) および B=(B1,B2,…,BN) が与えられます。
次の操作をちょうど K 回行うことで A を B に一致させることができるか判定してください。
操作:1≤i≤N を満たす i をひとつ選び Ai を Ai−1 または Ai+1 に置き換える
制約
・1≤N≤1000
・1≤K≤10^9
・1≤Ai,Bi≤10^6 (1≤i≤N)
・入力は全て整数
解答例
n, k = map(int,input().split()) A = list(map(int, input().split())) B = list(map(int, input().split())) diff = 0 for i in range(n): diff += abs(A[i] - B[i]) flag = True if diff > k: flag = False elif (diff - k) % 2 == 1: flag = False if flag: print("Yes") else: print("No")
解説
問題文の操作をちょうどK回行うことで数列Aを数列Bに一致させることができるか答える問題です。
数列AとBの各要素の差をdiffとして計算しました。
AをBに一致させるには少なくともdiff 回は操作しないといけないことがわかります。
AをBに一致させることができるかどうかをflagで管理します。
diffがkより大きい場合は先に述べたように一致させることはできないのでFalseとしました。
また、diff - k の値が奇数のときはちょうどk回の操作で一致させることができません。(どんなに近づけても必ず1だけ異なります)
したがってdiff - k が奇数のときもFalseとしました。
最後にflagにあわせて答えを出力してACでした。
027 - Sign Up Requests (★2)
問題文
低橋くんはプログラミングコンテストサイト「LowCoder」を作り、サービスを開始しました。
今日の時点では、LowCoder にはユーザはいません。
今日から数えて i (1≤i≤N) 日後には、ユーザ名 Si を希望するユーザが登録申請を行います。
申請を行った時点でユーザ名が Si であるユーザが存在する場合、その登録申請は無視されます。
そのようなユーザが存在しない場合は登録申請が受理され、LowCoder にそのユーザが登録されます。
何日目の登録申請が受理されるかを求めてください
制約
・1≤N≤10^5
・Si (1≤i≤N) は英小文字および数字からなる 1 文字以上 15 文字以下の文字列である。
より正確には、Si は正規表現 [a-z0-9]{1,15} で表せる文字列である。
解答例
n = int(input()) S = [] for i in range(n): s = input() S.append(s) user = set() for i in range(n): tmp1 = len(user) user.add(S[i]) tmp2 = len(user) if tmp1 != tmp2: print(i+1)
解説
i日目にユーザ名Siを希望するユーザが登録申請を行うとき、同じユーザ名が登録されてなければ登録できます。
何日目の登録が受理されるか答える問題です。
setのデータ構造を用いて解くことができました。
setは重複しない要素の集まりになるので i日目のユーザ名Siを追加してもsetの要素数が変化しない場合は、すでに登録されていることがわかります。
変化する場合は登録できるユーザ名なので、登録した日数であるi + 1を出力すればOKです。
033 - Not Too Bright(★2)
問題文
E869120 くんは、冬に公開するイルミネーションを作成することを計画しています。
E869120 くんが計画しているイルミネーションは、縦 H × 横 W の HW 個のLEDで構成されます。
イルミネーションの各 LED は、点灯・消灯の状態を任意に切り替えることができます。
このイルミネーションは、以下の条件を満たすとき 不適切である といいます。
・イルミネーション全体に完全に含まれる 縦 2 × 横 2 の、4 つの LED を含む領域であって、点灯している LED が領域内に 2 つ以上あるものが存在する。
適切な(不適切な状態ではない)イルミネーションの点灯パターンのうち、点灯している LED の個数としてありうる最大値を求めてください。
制約
・1≤H,W≤100
・入力はすべて整数
解答例
h, w = map(int,input().split()) ans = 0 if h == 1 or w == 1: ans = h * w else: ans = ((h+1) // 2) * ((w+1) // 2) print(ans)
解説
縦2×横2マスのなかで1つしかLEDを点灯させないことを条件とするとき、最大で何個のLEDを点灯させることができるか答える問題です。
マス目(i , j )についてi , jが奇数のときにLEDを点灯させることが最適なので((h+1) // 2) * ((w+1) // 2)が答えとなります。
ただし、HあるいはWが1のとき縦2×横2マスがとれないので、すべてのマスを点灯させても不適切とならないコーナーケースになります。
したがって、コーナーケースのときと、それ以外で計算式を変えてansを計算してACでした。
055 - Select 5(★2)
問題文
N 個の整数 A1, A2, ⋯, AN があります。 この中から 5 個を選ぶ方法のうち、これら 5 個の整数の積を P で割ると Q 余るようなものが何通りあるか求めてください。
制約
・5 ≤ N ≤ 100
・0 ≤ Ai ≤ 10^9
・0 ≤ Q < P ≤ 10^9
・入力はすべて整数
解答例
n, p, q = map(int,input().split()) A = list(map(int, input().split())) ans = 0 for i in range(n-4): for j in range(i+1,n-3): for k in range(j+1,n-2): for l in range(k+1,n-1): for m in range(l+1,n): if A[i] * A[j]%p * A[k]%p * A[l]%p * A[m]%p == q: ans += 1 print(ans)
解説
N個の整数から5個選び、この積をPで割ったときにQ余る組み合わせの数を答える問題です。
単純に5重ループで全探索を行うことでACできました。
詳しい説明ができませんが…
N^5では間に合いそうにありませんが、定数倍が軽いため間に合うようです。
組み合わせの数をansに格納し、ループ後に出力すればOKです。
061 - Deck(★2)
問題文
あなたはカードを整理するために 1 つの山札を作ります。 最初、山札にカードは 1 枚もありません。
これから Q 個の操作を行います。i 番目 (1≤i≤Q) の操作では以下を行います:
・ti=1 のとき、整数 xi が書かれたカードを山札の一番上にいれる
・ti=2 のとき、整数 xi が書かれたカードを山札の一番下にいれる
・ti=3 のとき、山札の上から xi 番目のカードに書かれた数を紙に書き出す
ti=3 の操作で書き出された整数を操作順に出力するプログラムを書いてください。
制約
・2≤Q≤10^5
・1≤ti≤3
・ti=1,2 のとき 1≤xi≤10^9
・ti=3 のとき 1≤xi≤ki(ki は 1≤j≤i かつ tj=1,2 を満たす j の個数)
・ti=1,2 を満たす i が少なくとも 1 つ存在する
・ti=3 を満たす i が少なくとも 1 つ存在する
・与えられる入力は全て整数
解答例
import collections q = int(input()) T = [] X = [] for i in range(q): t, x = map(int,input().split()) T.append(t) X.append(x) cards = collections.deque() for i in range(q): if T[i] == 1: cards.appendleft(X[i]) elif T[i] == 2: cards.append(X[i]) else: print(cards[X[i]-1])
解説
ti = 1のときは山札の一番上に、ti = 2のときは一番下にカードをいれて、ti = 3のとき上からxi番目のカードを答える問題です。
山札はdequeを用いて管理しました。
ti が1のときはdequeの左端に、tiが2のときは右端にxiを記録します。
tiが3のとき、dequeの左端が山札の一番上になりますのでX[i] -1番目の要素を出力すればACでした。
067 - Base 8 to 9(★2)
問題文
黒板に 8 進法の整数 N が書かれています。あなたは以下の操作を K 回行います。
・黒板の整数を 9 進法に直し、ここに現れる数字「 8 」を「 5 」に書き直す(書き直した後の数は 8 進数とみなされる)
操作を K 回行った後にできる数を 8 進法で出力してください。
制約
・0≤N<8^20
・1≤K≤100
・N は 8 進法で表される整数
・N の先頭に余分な 0 を含まない
・K は整数
解答例
def base10to(n, b): if n // b: return base10to(n // b, b) + str(n % b) return str(n % b) n, k = map(int,input().split()) num = str(n) for i in range(k): base_10 = int(num, 8) base_9 = str(base10to(base_10, 9)) num = "" for j in range(len(base_9)): if base_9[j] == "8": num += "5" else: num += base_9[j] print(num)
解説
8進数の値を9進数に直し、そのとき現れた「8」を「5」に書き換える操作をK回繰り返したあとでできる値を答える問題です。
まず、8進数を10進数base_10に変換します。
つぎに10進数base_10を9進数base_9に変換します。
このbase_9を1文字づつ確認していき、「8」がでたときは5を、それ以外の数字はそのままnumに格納していきます。
この操作をk回繰り返した後でnumを出力すれば求める答えとなりました。
078 - Easy Graph Problem(★2)
問題文
N 頂点 M 辺の連結な単純無向グラフが与えられます。グラフの頂点には、それぞれ 1 から N までの番号が振られています。 i 番目の辺は、頂点 ai と bi を双方向に結んでいます。
以下の条件を満たす頂点の個数はいくつあるか出力してください。
・自分自身より頂点番号が小さい隣接頂点がちょうど 1 つ存在する
制約
・2≤N≤100000
・N−1≤M≤min(N(N−1)2,100000)
・1≤ai,bi≤N
・与えられるグラフは単純グラフである
・与えられるグラフは連結である
・入力はすべて整数で与えられる
解答例
n, m = map(int,input().split()) list = [[] for _ in range(n)] for i in range(m): a, b = map(int,input().split()) list[a-1].append(b-1) list[b-1].append(a-1) ans = 0 for i in range(n): tmp = 0 for j in list[i]: if i > j: tmp += 1 if tmp == 1: ans += 1 print(ans)
解説
問題文の通り、自分自身の頂点番号より小さい隣接頂点がちょうど1つの頂点の数を答える問題です。
辺で結ばれた隣接リストlistにai、biを記録していきます。
つぎに各頂点をfor文で調べていきます。
自分自身の頂点番号より小さい隣接頂点の数をtmpとしました。
隣接リストから自身の頂点番号 i より隣接頂点番号 j が小さいときtmpに1を足していきます。
最後にtmpがちょうど1であればansに1を足し、ループを抜けた後にansを出力すればOKです。
以上が★2の問題解答例でした。
コンテストでも取りこぼしなく解けるように精進していきたいです。
競技プログラミングの学習にはこちらの本もおすすめです。