ABC141 E - Who Says a Pun?
【問題文】
文字列が与えられて、部分文字列として重ならずに 2 回以上現れるもののうち、最長のもの
【考え方】
Zアルゴリズムで解けるらしいけど、解説動画を見てDPで解いた。
過去に確認した値を用いて計算する。
n=int(input()) s=list(input()) dp=[[0]*n for _ in range(n)] ans=0 for i in range(n-1,-1,-1): for j in range(i-1,-1,-1): if s[i]==s[j]: if i==n-1: dp[i][j]=1 else: dp[i][j]=min(i-j,dp[i+1][j+1]+1) else: dp[i][j]=0 ans=max(ans,dp[i][j]) print(ans)
保有資格（未登録含む）
合格した資格試験です。
資格コラムの執筆や、資格取得支援を副業でやってみたいです。
保有資格一覧
| No | 区分 | 資格名 | 備考 |
| 1 | 情報処理技術者試験 | ITパスポート | |
| 2 | 情報セキュリティマネジメント | ||
| 3 | 基本情報技術者 | ||
| 4 | 応用情報技術者 | ||
| 5 | ネットワークスペシャリスト | ||
| 6 | 情報セキュリティスペシャリスト | ||
| 7 | データベーススペシャリスト | ||
| 8 | エンベデッドシステムスペシャリスト | ||
| 9 | ITストラテジスト | ||
| 10 | プロジェクトマネージャ | ||
| 11 | システムアーキテクト | ||
| 12 | ITサービスマネージャ | ||
| 13 | システム監査技術者 | ||
| 14 | 情報処理安全確保支援士試験 | 情報処理安全確保支援士 | |
| 15 | 中小企業診断士 | 未登録 | |
| 16 | PMP | ||
| 17 | 技術士 | 情報工学部門 | 未登録 |
| 18 | 総合技術監理部門 | 未登録 | |
| 19 | 電気通信主任技術者 | 線路 | |
| 20 | 伝送交換 | ||
| 21 | 工事担任者 | AI・DD総合種 | |
| 22 | 第一級陸上無線技術士 | ||
| 23 | IPTPC認定 VoIPアドバイザ | ||
| 24 | ISC2 | CISSP | |
| 25 | CCSP | 未登録 | |
| 26 | ISACA | CISA | 未登録 |
| 27 | CISM | 未登録 | |
| 28 | CompTIA | CloudEssential | |
| 29 | Cysa+ | ||
| 30 | CCSP+ | ||
| 31 | AWS Certificate | AWS Certified Cloud Practitioner | |
| 32 | AWS Certified Machine Learning - Specialty | ||
| 33 | AWS Certified Data Analytics - Specialty | ||
| 34 | AWS Certified Database - Specialty | ||
| 35 | AWS Certified DevOps Engineer - Professional | ||
| 36 | AWS Certified SysOps Administrator - Associate | ||
| 37 | AWS Certified Solutions Architect - Professional | ||
| 38 | AWS Certified Security - Specialty | ||
| 39 | AWS Certified Advanced Networking - Specialty | ||
| 40 | AWS Certified Developer - Associate | ||
| 41 | AWS Certified Solutions Architect - Associate | ||
| 42 | メンタルヘルスケアマネジメント | Ⅰ種（マスターコース） | |
| 43 | Ⅱ種（ラインケアコース） | ||
| 44 | Azure Certificate | Azure AI Fundamentals | |
| 45 | Azure Data Fundamentals | ||
| 46 | Azure Security, Compliance, and Identity Fundamentals | ||
| 47 | Azure Fundamentals | ||
| 48 | G検定 | ||
| 49 | 日商簿記 | 2級 | |
| 50 | 統計検定 | 3級 | |
| 51 | ITIL | Foundation | |
| 52 | MCPC | モバイルシステム技術検定2級 | |
| 53 | モバイルシステム技術検定1級 | ||
| 54 | シニアモバイルコンサルタント | ||
| 55 | IoTシステム技術検定中級 | ||
| 56 | IoTシステム技術検定上級 | ||
| 57 | MCPCスマートフォン・モバイル実務検定 | ||
| 58 | ビジネス著作権検定 | 上級 | |
| 59 | .com Master Adv. | ★★ | |
| 60 | 個人情報保護士 | 失効 | |
| 61 | EXIN Foundation Certificate in OpenStack Software | ||
| 62 | 危険物 | 乙4 | |
ABC235 E - MST + 1
■問題
最小全域木を構成する辺かどうかを調べる
■考え方
クラスカル法を用いて最小全域木を求める。
クラスカル法は、「コストが最小」かつ「閉路を作らない」辺を順番に追加していく方法。
閉路かどうかの判断にはUnionFindを利用しており、下記サイトのコードを利用している。
PythonでのUnion-Find（素集合データ構造）の実装と使い方 | note.nkmk.me
import sys sys.setrecursionlimit(10**8) n,m,q=map(int,input().split()) class UnionFind(): def __init__(self, n): self.n = n self.parents = [-1] * n def find(self, x): if self.parents[x] < 0: return x else: self.parents[x] = self.find(self.parents[x]) return self.parents[x] def union(self, x, y): x = self.find(x) y = self.find(y) if x == y: return if self.parents[x] > self.parents[y]: x, y = y, x self.parents[x] += self.parents[y] self.parents[y] = x def size(self, x): return -self.parents[self.find(x)] def same(self, x, y): return self.find(x) == self.find(y) def members(self, x): root = self.find(x) return [i for i in range(self.n) if self.find(i) == root] def roots(self): return [i for i, x in enumerate(self.parents) if x < 0] def group_count(self): return len(self.roots()) def all_group_members(self): return {r: self.members(r) for r in self.roots()} def __str__(self): return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots()) from collections import deque FIFO = [] for _ in range(m): a,b,c=map(int,input().split()) a-=1 b-=1 FIFO.append((c,a,b,0)) query=[] for _ in range(q): a,b,c=map(int,input().split()) a-=1 b-=1 FIFO.append((c,a,b,1)) query.append((c,a,b,1)) uf = UnionFind(n) ans={} FIFO.sort() FIFO = deque(FIFO) while FIFO: (c,a,b,flag)=FIFO.popleft() if flag==1: if uf.same(b,a): ans[(c,a,b,1)]="No" else: ans[(c,a,b,1)]="Yes" else: uf.union(a,b) for item in query: print(ans[item]) #uf = UnionFind(n) #uf.union(0, 2)
ABC245 F - Endless Walk
■問題
有向グラフが与えられて、ある点からスタートして永遠に移動し続けることが可能な点の数
→スタートした後に、ループし続ける点の数を求める
■考え方
ある点から出ていく事が出来ない場合、その点は要件を満たす事が出来ない。
出ていくことが出来ない点を消していく。
n,m=map(int,input().split()) uv=[list(map(int,input().split())) for _ in range(m)] desu=[0]*n tree=[[] for _ in range(n)] tree_rev=[[] for _ in range(n)] for [u,v] in uv: tree[u-1].append(v-1) tree_rev[v-1].append(u-1) desu[u-1]+=1 from collections import deque d = deque([]) for i in range(n): if desu[i]==0: d.append(i) check=[0]*n while d: node=d.popleft() check[node]=1 for nextNode in tree_rev[node]: desu[nextNode]-=1 if desu[nextNode]==0: d.append(nextNode) print(check.count(0))
ABC246 F - typewriter
【問題】
・限られた文字だけが入力可能な、タイプライターが複数与えられる。
・各タイプライターは1種類だけ利用可能で、L文字入力する。
・L文字が何種類出来るか答えよ。
【考え方】
・ABしか入力できないタイプライターと、ACしか入力出来ないタイプライターで入力できる文字は
それぞれAA、AB、BA、BBと、AA、AC、CA、CC。
AAが重複している為、AAを取り除く必要がある。
・余事象で解ける。
・余事象では、いまいち良く分かっていないが、ベンズでいうと
1つの円ー2つの円が重なっている場所＋3つの円が重なっている場所ー4つの円が重なっている場所＋5つの円が重なっている場所・・・・
で重なっていない全ての面積が求まるらしい。
・上記をbit全探索を用いて実装する。
n,l=map(int,input().split()) typewriter=[input() for _ in range(n)] typewriter_bin=[] mod= 998244353 for item in typewriter: tmp=0 for i in range(ord("z")-ord("a")+1): if chr(ord("a")+i) in item: tmp+=pow(2,i) typewriter_bin.append(tmp) ans=0 #タイプライターの組み合わせ for i in range(1,2**n): kouho=[] for j in range(n): if i>>j&1==1: kouho.append(typewriter_bin[j]) tmp=kouho[0] for item in kouho[1:]: tmp=tmp&item #足す tmp=str(bin(tmp)).count("1") if len(kouho)%2==1: ans+=pow(tmp,l,mod) ans%=mod #引く else: ans-=pow(tmp,l,mod) ans%=mod print(ans%mod)
ABC247 F - Cards
【問題】
・N毎のカードが配られる。
・カードの表面には1~Nの数字が、裏面にも1~Nの数字が書かれる。
・全ての１～Nの数字が記載されたカードを選ぶ時の選び方は何通りか。
【考え方】
・表面と裏面に1回ずつ記載されるため、画数字は、2か所に記載されている。
・UnionFindなどを使って、カードを連結してるかどうかのグループに分ける。
・各グループ毎にDPを用いて、そのグループで何通りの選び方があるかを計算する。
from collections import deque n=int(input()) p=list(map(int,input().split())) q=list(map(int,input().split())) mod=998244353 tree=[[] for _ in range(n)] for i in range(n): tree[p[i]-1].append(q[i]-1) tree[q[i]-1].append(p[i]-1) from collections import deque group=[] check=[0]*n for i in range(n): if check[i]==0: check[i]=1 d = deque([i]) tmp_group=set([]) while d: tmp=d.popleft() tmp_group.add(tmp) for j in tree[tmp]: if check[j]==0: d.append(j) check[j]=1 group.append(len(list(tmp_group))) ans=1 for nn in group: if nn==1: ans=ans*1 elif nn==2: ans=ans*3 else: #dp[i][x] # x=1繋がっている x=0繋がっていない dp_tunagi=[[0]*2 for _ in range(nn)] dp_tunagazu=[[0]*2 for _ in range(nn)] dp_tunagi[0][1]=1 dp_tunagazu[0][0]=1 for i in range(1,nn): dp_tunagi[i][0]+=dp_tunagi[i-1][1]%mod dp_tunagi[i][1]+=dp_tunagi[i-1][0]+dp_tunagi[i-1][1]%mod dp_tunagi[i][0]%=mod dp_tunagi[i][1]%=mod dp_tunagazu[i][0]+=dp_tunagazu[i-1][1]%mod dp_tunagazu[i][1]+=dp_tunagazu[i-1][0]+dp_tunagazu[i-1][1]%mod dp_tunagazu[i][0]%=mod dp_tunagazu[i][1]%=mod tmp=(dp_tunagi[-1][0]+dp_tunagi[-1][1]+dp_tunagazu[-1][1])%mod ans=ans*tmp%mod ans%=mod # print(dp_tunagi) #print(dp_tunagazu) print(ans%mod)
