A - Yay!
概要:文字列の中で唯一違う文字が先頭から何番目か出力してね
開始前に配点表みてA問題なのに配点150点でビビり散らかしてました。
文字列の長さが100なので制約は厳しくなく、1文字しかない文字が何かさえ分かれば文字列のindex()演算子で答えが出せます。
私は文字をkeyとした度数分布numを作成して、num[key] = 1であることから問題の文字を特定しました。
出力時に1-indexedに戻すことを忘れずに。
#ABC342 A - Yay!
from collections import Counter
S = input()
num = Counter(S)
#print(num)
for key in num:
if num[key] == 1:
print(S.index(key)+1)
これを入力例3に対して実行すると以下の出力が得られます(コメントアウトしている部分も有効化しています)
zzzzzwz #入力
Counter({'z': 6, 'w': 1}) #度数分布
6 #1-indexedしたS.index(w)の結果出力
提出リンク:提出 #50560688 - HUAWEI Programming Contest 2024(AtCoder Beginner Contest 342)
B - Which is ahead?
リンク:B - Which is ahead? (atcoder.jp)
概要:人が配列の順番で並んでいます。さんとさんを比べて前にいる人を回出力してね
、なので毎回index(A)とindex(B)の大小比較しても通りそうな気がしましたが、念のため計算量かかるindexではなくで出せるように工夫しました。
#ABC342 B - Which is ahead?
from collections import defaultdict
N = int(input())
P = list(map(int, input().split()))
num = defaultdict(int)
for i in range(N):
num[P[i]] = i
#print(num)
Q = int(input())
for _ in range(Q):
A, B = map(int, input().split())
a = num[A]
b = num[B]
if a < b:
print(A
)
else:
print(B)
これを入力例1に対して実行すると以下の出力が得られます(コメントアウトしている部分も有効化しています)
3 #入力N
2 1 3 #入力P
defaultdict(<class 'int'>, {2: 0, 1: 1, 3: 2}) #人をkeyとして並び順を保有するdict
3 #入力Q
2 3 #クエリ1
2 #Aのほうが前なので2を出力
2 3 #クエリ2
2 #Aのほうが前なので2を出力
1 3 #クエリ3
1 #Aのほうが前なので1を出力
提出リンク:提出 #50572209 - HUAWEI Programming Contest 2024(AtCoder Beginner Contest 342)
69msec
ちなみにdictを使わず普通に書いたコードは以下です。
72msecでACできています。
#ABC342 B - Which is ahead?
N = int(input())
P = list(map(int, input().split()))
Q = int(input())
for _ in range(Q):
A, B = map(int, input().split())
if P.index(A) < P.index(B):
print(A)
else:
print(B)
提出リンク:提出 #50613654 - HUAWEI Programming Contest 2024(AtCoder Beginner Contest 342)
C - Many Replacement
リンク:C - Many Replacement (atcoder.jp)
概要:文字列の中でに該当する文字をに書き換える操作を回行った最終的な文字列を出力してね
、なので計算量に気を付けないといけません。
またpythonでは文字列の一部置換が出来ないので別で答え出力用の配列を作成する必要があります。
を都度操作していると間に合わなそうに感じたので、アルファベット小文字のa~zを並べた文字列をさらにunicodeに変換した配列を準備し、これについて回の書き換え操作をすることにしました。
unicodeへの変換はord()演算子で、a=97、b=98、・・・という風に順番に数字が割り振られています。
数字から文字に戻すときはchr()演算子です。
書き換え箇所の参照にindex()演算子を使用していますが高々26回の計算なのでクエリの処理に、最後に文字列を出力するのになのでトータルの計算量はだと思います。
#ABC342 C - Many Replacement
N = int(input())
S = input()
Q = int(input())
ab = [97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122]
for i in range(Q):
c, d = map(str, input().split())
for j in range(len(ab)):
if ab[j] == ord(c):
ab[j] = ord(d)
#print(ab)
s = [0] * N
for i in range(N):
s[i] = chr(ab[ord(S[i])-97])
print(*s, sep = '')
これを入力例1に対して実行すると以下の出力が得られます(コメントアウトしている部分も有効化しています)
7 #入力N
atcoder #入力S
4 #入力Q
r a #クエリ1
t e #クエリ2
d v #クエリ3
a r #クエリ4
[114, 98, 99, 118, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 97, 115, 101, 117, 118, 119, 120, 121, 122] #['r', 'b', 'c', 'v', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'a', 's', 'e', 'u', 'v', 'w', 'x', 'y', 'z']に書き換え
recovea #t→e,d→vに書き換えた文字列
提出リンク:提出 #50593350 - HUAWEI Programming Contest 2024(AtCoder Beginner Contest 342)
D - Square Pair
リンク:D - Square Pair (atcoder.jp)
概要:配列の各要素を掛け算した数字が平方数になる組み合わせ数を出力してね
なので愚直にをして都度平方数の判定をしていてはTLEになります(なりました)。
を素因数分解してと足したときに各因数の数がすべて偶数だったらいいのかなぁ等考えていましたが高速に処理できる方法が思いつかず。
公式解説が天才すぎる。競技プログラミングあるところまで行くと数学みたいになる。
結果
以上3完でした。
C問題ACが53minで個人的には大満足の結果でした。
レートもようやく338まで上がり茶色が見えてきました。
年度内に色変したい。
(内部レートはABC339くらいから継続して茶色なので茶色コーダー名乗っていいですか?ダメ?はい・・・)