ABC343 python Atcoderの記録

問題はこちら
4完

A

A, B = list(map(int, input().split()))
for i in range(10):
    if i != A+B:
        print(i)
        break

B
各頂点（Inputの各行）ごとにつながっている頂点（Inputが１となっているIndex）を出力

N = int(input())
for i in range(N):
    A  = [0] + list(map(int, input().split()))
    output = []
    for i in range(1, N+1):
        if A[i] == 1:
            output.append(i)
    print(*output)

C
Nの1/3乗より小さい数を順に条件を満たすか探索する

N = int(input())
# N = 10 ** 18
for i in range(int(N ** 0.333334), 0, -1):
    # print(i)
    k = i ** 3
    if k > N:
        continue # 次のfor文へ
    if str(k) == str(k)[::-1]:
        print(k)
        break

D

"""
考え方
1秒に1人の得点しか変わらないため、出力は3通り（前回の値と同じ、前回の値±1）
得点の変更前と変更後の値、その人数を管理することで高速に回答できる
"""
N, T = list(map(int, input().split()))
# N, T = [2*10**5, 2*10**5]
list_score = [0 for _ in range(N)]
result = [] # 各秒の結果をまとめて後で出力する
dict_summary = {0:N} # Key:得点、Value:人数
counter_0 = 0 # dict_summaryで値が0の要素がいくつあるかを管理する
for t in range(T):
    A, B = list(map(int, input().split()))
    # A, B = [1, 10**9]
    score_before = list_score[A-1] # 変更前の得点
    score_after = score_before + B # 変更後の得点
    list_score[A-1] = score_after # 得点リストの更新
    # 
    dict_summary[score_before] -= 1 # 変更前の得点の人数を一人減らす
    if dict_summary[score_before] == 0:
        counter_0 += 1
    try:
        dict_summary[score_after] += 1
        if dict_summary[score_after] == 1:
            counter_0 -= 1
    except KeyError:
        dict_summary[score_after] = 1
    result.append(len(dict_summary) - counter_0)

    # result.append(len(set(list_score)))
    # print(list_score)
print('\n'.join(map(str, result)))

E

F

ABC342 python Atcoderの記録

問題はこちら
3完

A
時間を使ってしまった

from collections import Counter
S = list(input())
# 例としてCounter型を作成
my_counter = Counter(S)

# 値が1であるキーを取得
keys_with_value_one = [key for key, value in my_counter.items() if value == 1]
# print(keys_with_value_one)
for i in range(len(S)):
    if S[i] == keys_with_value_one[0]:
        print(1+i)

B

N = int(input())
P = [0] + list(map(int, input().split()))
Q = int(input())
#
for q in range(Q):
    A,B = list(map(int, input().split()))
    id_A = [idx for idx, value in enumerate(P) if value == A][0] 
    id_B = [idx for idx, value in enumerate(P) if value == B][0]
    # print(id_A, id_B)
    print(P[min(id_A, id_B)])

C

import string
N = int(input())
S = input()
Q = int(input())
#変換前のアルファベットa~z
alphabet_before = string.ascii_lowercase
#変換後のアルファベットa~z
alphabet_after =  string.ascii_lowercase
for _ in range(Q):
    c,d = list(input().split())
    alphabet_after = alphabet_after.replace(c,d)
dict_alphabet = {alphabet_before[i] : alphabet_after[i] for i in range(len(alphabet_before))}
# 与えられた文字列を1種類ずつ変換
result = ""
for s in S:
    result += dict_alphabet[s]
print(result)

D

E

F

ARC171 python Atcoderの記録

問題はこちら
1完

A
まずは条件を整理する。
ルーク・ポーンの配置条件を図示すると下記のようになる。

ルークのほうが配置時の駒の制限が大きいため、ルークをA個置いた時にポーンの最大配置可能数を計算し、その値とBを比較することで判定ができそうである。
そのためどのようにおくと効率的かを考える。
まずはルークとポーンどちらかの駒だけを置くとき、それぞれが最大でいくつ置けるかを考える。
ルークの最大配置数は行数と等しい。

ポーンの最大配置数は下記のようにNの偶奇で異なる。

