ABC393(AtCoder Beginners Contest 393)
A〜E問題をPythonで解いてみました。
- コードは雑めです。ゆるしてー
- 競技プログラミングの勉強一切したこと無いので、テクニックは知らないよ。ごめんねー
A問題(diff=10)
s1, s2 = input().split()
def solve():
if s1 == s2 == "fine":
print(4)
elif s1 == s2 == "sick":
print(1)
elif s1 == "sick":
print(2)
else:
print(3)
solve()
- 脳死で愚直に解きました
- 1は二人とも食べてるので、sick sickなら1
- 2は高橋くんだけ食べてるので、sick fine なら2
- 3は青木くんだけ食べてるので、fine sick なら3
- 4は二人とも食べてないので、fine fine なら4
B問題(diff=44)
S = input()
def solve():
toukankaku = 0
A_start = 0
while True:
A_find = S[A_start:].find('A')
if A_find < 0:
break
A_find += A_start
B_start = A_find + 1
while True:
B_find = S[B_start:].find('B')
if B_find < 0:
break
B_find += B_start
C_find = B_find + (B_find - A_find)
if C_find >= len(S):
break
if S[C_find] == 'C':
toukankaku += 1
B_start = B_find + 1
A_start = A_find + 1
print(toukankaku)
solve()
- こちらも愚直に解きました
- Aの位置を見つけて、そこからBまでの距離をつかって、B+(B-A)の位置にCがあればペアが完成します
- スライス→findは使わない方がだいぶ高速ですんで、その点はおすすめしません。pypy選んで1文字ずつ調べたほうが速いです
C問題(diff=188)
N,M = map(int,input().split())
def solve():
array = [[] for i in range(N+1)]
#print("len(array)={}".format(len(array)))
sakujo = 0
try:
for i in range(M):
mu1, mu2 = map(int,input().split())
if mu1 == mu2:
sakujo += 1
elif mu1 < mu2:
array[mu1].append(mu2)
else:
array[mu2].append(mu1)
except IndexError as ie:
print("mu1={}, mu2={}".format(mu1,mu2))
print(ie)
for i in range(N):
if len(array[i]) > 0:
set_i = set(array[i])
if len(set_i) < len(array[i]):
sakujo += (len(array[i])-len(set_i))
print(sakujo)
try:
solve()
except IndexError as ie:
print(ie)
- まず、同じ頂点を結んでいる無向グラフは削除します（カウント対象にします）
- ペアが同じ無向グラフはソートして追加すれば良い。以下で追加すればOK
- mu1がmu2 よりも小さい場合、array[mu1].append(mu2)
- mu1がmu2 よりも大きい場合、array[mu2].append(mu1)
- 各muごとにsetを作って、元のlistとの長さを比較すれば削除カウントに加算する値がわかります
- try ～ exceptはIndexErrorが出た時に書いたものなので、削除しても大丈夫です（消しとけって話ですがｗ）
別解
- コンテスト中にも思いついたのですがlistで取得→ソート→tupleにしてsetに格納、全体の差分を取って解答でも行けます
- tupleで判定できるのは知っていたのですが、普段使ったことがなかったので、怖気づきました。次は使います
N,M = map(int,input().split())
set1 = set()
for _ in range(M):
mu = list(map(int,input().split()))
if mu[0] != mu[1]:
set1.add(tuple(sorted(mu)))
print(M-len(set1))
D問題(diff=533)
N = int(input())
S = input()
def solve():
array = []
A_start = 0
for i in range(len(S)):
if S[i] == '1':
array.append(i)
#print("array={}".format(array))
center_index = len(array)//2
center = array[len(array)//2]
result = 0
for i in range(len(array)):
a_i = array[i]
result += abs(center-a_i)-abs(center_index-i)
print(result)
solve()
-
解法として、1の場所を順番に見ていったときに中央にある1を動かさずに周りの1を寄せる方法を思いつきました
- 入力例1の方法なのですが、この手法が全てにおいて言えることなのか確信が持てずに居ました
- 手元のノートで以下を確認して、この手法で進めることにしました
- 中央以外に寄せたケースでは回数が増えてしまう
- 1の数が偶数の時の中央はどちらでも同じ結果になる
-
方針が定まればプログラムするだけなので、上記の通りに書いていきます
- 1の位置を全てarrayに格納
- 中央の1の位置を取得
- 全ての1の位置をループして、中央との差分を集計
E問題(diff=1253)
提出コード ※時間外
- こちらは解法は思い浮かぶもののTLEが出てしまうものばかりでコンテスト中は間に合わずです
- 勉強のために解いている方のコードを写経して、まずはざっくり理解しました
N,K = map(int,input().split())
A = list(map(int,input().split()))
# bigM = 1200000
bigM = 1000000 # N<10^6 だったので改めた
def solve():
# 全てのA_iに対してカウントする配列を作る。計算量はO(N)
arr1 = [0]*(bigM+1)
for a_i in A:
arr1[a_i] += 1
# 全てのA_iの約数に対してカウントする配列を作る。計算量はO(N log N)
arr2 = [0]*(bigM+1)
arr2[1] = N # 1 は全てのA_iの約数のため
for p in range(2,bigM+1):
for q in range(1,bigM+1):
if p * q > bigM:
break
arr2[p] += arr1[p * q] # pを約数とする数をarr2に取得
# １～bigM までの組み合わせの数がarr2に入っているので、その数がK以上であれば使えるとしてarr3に約数を格納していく。計算量はO(N log N)
arr3 = [1]*(bigM+1) # この配列には約数が入るのだが、全ての整数は1を約数とするため、1を入れておく。
for p in range(2,bigM+1):
for q in range(1,bigM+1):
if p * q > bigM:
break
if arr2[p] >= K: # K回以上使用している場合
arr3[p * q] = p # p*qの約数としてpを代入。同じ数字(p*q)の約数としては後の値が優先される
# 求まった約数を出力する
for a in A:
print(arr3[a])
solve()
- 解説はコードに書いてあるコメントを読んだ方が良いと思います
感想
-
学生さん向け（まぁHugkunやってるしね）
- A～Cは学生エンジニアとしてアルバイトしたい方など、プログラム練習中の方にはわりと丁度いい問題かと
- 冷静に問題を読んで、アルゴリズムを書けば解ける問題かと思います
- 個人的にはDも解けて欲しい問題ですね（そんなに難しくないと思います）
-
個人のリハビリ的にはE解きたいですね（最近コード書いてないんで劣化が激しい）