ABC 242 のA,B,C,D 問題を解くために考えたこと、ACできるPython3(PyPy3)コードを紹介します。
この記事は @u2dayo さんの記事を参考にしています。見たことのない方はそちらもご覧ください。とても勉強になります。
また、問題の難易度を表す指標を Atcoder Problems から引用しています。このサイトは勉強した問題を管理するのにとてもオススメです。
質問やご指摘はこちらまで
Twitter : Waaa1471
作者プロフィール
Atcoder ：緑色 882
20230103 現在
目次
はじめに
A.T-shirt
B.Minimize Ordering
C.1111gal password
D.ABC Transform
はじめに
特にC問題以降になると、競技プログラミングに典型的な前提知識、少し難しい数学的考察が必要になり始めます。
しかし、公式解説ではこの部分の解説があっさりしすぎていて競技プログラミング(Atcoder)を始めたばかりの人にはわかりにくい、難しいと感じるのではないでしょうか。
またC++がわからないと、コードの書き方を勉強することが難しいです。一応、参加者全員のコードを見ること自体は可能ですが、提出コードは必ずしも教育的ではありません(ここで紹介する記事も本番で提出したものとは全く異なります)。そんなものから初学者が解説もなしになにか得ることはとても難しいと思います。実際適当に何人かのコードをみたものの、意味がわからずに終わった経験があるのではないでしょうか。
この記事がそんな方々の勉強の助けになればよいなと思っています。
A.T-shirt
難易度：灰色 37
考察
いろはちゃんの順位で場合分けして考えます。
➀ 1位 ～ A位
この時何位であっても Tシャツを貰うことができるので、確率は $1$
➁ B+1位 ～ 1000位
この時何位であっても Tシャツを貰えないので、確率は $0$
③ A+1位 ～ B位
この時Tシャツを貰える順位の数は C だけあります。また、この範囲に存在する全ての順位の数は $B-A$ です。したがって、確率は $ \frac{C}{B-A}$
コード
pypy3
A,B,C,X=[int(z) for z in input().split()]
if X<=A:
print(1)
elif B+1<=X:
print(0)
else:
print(C/(B-A))
補足
なし
B.Minimize Ordering
難易度：灰色 45
考察
辞書順の定義がご丁寧に記載されていますが、この通りに実装する必要は一切ありません。sorted(S) でSを昇順にソートすれば辞書順で最小なものを求められます。
ただし、sorted() はリスト型を返すので文字列型に直す必要があります。
リストの中身を結合した文字列を作成するには join() を利用します。
コード
pypy3
S=input()
print("".join(sorted(S)))
補足
-
昇順にソート sorted()
Pythonでリストをソートするsortとsortedの違い -
文字列結合 join()
Pythonで文字列を連結・結合（+演算子、joinなど）
C.1111gal password
難易度 ： 茶色 512
考察
◦ 全ての整数 $1≤i≤N−1$ に対して、 $∣X_i −X_{i+1}∣\ ≤\ 1$
この条件より、求めるべき整数は上の桁から順番に決まっていくと考えられます。
$ N=3\ ,\ X_1=3 $ を例にして条件を満たす整数 $X$ を上の桁から順番に求めていくと図のようになります。
ここから、「今見ている桁の数字を用いて次の位の数字を求めること」 を$N$ 回繰り返すことで整数 $X$ が求められると分かりました。
また、「今見ている桁の数字を用いて次の位の数字を求めること」をより明確にすると、 これは 1 の位が $i$ となる $k$ 桁の整数 $Y_{k,i}$ が条件を満たすときに、$Y_{k+1,i-1}$ , $Y_{k+1,i}$ ,$Y_{k+1,i+1}$ も条件を満たすと定めることです。また、これらは全て $Y_{k,i}$ と同じ数だけ存在します。
ここまで得た情報を整理すると、
- 桁数
- 1 の位の値
- 個数
これらの情報で状態を定義することで、状態の遷移に忠実に全ての状態を更新させることができそうです。
状態の遷移は 動的計画法 (DP) で行うことが頻出です。また、1 ～ 2 の情報で 3 を管理すると考えると、2次元 dpテーブル (リスト) を作成することになりそうです。考えられるすべての状態を管理するためには、テーブルのサイズは $N × 10$ である必要があります。
ここで、$Y_{k,i}$ の状態から $Y_{k+1,i-1}$ , $Y_{k+1,i}$ ,$Y_{k+1,i+1}$ へ遷移することを考えると、各状態に対して 3回操作を行う可能性があります。したがって、全体で計算量は $O(3× 10 × N)$ になり十分高速です。
実装では、1 の位として 0 , 10 も含めておくことで(これに伴い、サイズを $11×N$に変更する)、1 の位が 1 , 9 の場合にも -1 , 0 , +1 の遷移を考えられるような工夫を施しています。
コード
pypy3
N=int(input())
MOD=998244353
dp=[[0 for _ in range(11)] for _ in range(N)]
# 1桁目を更新
dp[0]=[1 for _ in range(11)]
dp[0][0]=0
dp[0][-1]=0
for i in range(N-1):
# 0,10 からは状態を更新させない
for j in range(1,10):
dp[i+1][j-1]+=dp[i][j]
dp[i+1][j-1]%=MOD
dp[i+1][j]+=dp[i][j]
dp[i+1][j]%=MOD
dp[i+1][j+1]+=dp[i][j]
dp[i+1][j+1]%=MOD
print(sum(dp[-1][1:-1])%MOD)
補足
-
mod 計算
X mod(Y) = Z は X を Y で割ったときの余りが Z であることを示します。
筆者も高校で出会ったとき、なかなか理解するのに苦労した記憶があります。この動画で勉強しましょう。これは令和のスタンダードですが、数学でわからないことがあれば、まずヨビノリで調べてください。 -
動的計画法
・動的計画法ってなに？ (導入)
・典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～
こちらで動的計画法の概念を勉強することができます。
分かるようになったら、アルゴ式 1～2章で練習してみましょう
動的計画法 (DP)
D.ABC Transform
難易度： 水色 1286
考察
木を構築
$S$ の各文字を根にした木を考えると、深さ $t$ の位置に生成される文字列 と $S ^{(t)}$ は一致します。
ここで、$A→0$ , $B→1$ , $C→2$ に変換して木を構築しなおすと、左側の子の値は親の値 +1 $(mod3)$ , 右側の子の値は 親の値 -1 $(mod3)$ となることになります。
したがって、根から目的の位置 $E_{t_i,k_i}$ までの経路が分かっていれば、根の値からの増減で $E_{t_i,k_i}$ の値を求めることができそうです。
ではどうすればその経路を求められるでしょうか。
親を遡って経路を求める
もちろん根から $E_{t_i,k_i}$ までの経路を求めるために、親からどちらの子へ進めば $E_{t_i,k_i}$ に到達するかを考えることを繰り返しても良いですが、逆に、$E_{t_i,k_i}$ から根に到達するまで親を遡ることを繰り返す ことで経路を求めることにします。この方法であれば目的の経路以外を考慮する必要がなく、実装が簡単だからです。
ここで、$E_{t_i,k_i}$ の親は $E_{t_i-1,⌊\frac{K_i}{2}⌋}$ であり、そのさらに親は $E_{t_i-2,⌊\frac{K_i}{2^2}⌋}$ です。つまり、図のような経路で $E_{t_i,k_i}$ から 根 $E_{0,⌊\frac{K_i}{2^{t_i}}⌋}$ に到達できることが分かりました。
※ ⌊x⌋ は 切り捨て演算を表す
したがって、目的の $E_{t_i,k_i}$ の値は 「 $S^{0}$ の $⌊\frac{K_i}{2^{t_i}}⌋$ 番目の値 」+ 「 経路の増減値 」によって、理論的には求められる ということが分かりました。
以降、始点 $s$ から 終点 $g$ の値の増減を $f(s,g)$ で表現することにします。また、頂点の値やその増減値は 全て 3で割った余りで表現しています( mod3 の表記を省略 )。
計算量 と その改善
経路を求めることと同時に値の増減も求められます。具体的には
$E_{a,b}$ において $b$ の値が偶数なら 親からの増減は $+1$ , 奇数ならば $-1$ とすればよいです。
よって、1クエリあたりの計算量は $O(𝒕_𝒊)$ になります。( $E_{t_i,k_i}$ から $E_{0,⌊\frac{K_i}{2^{t_i}}⌋}$ へ、親を $t_i$ 回遡る必要があるから )
制約から $0 ≦ t_i ≦ 10^{18}$ なので、当然このままでは間に合いません。
どうにか、もっと少ない遡り回数に抑えられないでしょうか。
注目すべきは $k_i$ です。 制約から $k_i$ は最高でも $10^{18}$ なので、根まで遡れないような $t_i$ であっても、$E_{t_i,k_i}$ から 高々 60 回程度で 頂点 $E_{{t_i}',0}$ には到達できます。
つまり計算量 $O(log_2{t_i})$ で、目的の $E_{t_i,k_i}$ の値が以下の関係式のもと求められることになります。
$\\[0pt]$
$$
\\[0pt]「\ E_{t_i,k_i} の値 \ 」 = 「\ E_{{t_i}',0}の値 \ 」 + f(E_{{t_i}',0} , E_{t_i,k_i})\
$$
この擬似的な根 $ \ E_{{t_i}',0}$ (以降 仮の根 と呼ぶ) へは 根 $E_{0,0}$ から 左の子へ ${t_i}'$ 回進み続けることで到達できるので、
$\\[0pt]$
$$
\\[0pt]「\ E_{{t_i}',0} の値 \ 」 = 「\ E_{0,0}の値 \ 」 + t'\
$$
が成立します。
これを視覚的にイメージすると図の通りです。
これを全てのクエリで実行しても全体で $O(N log_2{t_i})$ なので、計算量を十分に改善することができました。
もちろん、${t_i}$ , ${k_i}$ 次第で直接根まで遡ることも可能ですが、この場合でも根を仮の根と同様に扱うことができるので、実装ではまとめて処理しています。
コード
pypy3
S=input()
# A→0 B→1 C→2 に変換
SS=[]
for s in S:
if s=="A":
SS.append(0)
elif s=="B":
SS.append(1)
else:
SS.append(2)
Q=int(input())
for _ in range(Q):
t,k=[int(tk) for tk in input().split()]
k-=1
tmp=0
# 仮の根まで遡って増減値を求める
while k!=0 and t>0:
if k%2==0:
tmp+=1
else:
tmp-=1
k//=2
t-=1
tmp%=3
# 仮の根の値
ans=SS[k]+t%3
# 仮の根の値 + 増減値 が答え
ans+=tmp
ans%=3
if ans==0:
print("A")
elif ans%3==1:
print("B")
else:
print("C")
補足
なし
終わり
前回、2022年内までにこの記事を出すと宣言していたので、今日からが2023年です。
今年もいっぱい見てくれよな!!!!!!!!!!!!!!!!!!