【AtCoder】 ABC237 A~C(D)問題を解いてみた

こんにちは、海月(うみつき)です。
HHKBプログラミングコンテスト2023(AtCoder237)をやったので、その話をしようと思います。

自分(初心者です)の考えを書き留め、他の人と共有し、高め合うことを目標として書いています。
(こちらの記事に書いてあるコードは最適解ではない場合がありますのでご注意ください。)

HHKB Programming Contest 2023(AtCoder Beginner Contest 327) - AtCoder

A問題(ab)

英小文字からなる長さ N の文字列 S が与えられます。
S の中で a と b が隣接する箇所があれば Yes を、なければ No を出力してください。(a と b の順序は問いません。)

• 2 ≤ N ≤ 100

• S は英小文字からなる長さ N の文字列

入力

N
S

出力
S の中で a と b が隣接する箇所があれば Yes を、なければ No を出力せよ。

考えたこと

"ab"もしくは"ba"が含まれているかを入力文字列に対して確認をすれば良いわけです。
Nをリストに入れ、「リストのi番目が'a'かつi+1番目が'b'」もしくは「リストのi番目が'b'かつi+1番目が'a'」であれば"Yes"を出力します。これらの条件に当てはまらなければ"No"を出力します。

コード

n = int(input())
s = input()

for i in range(n-1):
    if (s[i] == 'a') & (s[i+1] == 'b'):
        print("Yes")
        exit()
    if (s[i] == 'b') & (s[i+1] == 'a'):
        print("Yes")
        exit()
print("No")

B問題(A^A)

整数 B が与えられます。
A^A=B であるような正の整数 A が存在するならばその値を、存在しないならば -1 を出力してください。

• 1 ≤ B ≤ $${10^{18}}$$

• Bは整数

入力

B

出力
A^A=B であるような正の整数 A が存在するならばその値を、存在しないならば -1 を出力せよ。
A^A=B を満たす正の整数 A が複数ある場合は、どれを出力しても正解とみなされる。

考えたこと

A^Aなので、かなり大きい数ですよね。
$${3 :3^3=27}$$
$${4 :4^4=64}$$
$${5 :5^5=3125}$$
$${6 :6^6=46656}$$

(Siriに計算させました)

と、かなり大きな数になることがわかります。
今回のBの上限値が、$${10^{18}}$$なので、それに対応するくらいのAを見つければ良いかなと考えました。そのAより大きいものは考えなくて良いので。(このときのAを上限値と呼んでいます)

まぁ20くらいとかどうなん？と思って、計算させると、
$${20 :20^{20}=1.04*10^{26}}$$
で、余裕だなと思って、上限値に設定しました。20から小さくなったとしても、16とかで、計算量はほぼ変わらないかなと感じたためです。また、コード上では、一様、20とBの最小値を上限値とする形にしました。

A^A=Bなので、Aの値を1から、先ほどの上限値まで変化させて等号(=)が成立するかを確認しました。

コード

b = int(input())

for i in range(min([20,b])):
    if i**i == b:
        if i == 0:
            print(1)
            exit()
        print(i)
        exit()

print("-1")

for文では、iが0から始まっているので、$${1^1}$$ のときは i=0 のときなので注意が必要です。

C問題(Number Place)

9×9 のマス目 A があり、各マスには 1 以上 9 以下の整数が書き込まれています。
具体的には、 A の上から i 行目、左から j 列目のマスには $${A_{i,j}}$$ が書き込まれています。
A が次の条件をすべてみたしているならば Yes を、そうでないならば No を出力してください。

• A の各行について、その行に含まれる 9 マスには 1 以上 9 以下の整数がちょうど 1 個ずつ書き込まれている。

• A の各列について、その列に含まれる 9 マスには 1 以上 9 以下の整数がちょうど 1 個ずつ書き込まれている。

• A の行を上から 3 行ずつ 3 つに分け、同様に列も左から 3 列ずつ 3 つに分ける。 これによって A を 9 つの 3×3 のマス目に分けたとき、それぞれの 3×3 のマス目には 1 以上 9 以下の整数がちょうど 1 個ずつ書き込まれている。

