ABC327,A~D問題の解説
A問題 ab
単純な全探索で通ります。
Pythonの自分のコード
n=int(input()) s=list(input()) check=0 for i in range(n-1): hako=s[i]+s[i+1] if hako=="ab" or hako=="ba": check=1 break if check==1: print("Yes") else: print("No")
C++の自分のコード
#include <bits/stdc++.h> using namespace std; int main() { int n; string s; int check=0; cin >> n; cin >> s; for (int i=0;i<n-1;i++){ if (s[i]=='a' && s[i+1]=='b' || s[i]=='b' && s[i+1]=='a'){ check=1; break; } } if (check==0){ cout << "No" << endl; } else{ cout << "Yes" << endl; } return 0; }
B問題 A^A
これもまた全探索で通ります。
C++を使っている人はオーバーフローに気をつけなくてはいけないようです。
Pythonの自分のコード
b=int(input()) check=0 for i in range(1,10000000000): hako=i count=1 for ipp in range(hako): count*=hako if count==b: check=1 break elif count>b: break if check==1: print(hako) else: print("-1")
C問題 Number Place
めんどくさい問題ですね。
頑張って実装しましょう。
愚直なコードで通ります。
Pythonの自分のコード
rotti=[[]*1 for i in range(9)] for i in range(9): rotti[i]=list(map(int,input().split())) check=0 #縦 for i in range(9): irane=set() for ipp in range(9): irane.add(rotti[ipp][i]) if len(irane)!=9: check=1 #横 for i in range(9): irane=set() for ipp in range(9): irane.add(rotti[i][ipp]) if len(irane)!=9: check=1 #それぞれのます irane=set() for i in range(9): for ipp in range(3): irane.add(rotti[ipp][i]) if (i+1)%3==0: if len(irane)!=9: check=1 irane=set() #まんなか irane=set() for i in range(9): for ipp in range(3,6): irane.add(rotti[ipp][i]) if (i+1)%3==0: if len(irane)!=9: check=1 irane=set() #いちばんした irane=set() for i in range(9): for ipp in range(6,9): irane.add(rotti[ipp][i]) if (i+1)%3==0: if len(irane)!=9: check=1 irane=set() if check==0: print("Yes") else: print("No")
D問題 Good Tuple Problem
これは典型の問題です。
UnionFindなり、幅優先探索なりを使うと解けます。
簡単に説明すると、まず1つ目の要素を0だと仮定する。
→1つ目の要素と関係がある要素をチェックしていって、その要素を1と置く。
…これを繰り返して矛盾が生じだらNo、生じなかったらYesを出力すればいいです。
Pythonの自分のコード
n,m=map(int,input().split()) rotti=[[]*1 for i in range(n)] a=list(map(int,input().split())) b=list(map(int,input().split())) for i in range(m): if a[i]==b[i]: print("No") exit() for i in range(m): rotti[a[i]-1].append(b[i]) rotti[b[i]-1].append(a[i]) x=[-1]*n irane=set() check=0 for i in range(n): if i+1 in irane: continue irane.add(i+1) stack=[[i+1,0]] x[i]=0 iti=0 while len(stack)>iti: hako=stack[iti][0] if stack[iti][1]==0: count=1 else: count=0 for ipp in range(len(rotti[hako-1])): if rotti[hako-1][ipp] in irane: continue x[rotti[hako-1][ipp]-1]=count stack.append([rotti[hako-1][ipp],count]) irane.add(rotti[hako-1][ipp]) iti+=1 for ipp in range(len(stack)): hako=stack[ipp][0] for k in range(len(rotti[hako-1])): if x[rotti[hako-1][k]-1]==x[hako-1]: check=1 break if check==1: print("No") else: print("Yes")
最後までありがとうございました。
どうでもいいけど、ここのページにのっている自分のコードでほっとんど効果ないよね…?(ま、いっか)