どうもこんにちは！
5月3日のAtCoderのコンテストに参加しましたので記録します。
今回はAのみ完答。BよりCの方が解けそうと思って取り組みましたが解ききれず。
問題
問題は以下のリンクから。完答できたAと途中までやったB,Cを振り返ります。
A - Not Found -
25文字以下の英小文字列のうち、この文字列に含まれない文字をひとつ出力するという問題。含まれない文字が2個以上ある場合はいずれか1つを出力すればOKとしています。
シンプルに、aからzの英小文字の列を用意して、for文で含まれない文字が見つかったら出力するという形で実装しました。
s = input()
c = 'abcdefghijklmnopqrstuvwxyz'
for i in c:
if i not in s:
print(i)
break
B - Grid Rotation -
N行N列の配列で構成するグリッドが2つ与えられるので、一方のグリッドを加工して一致させるのに最小で何回の操作が必要かを出力する問題。グリッドに対してできる加工は以下の2つ。
1. グリッドの任意の1マスの値を変更する
2. グリッドを90°右回転させる
回転しないのであれば、2つのグリッドを比較して異なっているマスの数が必要回数です。同様に回転してからグリッドを比較すれば回転した場合の必要回数もわかります。問題はグリッドをどうやったら回転させられるかで、方法が思いつかず断念しました。
さて、解説によると配列の回転は下記の1行でできるようです。調べてみると過去にまとめている人がいて、まず*S[::-1]で配列を上下逆にして、次にzip関数で上下逆にした配列を転置したら回転した状態になるとのこと。なるほど。
list(zip(*S[::-1]))
これらを踏まえて以下のコードを作ったら完答となりました。
n=int(input())
s = [list(input()) for _ in range(n)]
t = [list(input()) for _ in range(n)]
ans = 10000000000
for i in range(4): # iは回転の回数
count = i
# グリッドの差異の個数をカウント
for j in range(n):
for k in range(n):
if s[j][k] != t[j][k]:
count += 1
# sを回転
ans = min(ans,count)
s = list(zip(*s[::-1]))
print(ans)
C - Cycle Graph? -
与えられたN頂点M辺の単純無向グラフがサイクルグラフか否かを判定して出力する問題。サイクルグラフは全部の辺と頂点で1つの輪っかとなるようなグラフというイメージです。頂点や辺の最大数は$2 × 10^5$個で、計算量を考えないといけないC問題の定番ですね。
輪っかのようになるということは、1つの頂点につながる辺は2個なので、少なくともそれ以外の頂点があるグラフはサイクルグラフではないとなります。これを満たしたうえで、あと何を満たせばよいかわからず断念。なお解説によると、これは想定される間違いの1つとのこと。もう1つの条件が連結であることで、これら2つの条件を満たすかはDFSやBFS、Union-Findを使って判定できるということでした。
おわりに
過去問を解いてないためと思いますが、問題のバリエーション多くてなかなか安定した成績を残せないところです。まぁ落ち着いてやっていきたいと思います。
ではでは。