• 1 ≤ $${A_{i,j}}$$ ≤ 9

• 入力はすべて整数

入力

$${A_{1,1}}$$ $${A_{1,2}}$$ . . . $${A_{1,9}}$$
$${A_{2,1}}$$ $${A_{2,2}}$$ . . . $${A_{2,9}}$$
.
.
.
$${A_{9,1}}$$ $${A_{9,2}}$$ . . . $${A_{9,9}}$$

出力
マス目 A が問題文の条件をすべてみたすならば Yes を、 そうでないならば No を出力せよ。

考えたこと

見たときに、いわゆるナンプレだなと。ナンプレのルールがわかっていたので、問題理解がスムーズにできたなと思っています。
入力が、2次元配列(リスト)なので、そこから、必要なものをリストに入れて、1~9の確認をしていくという流れで進めました。
行→列→各3×3マスという感じで進めました。
for分でループさせ、1行の要素9つをリストに代入、1~10までの要素で含まれていないものがないかを確認しています。
各3×3マスはナンプレ全体を9つに分け、

のように考えてコードを書いています。

コード

A = [list(map(int, input().split())) for _ in range(9)]

# A:[[1, 2], [3, 4]]

#各行
for i in range(9):
    line_lis = []
    for j in range(9):
        line_lis.append(A[i][j]) #i行の要素9つ
    for k in range(1, 10):
        if k not in line_lis:
            print("No")
            exit()

#各列
for j in range(9):
    line_column = []
    for i in range(9):
        line_column.append(A[i][j]) #j列の要素9つ
    for k in range(1, 10):
        if k not in line_column:
            print("No")
            exit()

#3*3のそれぞれの要素
A_1 = []
for i in range(3):
    for j in range(3):
        A_1.append(A[i][j])
for k in range(1, 10):
    if k not in A_1:
        print("No")
        exit()

A_2 = []
for i in range(3):
    for j in range(3):
        A_2.append(A[i][j+3])
for k in range(1, 10):
    if k not in A_2:
        print("No")
        exit()

A_3 = []
for i in range(3):
    for j in range(3):
        A_3.append(A[i][j+6])
for k in range(1, 10):
    if k not in A_3:
        print("No")
        exit()

A_4 = []
for i in range(3):
    for j in range(3):
        A_4.append(A[i+3][j])
for k in range(1, 10):
    if k not in A_4:
        print("No")
        exit()

A_5 = []
for i in range(3):
    for j in range(3):
        A_5.append(A[i+3][j+3])
for k in range(1, 10):
    if k not in A_5:
        print("No")

A_6 = []
for i in range(3):
    for j in range(3):
        A_6.append(A[i+3][j+6])
for k in range(1, 10):
    if k not in A_6:
        print("No")
        exit()

A_7 = []
for i in range(3):
    for j in range(3):
        A_7.append(A[i+6][j])
for k in range(1, 10):
    if k not in A_7:
        print("No")
        exit()

A_8 = []
for i in range(3):
    for j in range(3):
        A_8.append(A[i+6][j+3])
for k in range(1, 10):
    if k not in A_8:
        print("No")
        exit()

A_9 = []
for i in range(3):
    for j in range(3):
        A_9.append(A[i+6][j+6])
for k in range(1, 10):
    if k not in A_9:
        print("No")
        exit()



print("Yes")

3×3のマスを9つ同じようなコードを書いている時点で初心者丸出ですね。。いいやり方が思いつかなかったので諦めました。。。
たぶん、+3でループを回す(for i in range(0, 9, 3))のようなやり方だと、書く量を減らせると思います。

D問題(GoodTupleProblem)

