A問題 2023
Pythonだとスライスが便利です
s=list(input()) for i in range(len(s)-1): print(s[i],end='') print("4")
#include <bits/stdc++.h> using namespace std; int main() { string s; cin >> s; for (int i=0;i<s.size()-1;i++)cout << s[i]; cout << 4 << endl; return 0; }
B問題 Tetrahedral Number
全探索で通ります。
n=int(input()) for i in range(n+1): for ipp in range(n+1): for k in range(n+1): if i+ipp+k<=n: print(i,ipp,k)
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; for (int a=0;a<=n;a++){ for (int b=0;b<=n;b++){ for (int c=0;c<=n;c++){ if (a+b+c<=n)cout << a << " " << b << " " << c << endl; } } } return 0; }
C問題 Loong Tracking
すべての座標をリストに入れて添字をいい感じにする
n,q=map(int,input().split()) rotti=[] for i in range(n): rotti.append([n-i,0]) count=0 for i in range(q): a,b=input().split() if a=="1": x=rotti[len(rotti)-1][0] y=rotti[len(rotti)-1][1] if b=="R": rotti.append([x+1,y]) elif b=="L": rotti.append([x-1,y]) elif b=="U": rotti.append([x,y+1]) else: rotti.append([x,y-1]) count+=1 else: print(rotti[n-int(b)+count][0],rotti[n-int(b)+count][1])
D問題 Loong and Takahashi
一番外側から順番にまいていくようにすれば簡単です。
n=int(input()) rotti=[[-1]*n for i in range(n)] rotti[n//2][n//2]="T" hako=["R","D","L","U"] iti=0 a=0 b=0 for i in range(n*n-1): rotti[a][b]=i+1 if hako[iti]=="R" and b+1<n and rotti[a][b+1]==-1: b+=1 continue elif hako[iti]=="D" and a+1<n and rotti[a+1][b]==-1: a+=1 continue elif hako[iti]=="L" and b-1>=0 and rotti[a][b-1]==-1: b-=1 continue elif hako[iti]=="U" and a-1>=0 and rotti[a-1][b]==-1: a-=1 continue else: iti+=1 if len(hako)==iti: iti=0 if hako[iti]=="R" and b+1<n: b+=1 continue elif hako[iti]=="D" and a+1<n: a+=1 continue elif hako[iti]=="L" and b-1>=0: b-=1 continue elif hako[iti]=="U" and a-1>=0: a-=1 continue for i in range(n): print(*rotti[i])
E問題 Non-Decreasing Colorful Path
そもそもこの問題だと、書いてある整数が大きい頂点から小さい頂点に行くことは絶対にできないので最初に辺を削除します（値が小さい頂点から大きい頂点しか行けない有向グラフにする）
その後、その頂点に来るまでに何通りの方法があるかDPします。
ここで、同じ数字かつ連結関係にある頂点たちは、まとめて一つの頂点ということにします。
n,m=map(int,input().split()) amount=list(map(int,input().split())) rotti=[[]*1 for i in range(n)] same=[[]*1 for i in range(n)] irane=set() for i in range(m): a,b=map(int,input().split()) if amount[a-1]==amount[b-1]: same[a-1].append(b) same[b-1].append(a) irane.add(a) irane.add(b) elif amount[a-1]>amount[b-1]: rotti[b-1].append(a) else: rotti[a-1].append(b) irane_rotti=set([1]) iti=0 stack=[1] while len(stack)>iti: hako=stack[iti] for i in range(len(rotti[hako-1])): if rotti[hako-1][i] in irane_rotti: continue irane_rotti.add(rotti[hako-1][i]) stack.append(rotti[hako-1][i]) for i in range(len(same[hako-1])): if same[hako-1][i] in irane_rotti: continue irane_rotti.add(same[hako-1][i]) stack.append(same[hako-1][i]) iti+=1 dp=[0]*n dp[0]=1 stack=[] a=[] hako=amount[0] for i in range(len(amount)): if not i+1 in irane_rotti: continue a.append([amount[i],(i+1)*-1]) a=sorted(a) for i in range(len(a)): stack.append(a[i][1]*-1) iti=0 irane_num=set() while len(stack)>iti: hako=stack[iti] if not hako in irane: for i in range(len(rotti[hako-1])): dp[rotti[hako-1][i]-1]=max(dp[rotti[hako-1][i]-1],dp[hako-1]+1) iti+=1 continue if hako in irane_num: iti+=1 continue irane_num.add(hako) hako2=[hako] iti2=0 irane2=set([hako]) while len(hako2)>iti2: hako=hako2[iti2] for i in range(len(same[hako-1])): if same[hako-1][i] in irane2: continue hako2.append(same[hako-1][i]) irane_num.add(same[hako-1][i]) irane2.add(same[hako-1][i]) iti2+=1 irane2=set() count=0 for i in range(len(hako2)): hako=hako2[i] count=max(count,dp[hako-1]) for ipp in range(len(rotti[hako-1])): irane2.add(rotti[hako-1][ipp]) #dp[rotti[hako-1][i]-1]=dp[hako-1]+1 #stack.append(rotti[hako-1][i]) for i in range(len(hako2)): hako=hako2[i] dp[hako-1]=count irane2=list(irane2) for i in range(len(irane2)): hako=irane2[i] dp[hako-1]=max(dp[hako-1],count+1) iti+=1 print(dp[n-1])
