はじめに
問題はこちら
初心者（灰色〜茶色）向けです。
A - ab
考え方
「ab」 か、「ba」の文字列があれば、「Yes」、そうでなければ「No」を返します。
Pythonには文字列検索のmethodがありますから、それを活用します。
findの詳細はこちら。
解答例
n = int(input())
s = input()
print('Yes' if s.find('ab') != -1 or s.find('ba') != -1 else 'No')
B - A^A
考え方
x^x はxが大きくなるにつれてかなり大きくなります。これは指数関数よりも大きな増加です。 B <= 10^18 で、16^16 > 10^18 のため、 Aとしてありうるのは1, 2, 3, ... , 15 の15パターンしかありません。
下記に値の表を記載します。
| $x$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ |
|---|---|---|---|---|---|---|---|
| $x^x$ | $1$ | $4$ | $27$ | $512$ | $3125$ | $46656$ | $823543$ |
| $x$ | $8$ | $9$ | $10$ | $11$ | $12$ |
|---|---|---|---|---|---|
| $x^x$ | $16777216$ | $387420489$ | $1.000 × 10^{10}$ | $2.853 × 10^{11}$ | $8.916 × 10^{12}$ |
| $x$ | $13$ | $14$ | $15$ | $16$ |
|---|---|---|---|---|
| $x^x$ | $3.029 × 10^{14}$ | $1.111 × 10^{16}$ | $4.379 × 10^{17}$ | $1.845 × 10^{19}$ |
グラフ
ですから、b と a^a が一致するかを a = 1, 2, ... , と順番に確認し、一致すれば「Yes」を出力して終了、 a^a が 10^18 を超えたらループを抜けて「No」を出力して終了すれば良いです。
解答例
b = int(input())
a = 1
while a**a < 10**18+1 :
if b == a**a :
print(a)
exit()
a+=1
print(-1)
C - Number Place
考え方
各行、各列と9個のブロック が 集合{1, 2, 3, 4, 5, 6, 7, 8, 9} と一致するかを確認して、一致しないのが一つでもあれば「No」、全て一致していれば「Yes」を出力して終了すれば良いです。
9個のブロックについては下記のように考えました。
-
各ブロックの開始位置をブロックの左上（a,b)とします。
-
開始位置から右に3列、縦に3行分の要素がブロックです。現在のマスを(a+c, b+d)とすれば、cとdはそれぞれ、0, 1, 2を動けば良いことになります。
具体的には、マス目 1列目 2列目 3列目 1行目 (a,b) (a,b+1) (a,b+2) 2行目 (a+1,b) (a+1,b+1) (a+1,b+2) 3行目 (a+2,b) (a+2,b+1) (a+2,b+2) -
開始位置の(a,b)についてはaもbも 0, 3, 6です。
具体的には、各ブロックの開始位置は下記のようになります。開始位置 1 2 3 1 (0,0) (0,3) (0,6) 2 (3,0) (3,3) (3,6) 3 (6,0) (6,3) (6,6) これをもとに例として、縦に2番目、横に3番目のブロックのマス目を列挙すると下記です。
マス目 1 2 3 1 (3,6) (3,7) (3,8) 2 (4,6) (4,7) (4,8) 3 (5,6) (5,7) (5,8)
解答例
a_ij = [input().split() for _ in range(9)]
digits = {'1','2','3','4','5','6','7','8','9'}
for k in range(9) :
if {a_ij[k][j] for j in range(9)} != digits :
print('No')
exit()
if {a_ij[i][k] for i in range(9)} != digits :
print('No')
exit()
for a in range(3) :
for b in range(3) :
if {a_ij[a*3+c][b*3+d] for c in range(3) for d in range(3)} != digits :
print('No')
exit()
print('Yes')
D - Good Tuple Problem
考え方
N個頂点のあるグラフについて、各頂点に1と0のいずれか一方を割り振ることを考えます。
点a_iと点b_iが結ばれている、と考えた時、全ての辺（つまり、i = 1, 2, ... , M)について、辺の両端が別の数値になっていれば良いです。こういったグラフは二部グラフと呼ばれます。
二部グラフは簡単にいうと、グラフの頂点をGとH(例えば、0と1を割り振る)の2グループに分けたとき、G同士、H同士には辺が存在しないようなものを指します。
与えられた入力が二部グラフであれば、各頂点の数値を順番に並べたものが、問題の説明文の良い数値の組の条件になるための数列Xになります。
また、逆に数列Xを元に頂点に数値を割り振り、a_iとb_i（i = 1, 2, ... , M)を辺で結ぶと二部グラフになります。
よって、与えられた入力に対して数列Xが存在することと、与えられた入力が二部グラフになることは同値と言えます。
二部グラフはBFSやDFSを用いて判定ができます。
実際に頂点に0と1を割り振っていき、既に数値が割り振られている頂点に対して別の数値を割り振るしかなくなったら二部グラフではないグラフ、全ての頂点に数値を割り振ることができれば二部グラフです。
二部グラフの詳細な説明は下記のリンクをご参考ください。
解答例
from collections import deque
n, m = map(int, input().split())
a_m = list(map(int, input().split()))
b_m = list(map(int, input().split()))
graph = [[] for _ in range(n)]
for i in range(m) :
graph[a_m[i]-1].append(b_m[i]-1)
graph[b_m[i]-1].append(a_m[i]-1)
color = [-1 for _ in range(n)]
ans = 'Yes'
for v in range(n) :
if color[v] != -1 :
continue
q = deque()
color[v] = 0
q.append(v)
while q :
qv = q.popleft()
for nextv in graph[qv] :
if color[nextv] != -1 :
if color[nextv] == color[qv] :
print('No')
exit()
continue
color[nextv] = 1 - color[qv]
q.append(nextv)
print('Yes')
参考文献
感想
今回Dが解けてよかったです。レートも過去最大となりました。
正直二部グラフの理解が浅かったので、今回の問題を通じ、理解できてよかったです。
D問題の解答にあたって初めてアルゴ式を見てみたのですが、とてもわかりやすく、実装例もあり勉強に良いかもと思いました。
E問題DPっぽいなと思ったものの、実装できなかったのでといてみようと思います。
問題
年内入緑目指して頑張ります。