はじめに
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回の筆者の成績(oooooxx)
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
- 解説で示したD問題の提出
- 解説で示したE問題の提出
- 解説で示したF問題の提出
補足
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
A問題
- 最初が仲間外れのパターンだけ例外処理をする．
- Sは3以上なので，Sは0，1，2でアクセスしても問題無い．
A.py
"""
<方針>
- 最初が仲間外れのパターンだけ例外処理をする．
- Sは3以上なので，Sは0，1，2でアクセスしても問題無い．
"""
# 標準入力受け取り
S = input()
### 最初の文字が仲間外れのパターン
# 最初と2文字目が違って，2文字目と3文字目が仲間のとき
if(S[0] != S[1] and S[1] == S[2]):
# 最初の文字が仲間外れ
print(1)
# 今すぐ終了して，下のコードを実行させない．
exit()
### 最初の文字が多数派のパターン
# それぞれの文字で試す．
for i in range(len(S)):
# 最初の文字と異なっている文字を見つけたとき，
if(S[0] != S[i]):
# 現在0初めで見ているので，1足したものを出力．
print(i+1)
# このbreakはしてもしなくても結果は変わらない(はず)．
break
B問題
- NもQも100なので，愚直にQ毎にNのfor文を回す．
- AとBを受け取ったときに，毎回printして出力している．
B.py
"""
<方針>
- NもQも100なので，愚直にQ毎にNのfor文を回す．
- AとBを受け取ったときに，毎回printして出力している．
"""
# 標準入力受け取り
N = int(input())
P = list(map(int, input().split()))
Q = int(input())
for i in range(Q):
# 標準入力受け取り(問題文におけるA,Bを，a,bと表現しています．)
a, b = map(int, input().split())
# aI, bIがそれぞれ，a, bの左からの順番である．
for i in range(N):
if(P[i] == a):
aI = i
if(P[i] == b):
bI = i
# aの方が左にあるとき
if(aI<bI):
print(a)
# bの方が左にあるとき
else:
print(b)
C問題
- 英小文字を数値で表現するために，ord()/chr()を使用する．(必ずしも数値で表現する必要は無い(と思う))
- 毎回英小文字を変換していては，O(NQ)になってしまい，TLEになってしまう．
- それぞれの英小文字が最終的に何に変化するかを保持する配列を作ることで，O(N+Q)にする．
- 最後にその配列を元に文字を変換する．
- 文字列の+=のオーダーがO(N^2)になるかと思ってビビったため，配列のappendを採用している．
C.py
"""
<方針>
- 英小文字を数値で表現するために，ord()/chr()を使用する．(必ずしも数値で表現する必要は無い(と思う))
- 毎回英小文字を変換していては，O(NQ)になってしまい，TLEになってしまう．
- それぞれの英小文字が最終的に何に変化するかを保持する配列を作ることで，O(N+Q)にする．
- 最後にその配列を元に文字を変換する．
- 文字列の+=のオーダーがO(N^2)になるかと思ってビビったため，配列のappendを採用している．
"""
N = int(input())
S = input()
Q = int(input())
# 26種類の英小文字が最終的に何に変化するかを記録する配列．
# i番目の配列にアクセスすると，最終的にどの数値に変化するかが参照できる．
# 最初はi番目には同じ値「i」が格納されている．
alps = [i for i in range(26)]
# 英小文字の変換配列(alps)をどんどん更新していく．
for i in range(Q):
c, d = input().split()
# cとdを数値で表現したものをcI,dIとする．
cI = ord(c) - ord("a")
dI = ord(d) - ord("a")
# alpsにアクセスして，現在値がcIとなっているところ全てをdIに変換する．
for j in range(26):
if(alps[j] == cI):
alps[j] = dI
# 変換後の文字列を一度配列に格納する．
ans = []
for i in range(N):
# 元々の文字
orig = S[i]
# 変換後の文字(数値表現)
ansInt = alps[ord(orig) - ord("a")]
# 英小文字に変換しつつ，その文字を変換後の配列に格納する．
ans.append(chr(ansInt+ord('a')))
# 配列を区切り文字無しで出力
print(*ans, sep="")
D問題
D.py
"""
<方針>
- Aの中で積をとったときに平方数になるためには，Aの中の値それぞれを素因数分解したものを考える(2^i*3^j*5*k*...)．
- 上記の素因数分解したものの指数部分(i, j, k...)を2で割ったものを新しい配列(B)にしても答えに影響はしない．
- その新しい配列(B)の中で同じ値になっているもの同士では必ず平方数になり，違う値では必ず平方数にならない．
- ただし，値が0のものに関しては誰とでも平方数になれることに注意して実装する．
"""
"""
参考記事
https://qiita.com/snow67675476/items/e87ddb9285e27ea555f8
上記に書いてあったコードを元に，素因数分解した結果，その素因数の個数が奇数であるものの積を出力する関数．を作成しました．
"""
def fac(n):
ans = 1
arr = []
temp = n
for i in range(2, int(-(-n**0.5//1))+1):
if temp%i==0:
cnt=0
while temp%i==0:
cnt+=1
temp //= i
arr.append([i, cnt])
if(cnt%2==1):
ans *= i
if temp!=1:
arr.append([temp, 1])
ans *= temp
if arr==[]:
arr.append([n, 1])
ans *= n
return ans
N = int(input())
A = list(map(int, input().split()))
# 指数部分を2で割ったものの配列
B = []
for i in range(N):
a = A[i]
B.append(fac(a))
# 同じものがどのくらいあるかをカウントしてくれる便利なライブラリ
import collections
C = collections.Counter(B)
ans = 0
for k, v in C.items():
# 0のときは自分以外の誰とでも平方数になれるので，例外処理
if(k==0):
# 初項:N-1
# 末項:N-v
# 項数:v
# 上記の条件における等差数列の和を考える．
ans += (((2*N) - v - 1)*v)//2
else:
if(v!=1):
# v個のものから2個取る組み合わせ(vC2)となる．
ans += (v*(v-1))//2
print(ans)
E問題
- 問題文の意訳：それぞれの駅において，N番目の駅への終電の時間を求める問題である．
- 最も終電が遅いところ(始点はN番目の駅)から，ダイクストラ法で行く．
- heapqを用いているため，最小の値を出力する関係で，終電の時間にマイナスをつけている．
E.py
"""
<説明>
- 問題文の意訳：それぞれの駅において，N番目の駅への終電の時間を求める問題である．
- 最も終電が遅いところ(始点はN番目の駅)から，ダイクストラ法で行く．
- heapqを用いているため，最小の値を出力する関係で，終電の時間にマイナスをつけている．
"""
import heapq
N, M = map(int, input().split())
INF = float("inf")
# 終電の時間にマイナスをつけたもので初期化．
revFinal = [-(-INF) for i in range(N)]
# N-1番目(0-index)は終電は無い．無限時間後もN-1番目の駅はN-1番目の駅に到着できる．
revFinal[N-1] = -INF
# 0-indexにしつつ，A出発のB到着に対して，有向辺は逆にBからAへ出す．
Edges = [[] for i in range(N)]
for i in range(M):
data = list(map(int, input().split()))
l, d, k, c, A, B = data
A -=1
B-=1
Edges[B].append([l, d, k, c, A, B])
# ダイクストラで回る頂点集合
nodeName = []
# N-1番目の駅は無限時間後もN-1番目の駅に到着できる．
heapq.heappush(nodeName, [-INF, N-1])
# ダイクストラ開始
while nodeName:
# 終電が遅い駅origを取得する．
revCost, orig = heapq.heappop(nodeName)
# その駅への電車がある駅でループを回す．
for nex in Edges[orig]:
l, d, k, c, A, B = nex
# A駅の終電の時間とする．
temp = -1
# 駅orig(B駅)における終電
cost = -revCost
# A駅の最後の電車に乗っても間に合う時
if(l+d*(k-1)<cost-c):
temp = l+d*(k-1)
# 流石にA駅の最後の電車では間に合わない時
else:
# A駅最初の駅でもB駅に行って，N-1番目の駅に行けない時
if(cost-c-l<0):
# 更新できない．
continue
# A駅から行けて，終電に間に合うギリギリの時間を取得
else:
temp = ((cost-c-l)//d)*d + l
# 終電の時間をマイナスに反転させてます．
revTemp = -temp
# もっと遅い終電が見つかったとき
if(revTemp < revFinal[A]):
# 更新
revFinal[A] = revTemp
heapq.heappush(nodeName, [revTemp, A])
# 答え出力
for i in range(N-1):
if(revFinal[i] == INF):
print("Unreachable")
else:
print(-revFinal[i])
F問題
- 公式解説通りです(多分)．一応公式解説におけるp, q, rの個人的補足．
- pは「ディーラー」であるyがiになる確率．すなわち，y<Lである間はサイコロを回すので，i<Lは0になるはず．
- qは「あなた」がx=iという状況になったときに(つまりこの段階にたどり着くための確率は考慮しない)，そのままサイコロを回さないでいたときに勝利をする確率．
- rは「あなた」がx=iという状況になったときに(つまりこの段階にたどり着くための確率は考慮しない)，サイコロを振るor振らないに関する最適な行動をとったときに勝利をする確率．
F.py
"""
<説明>
- 公式解説通りです(多分)．一応公式解説におけるp, q, rの個人的補足．
- pは「ディーラー」であるyがiになる確率．すなわち，y<Lである間はサイコロを回すので，i<Lは0になるはず．
- qは「あなた」がx=iという状況になったときに(つまりこの段階にたどり着くための確率は考慮しない)，そのままサイコロを回さないでいたときに勝利をする確率．
- rは「あなた」がx=iという状況になったときに(つまりこの段階にたどり着くための確率は考慮しない)，サイコロを振るor振らないに関する最適な行動をとったときに勝利をする確率．
"""
N, L, D = map(int, input().split())
# y=iになる確率
p = [0]*(L+D)
# x=iで終わって勝利する確率
q = [0]*(N+1)
# x=iの時の勝率
r = [0]*(N+1)
### pを求める．
p[0] = 1
gety = 0
for i in range(L+D-1):
if(i<L):
gety += p[i]
if(i-D>=0):
gety -= (p[i-D])
p[i+1] = gety/D
p[:L] = [0]*L
### qを求める．
dead = 0
if(N+1<=L+D):
dead = sum(p[N+1:L+D])
for i in range(N+1):
q[i] = dead
if(i<L+D):
dead += p[i]
### rを求める．
other = 0
for i in range(N, -1, -1):
r[i] = max(q[i], other/D)
other += (r[i])
if(i+D<=N):
other -= (r[i+D])
### 出力
print(r[0])