はじめに
問題はこちら
初心者（灰色〜茶色）向けです。
解説初挑戦ですのでお手柔らかに。
A - Same
考え方
愚直にリストの1番目と全要素が一致するかを確認し、1つでも異なる物があれば「No」を出力して終了し、そうでなければ「Yes」と解答します。
解説のように1つめとそれ以外を別変数に入れてしまった方がシンプルかと思います。
下記の方の解説のように、A_n をSetで持ってしまってその要素数で判定する、が秀逸だと思いました。
解答例
n = int(input())
an = list(map(int, input().split()))
isYes = True
a0 = an[0]
for i in range(n) :
if a0 != an[i] :
print('No')
exit()
print('Yes')
B - 3-smooth Numbers
考え方
- nが2で割り切れる間は2で割り続ける
- nが3で割り切れる間は3で割り続ける
- (１.と2.の後のn) == 1 かどうか確認する
で問題の制約上、2秒以内に実行可能です。
x = 1.で割った回数
y = 2.で割った回数
です。
下記に念のため実行回数に関する計算式を記載しておきます。
2で割る回数が高々60回程度のため、3で割る回数と合わせても120回しか計算しなくて良いです。
また、この式からもわかリますが、2^x * 3^y のパターンがそれほどないことは明らかなので、こちらの記事のように、2^x * 3^y を出し切ってしまう方針もありだと思います。
2^x \leq 10^{18}
\Leftrightarrow x \leq 18 log_2{10} \risingdotseq 59.79...
3^y \leq 10^{18}
\Leftrightarrow y \leq 18 log_3{10} \risingdotseq 37.72...
解答例
n = int(input())
while n%2 == 0 :
n = n//2
while n%3 == 0 :
n = n//3
print('Yes' if n == 1 else 'No')
C - Error Correction
考え方
T'はTから下記のように作られます。
- T′ : T
- T′ : Tのいずれか1文字を別の文字に入れ替えたもの
- T′ : Tの任意の位置(先頭、末尾を含む）に1文字追加したもの
- T′ : Tの任意の1文字を削除したもの
実は下記のように、1.の条件は 2.の条件に組み込むことができます。
2'. T′ : Tのいずれか1文字を任意の文字に入れ替えたもの
(別の文字ではなく、同じ文字を入れても良い とすれば十分）
また、3. と 4. はこの問題においては逆変換のような役割を果たします。
そのため、下記の3つを愚直に確認し、いずれかに該当すれば、等しい可能性があるものとしてカウントすれば良いと言うことになります。
2'. T : T'のいずれか1文字を任意の文字に入れ替えたもの
3. T : T'の任意の位置(先頭、末尾を含む）に1文字追加したもの
4. T : T'の任意の1文字を削除したもの
加えて、
2': T'と同じ文字列長
3 : T'の文字列長+1
4 : T'の文字列長-1
ですから、これらの長さ以外の場合は必ず答えには影響しません。
大枠の方針としては、各S_i について、
① : 長さをチェック
② ： 上記の 2', 3, 4のチェックを行う
②-1 : S_i の長さ = T'の長さ の場合
②-２ : S_i の長さ = T'の長さ+1 の場合
②-3 : S_i の長さ = T'の長さ-1 の場合
（②-4 : S_i の長さ が上記以外の場合)
として ②-1〜②-3で条件を満たすか確認します。
いずれも T'の文字列とS_iの違いの数(diffCnt)が2未満であることを確認すれば十分です。
解答例
n, tPrime = input().split()
n = int(n)
tLen = len(tPrime)
ans = []
for i in range(n) :
t = input()
if len(t) == tLen :
diffCnt = 0
for j in range(tLen) :
if tPrime[j] != t[j] :
diffCnt += 1
if diffCnt < 2 :
ans.append(i+1)
elif len(t) == tLen+1 :
diffCnt = 0
for j in range(len(t)) :
if diffCnt > 1 :
break
if diffCnt == 0 and j == len(t)-1 :
diffCnt += 1
break
if tPrime[j-diffCnt] != t[j] :
diffCnt += 1
if diffCnt < 2 :
ans.append(i+1)
elif len(t) == tLen-1 :
diffCnt = 0
for j in range(tLen):
if diffCnt > 1 :
break
if diffCnt == 0 and j == tLen-1 :
diffCnt += 1
break
if tPrime[j] != t[j-diffCnt] :
diffCnt += 1
if diffCnt < 2 :
ans.append(i+1)
print(len(ans))
print(*ans)
D - Square Permutation
考え方
Sの全ての並び替えを考えると明らかに間に合わないので、10^13までの平方数を列挙し、Sがその文字列とどれだけ一致するかを確認します。
ちなみに、全ての順列の最大値は数字全種 + 3種類だけ同じ数字2回使うパターンで下記になると思います。
13!/(2!2!2!) = 778377600 > 10^8
一方、平方数の数 と 文字列の並び替え を考えると計算量は
\sqrt{10^{13}} \times 13\log{13} = 10^6 \times \sqrt{10} \times 13\log{10} \risingdotseq 1.05444 × 10^8
ですから、下記 1. と 2. が一致することを 0 〜 10^13未満の全平方数について確認すればよいです。
- 平方数の文字列(文字列長がnになるように0埋め)をソートしたもの
- Sをソートしたもの
解答例
n = int(input())
s = input()
sList = sorted(list(str(s)))
ans = 0
tmp = 0
while tmp*tmp < 10**n :
sq = tmp*tmp
if sList == sorted(list(str(sq))+['0']*(n-len(str(sq)))) :
ans += 1
tmp += 1
print(ans)
参考文献
初作成にあたっていくつか記事を参考にしましたので記載しておきます。
類似のAtCoder(Python)の解説記事
私は足元にも及びませんが、、
数式の計算
ソートの計算量
Latex
Markdown記法
感想
先週IPAのデータベーススペシャリスト試験を受けており、前々回ぶりの参戦でした。
時間内にDのACができてよかった。直近AtCoderの練習できておらず、で、D問題あまり解けてなかったのでいい感じです。
年内入緑目指してます。
今後もアウトプット練習がてら解説記事書いていこうと思います。
よろしくお願いします。