よって両方の駒を配置するとき、ルークは偶数行におくと効率が良いことがわかる（1行目にポーンを置きたい＆i行目にポーンを置くとi-1行目に駒は置けないため）。

あとはルークの数がN/2より多いか少ないかで場合分けを行う必要があることに注意する。

T = int(input())
# ルークがあるとき、同列・同行に駒がない
# ポーンがあるとき、1つ上のマスに駒がない→同じ列にポーンは1つだけ
for _ in range(T):
    N, A, B  = list(map(int, input().split())) # Aがルーク、Bがポーン
    diff = N-A # 行数-ルークの数
    flag = "No"
    if diff < 0 : # ルークのほうが多いとNo
        pass
    if 0 <= diff <= N/2: # ポーンをすべての奇数行に配置できる
        max_B = diff**2
        if max_B >= B:
            flag = "Yes"
    if N/2 < diff: # ポーンを置けない奇数行がある
        max_B = diff*(N//2 + N%2)
        if max_B >= B:
            flag = "Yes"
    print(flag)

B

C

D

E

F

ABC339 python Atcoderの記録

問題はこちら
3完

A
"."で分割して最後の要素を出力する。

S = input().split(".")
print(S[-1])

B
愚直に実装。回転の表し方でもっと良い方法がないか知りたい。

H, W, N = list(map(int, input().split()))
grid = [["."] * W for _ in range(H)]
#
h,w = [0,0]
d = 0 # 0が上向き、90が右向き。180が下向き、270が左向き
for n in range(N):
    # print(n)
    if grid[h][w] == ".":
        grid[h][w] = "#"
        d = (d+90) % 360 # 360を超えないようにする
        if d == 0:
            h,w = [(h-1)%H,(w)%W] # インデックスについても同様
        if d == 90:
            h,w = [(h)%H,(w+1)%W]
        if d == 180:
            h,w = [(h+1)%H,(w)%W]
        if d == 270:
            h,w = [(h)%H,(w-1)%W]
            
    else:
        grid[h][w] = "."
        d = (d-90) % 360
        if d == 0:
            h,w = [(h-1)%H,(w)%W]
        if d == 90:
            h,w = [(h)%H,(w+1)%W]
        if d == 180:
            h,w = [(h+1)%H,(w)%W]
        if d == 270:
            h,w = [(h)%H,(w-1)%W]

# output
for i in range(H):
    print("".join(grid[i]))

C
満たすべき条件は、i回目の乗降後の乗客が0以上。
最初の乗客を0人と仮定したときのi回目の乗降後の乗客を計算する。
その最小値がマイナスのとき、最初の乗客が少なくともその人数だけいる必要がある。
また最終的な乗客人数は、最初の乗客＋累計乗客（与えられたA1～ANの和）である。

N = int(input())
A = list(map(int, input().split()))
min_person = 0 # 最初の人数を0人としたとき、最も少ない乗客人数。
diff_person = 0 # 最初の人数を0人としたとき、i回目の乗客の乗り降り後に何人乗っているか。
for i in range(N):
    diff_person += A[i]
    min_person = min(min_person, diff_person)
# print(min_person, diff_person)
print(diff_person-min_person)

D
追記予定

E

F

ARC170 python Atcoderの記録

問題はこちら
1完

A
文字列SとTを前から順番に比較していくと、AをBに変えたいときとBをAに変えたいときがある。
それぞれ考えられる操作は、2通りずつ。
1．AをBに変えたいとき
1-1．変えたい場所より左のBをAに変えて、AをBに変える
1-2．変えたい場所より左のAをAに変えて、AをBに変える

2．BをAに変えたいとき
2-1．BをAに変えて、変えたい場所より右にあるAをBに変える
2-2．BをAに変えて、変えたい場所より右にあるBをBに変える

最も操作回数が少なくなるのは、1-1と2-1をまとめて行えるときであるため、1．AをBに変えたいとき（A2B）と2．BをAに変えたいとき（B2A）の回数をカウントする。

またAをBに変えたいときより前にAが存在するか、つまりS[i]、T[i]がどちらもAであるときorBをAに変換するときがあるかの情報が必要である（Can_A2B）。

同様にBをAに変えたいときより後にBが存在するか、つまりS[i]、T[i]がどちらもBであるときorAをBに変換するときがあるかの情報が必要である（Can_B2A）。

N = int(input())
S = input()
T = input()

B2A = 0
A2B = 0
Can_A2B = 0
Can_B2A = 0
n_operatinons = 0

for i in range(N):
    if S[i] == T[i] == "A":
        Can_A2B = 1
    elif S[i] == T[i] == "B":
        Can_B2A = 1
    elif S[i] == "A" and T[i] == "B":
        # A2B +=1
        # B2Aがあればマイナス１し、n_ope =+1
        if B2A > 0:
            B2A -= 1
            n_operatinons += 1
            Can_B2A = 1
        elif Can_A2B == 1:
            n_operatinons += 1
            Can_B2A = 1
        else:
            n_operatinons = -1
            break
            
    elif S[i] == "B" and T[i] == "A":
        B2A +=1
        Can_B2A = 0 # 初期化
        Can_A2B = 1
# 残ったB2Aの処理
if Can_B2A == 1:
    n_operatinons += B2A
elif Can_B2A == 0  and B2A > 0:
    n_operatinons = -1
# print(S,T,n_operatinons)
print(n_operatinons)

ABC337 python Atcoderの記録

問題はこちら
3完（バーチャル参加）

A

N = int(input())
x,y = [0,0]
# 結果の集計
for i in range(N):
    xi, yi = list(map(int, input().split()))
    x += xi
    y += yi
# 勝者の判断
result = ""
if x > y :
    result = "Takahashi"
elif x < y :
    result = "Aoki"
else:
    result = "Draw"
print(result)

B

import re

def remove_consecutive_chars(input_str):
    # 正規表現を使って連続する文字を検出し、1つに置き換える
    result_str = re.sub(r'(.)\1+', r'\1', input_str)
    return result_str

S = input()
S_duplicated = remove_consecutive_chars(S)
# print(S_duplicated)
list_answer = ["ABC","BC","AC","AB","A","B","C"]
if S_duplicated in list_answer:
    print("Yes")
else:
    print("No")

C
リストAの要素から、インデックスを取得することで人の順番を追える。

N = int(input())
A = [0] + list(map(int, input().split()))
dict_order = {}
for i in range(N+1):
    dict_order[A[i]] = i
#
ind = -1
for _ in range(N):
    ind = dict_order[ind]
    print(str(ind), end = " ")

D
愚直に描いてTLE
累積和を使う発想がなかった

H, W, K = map(int, input().split())
S = [input() for _ in range(H)]

min_action = float('inf')
# 累積和を計算する関数
def calc_prefix_sum(s):
    """
    input: 文字列
    output:辞書（要素はリスト）
    sample: "o.xo.x"→{"o":[1,1,1,2,2,2], ".":[0,1,1,1,2,2], "x":[0,0,1,1,1,2]}
    """
    
    # 辞書の初期化
    result_dict = {char: [0] * len(s) for char in ["o", ".", "x"]}

    # 初期値の設定
    for char in result_dict:
        result_dict[char][0] = int(s[0] == char)

    # 累積和の計算
    for i in range(1, len(s)):
        for char in result_dict:
            result_dict[char][i] = result_dict[char][i - 1] + int(s[i] == char)

    # 末尾に0を追加する（インデックスがー1の時に0を返したいため）
    for char in result_dict:
        result_dict[char].append(0)

    return result_dict

# 行ごとにチェック
for i in range(H):
    row = S[i]
    # 累積和でo.xの数を計算する
    prefix_sum = calc_prefix_sum(row)
    # print(prefix_sum)
    for j in range(W - K + 1):
        n_o = prefix_sum["o"][j+K-1] - prefix_sum["o"][j-1]
        n_dot = prefix_sum["."][j+K-1] - prefix_sum["."][j-1]
        n_x = prefix_sum["x"][j+K-1] - prefix_sum["x"][j-1]
        # print(i, j, n_o, n_dot, n_x)
        
        if n_x > 0: # 文字の範囲内にxがあれば、min_actionは更新しない
            pass
        else: # xがなければ.の数をmin_actionとして更新する
            min_action = min(min_action, n_dot)
        
# 転置して再度行ごとにチェックする
t_S = list(map(''.join, zip(*S)))
# print(t_S)
# 行ごとにチェック
for i in range(W):
    row = t_S[i]
    # 累積和でo.xの数を計算する
    prefix_sum = calc_prefix_sum(row)
    # print(prefix_sum)
    for j in range(H - K + 1):
        n_o = prefix_sum["o"][j+K-1] - prefix_sum["o"][j-1]
        n_dot = prefix_sum["."][j+K-1] - prefix_sum["."][j-1]
        n_x = prefix_sum["x"][j+K-1] - prefix_sum["x"][j-1]
        # print(i, j, n_o, n_dot, n_x)
        
        if n_x > 0: # 文字の範囲内にxがあれば、min_actionは更新しない
            pass
        else: # xがなければ.の数をmin_actionとして更新する
            min_action = min(min_action, n_dot)
# 出力
if min_action == float('inf'):
    print(-1)
else:
    print(min_action)

E
必要な友人はlog2(N)人（適当に拾ってきた考えt型のサイト

1000本の毒入りワインの論理パズル - 優雅に華麗に大胆に！(FGO攻略ブログ)

）。
ジュースの番号を2進数で表し、そのi桁目が1であるジュースをi番目の友人に飲んでもらう。
その結果を10進数に直すことで、どのジュースが悪いか特定できる。
あとはジュースの本数が２のべき乗であるときの処理を気を付ける

import math
N = int(input())

def binary_representation(n, m):
    # 1~nをm桁の2進数で表すリストを返す関数
    result = []
    for i in range(1, n+1):
        binary_str = format(i, '0' + str(m) + 'b')
        if len(binary_str) <= m:
            result.append(binary_str)
        else:
            result.append("0"*m)
    return result

def find_indices_with_one(lst, n):
    # 各2進数の上からN桁目を取得し、それが1であればインデックスを返す
    result_indices = [index for index, element in enumerate(lst) if element[n-1] == '1']
    return result_indices


n_friends = math.ceil(math.log2(N)) # 最小の友人数
# 飲料bin(i)の上からj桁目が1であれば、友人jはそのドリンクを飲む
print(n_friends) # 最小の友人



# 飲料1~Nをn_friends桁の2進数で表す
result_list = ["0"*n_friends] + binary_representation(N,n_friends)
# print(result_list)
# 飲むドリンクを返す
for i in range(1, n_friends+1):
    drinked = find_indices_with_one(result_list, i)
    print(len(drinked), end = " ")
    print(*drinked)
    # print(*find_indices_with_one(result_list, 1))
# returnを受け取り2進数を10進数に直して出力
answer = int(input(), 2)
if answer ==0:
    answer = 2**n_friends
print(answer)

F

ABC336 python Atcoderの記録

問題はこちら
3完

A
"o"がN個並んだ文字列は、 N * "o"　と書ける。

N = int(input())
print("L" + N * "o" + "ng")

B
2進数に変換する関数はbin。
その後、右側にある0の個数を数える方法を考えればよい。
末尾から0であるかの判定をしていく方法でもよい。

N = int(input())
def count_trailing_zeros(string):
    # 右側の0の文字数　＝　全体の文字数 - 右から0を取り除いた後の文字数
    return len(string) - len(string.rstrip('0')) 
    #　MEMO
    #  rstrip : 文字列の右側（末尾）から指定された文字を取り除くメソッド
    #  lstrip という文字列の左側（先頭）から指定された文字を取り除くメソッドもある
print(count_trailing_zeros(str(bin(N))))

C
問題文の"良い整数"（10進数で表記したときに、0，2，4，8のみが出現する）は5つの文字だけで10進数を表していることから、5進数で考えた後に各位の数を2倍にすればよいと思った。
1番小さい5進数は0（５）、2番目に小さい5進数は1（５）だから、N番目に小さい5進数はN-1（５）である。
よってN-1（５）を求め、各位の数値を倍にすればよい。
自画自賛だが、うまく発想できたと思う。

N = int(input())
def to_base_5(n):
    # 5進数に変換する関数
    result = ''
    while n > 0:
        n, remainder = divmod(n, 5)
        result = str(remainder) + result
    return '0' if result == '' else result
str_Quinary = to_base_5(N-1)
print(int(str_Quinary)*2)

D
Cを早めに解けて調子に乗ったが、Dがわからず。
後で追記します。

E

F