N 以下の正整数からなる長さ M の数列の組 (S,T)=(($${S_1}$$,$${S_2}$$​,…,$${S_M}$$​),(${{T_1}$$​,$${T_2}$$​,…,$${T_M}$$​)) が 良い数列の組である とは、(S,T) が次の条件を満たすことを言います。

• 0,1 からなる長さ N の数列 X=($${X_1}$$​,$${X_2}$$​,…,$${X_N}$$​) であって次の条件を満たすものが存在する。

  • i=1,2,…,M それぞれについて、$${X_{S_i}}$$​​=$${X_{T_i}}$$​​ が成立する。

N 以下の正整数からなる長さ M の数列の組 (A,B)=(($${A_1}$$​,$${A_2}$$​,…,$${A_M}$$​),($${B_1}$$​,$${B_2}$$​,…,$${B_M}$$​)) が与えられます。(A,B) が良い数列の組である場合は Yes を、そうでない場合は No を出力してください。

入力

$${N \ M}$$
$${A_1}$$​ $${A_2}$$​  . . .  $${A_M}$$​
$${B_1}$$​ $${B_2}$$​  . . .  $${B_M}$$​

出力
(A,B) が良い数列の組である場合は Yes を、そうでない場合は No を出力せよ。

考えたこと

例1を見た後、入力例4 & 出力例4を見て、問題文を噛み砕くと
「AとBの下添字(i番目の要素)が異なるという条件でXを生成」ということだと感じました。
どういうことかというと、1( $${A_1}$$ )と、3( $${B_1}$$ ) より、Xの1番目の要素と3番目の要素は異なる値(1と0)が入っているということです。
そのようにして、Xの要素を0と1で埋めていき、矛盾が発生したら、"No"と出力すれば良いのでは？と考えました。
1つ目の要素のみを考えたときは以下の図のようになります。

Xの1番目の要素と3番目の要素が異なる値とわかったので、とりあえず0と1を適当に入れました。その他部分は空白にしておきます。
この操作を M=8となるまで進めると、

となりました。
M=3(2と7)のときは、Xの2番目の要素が、 "1"と決められているので、1と異なった数(0)を7番目の要素に入れています。その後M=4(7と2)のときは、Xの7番目の要素も2番目の要素も決定されており、異なった値が格納されているので、矛盾なしとしてスルーしています。このように、Mを最後の数まで進めていき、矛盾がなければ、"Yes"の出力で良いのでは？と考えました。

が、
1と0を適当に入れているので、「1と0」と入れるのか、「0と1」と入れるのかで違った結果となります。これを考慮していないコードが以下になります。1と0をどちらにするかは、全通り考えると良いと思ったのですが、良い方法が思いつかなかったです。Aを昇順に並び替えて、その並び替えに対応するようにBを並び替え、前から順番に進めていけばよいのかと思いましたが、わからず、諦めました。。

(AtCoder解説は、別のやり方でやっていました。)

コード(不正解ですが、)

不正解コードですが、一様載せておきます。

n, m = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

x = []
for _ in range(n+1):
    x.append(2)

for i in range(m):
    if A[i] == B[i]:
        print("No")
        exit()
    if (x[A[i]]==2) & (x[B[i]]==2):
        x[A[i]] = 1
        x[B[i]] = 0
    if (x[A[i]] != 2) & (x[B[i]] == 2):  #Aに対応したXの要素は0か1、Bは2
        x[B[i]] = abs(x[A[i]]-1)
    if (x[B[i]] != 2) & (x[A[i]] == 2):
        x[A[i]] = abs(x[B[i]]-1)
    if (x[A[i]] != 2) & (x[B[i]]!=2):
        if x[A[i]] == x[B[i]]:
            print("No")
            exit()
   
print("Yes")

最初はXを2で初期化し、その後、0と1で埋めています。そして、Mが最大になるまで矛盾なくXを埋めることができるかを確認しています。(確認不足となっていますが。)

感想とか

多くのときは、B問題まで解けて、C問題は"TLE"で終了という形が多かったですが、今回はC問題まで解けてよかったです。

毎週はできないかもしれないけれど、ABCに参加したときには、ABC解いてみた記事を更新していこうと思います。

海月でした
それでは、また〜