ARC-B ツリーグラフ
B: ツリーグラフ - AtCoder Regular Contest 030 | AtCoder
頂点からなるツリーグラフが与えられます。
いくつかの頂点にはお宝があり、そのお宝をすべて回収し、最初の頂点に戻ってくるまでの最小コストを求める問題です。
各頂点について考えます。
現在見ている頂点()を親に持つ頂点を通る必要がある→子孫のうち1つでも宝石を持っている。
という場合です。
宝石が見つかった場合は親にtrueを、そうでない場合はfalseを返すような再帰関数で解くことができます。
こういう問題が好きです()
#include <vector> #include <iostream> #include <utility> #include <algorithm> #include <string> #include <deque> #include <queue> #include <tuple> #include <queue> #include <functional> #include <cmath> #include <iomanip> #include <map> #include <set> #include <numeric> #include <unordered_map> #include <unordered_set> #include <complex> #include <iterator> #include <array> #include <memory> #include <stack> #define vi vector<int> #define vvi vector<vector<int> > #define ll long long int #define vl vector<ll> #define vvl vector<vector<ll>> #define vb vector<bool> #define vc vector<char> #define vs vector<string> #define ld long double #define INF 1e9 #define EPS 0.0000000001 #define rep(i,n) for(int i=0;i<n;i++) #define loop(i,s,n) for(int i=s;i<n;i++) #define all(in) in.begin(), in.end() template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; } template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; } #define MAX 9999999 using namespace std; class Edge{ public: int to,from,cost; }; vector<int>jem(101,0); vector<vector<int>>edge(101); vector<int>cost(101,0); bool dfs(int from,int vertex){ bool var=false; if(edge[vertex].size()==1&&jem[vertex]==0)return false; rep(i,edge[vertex].size()){ int next=edge[vertex][i]; if(next==from)continue; if(dfs(vertex,next))var=true; } if(var||jem[vertex])cost[from]+=cost[vertex]+2; else return false; return true; } int main(){ int n,x; cin>>n>>x; rep(i,n){ int foo; cin>>foo; if(foo)jem[i+1]=1; } rep(i,n-1){ int to,from; cin>>to>>from; edge[to].push_back(from); edge[from].push_back(to); } rep(i,edge[x].size())dfs(x,edge[x][i]); cout<<cost[x]<<endl; }
AOJ -0235 Sergent Rian
問題文:Sergeant Rian | Aizu Online Judge
すべての橋を爆破する最短コストは、最もコストが掛かる島(葉ではなく、1から到達するまでに最もコストがかかる島)を爆破する順番を最後にすれば良い。
サンプルを最短コストになるように鉛筆でなぞると、最もコストが掛かる島に辿り着くまでの橋以外は二度通ることになります。
したがって解法は
すべての橋を爆破するコスト*2-最長のコスト
となります。
#include <vector> #include <iostream> #include <utility> #include <algorithm> #include <string> #include <deque> #include <queue> #include <tuple> #include <queue> #include <functional> #include <cmath> #include <iomanip> #include <map> #include <set> #include <numeric> #include <unordered_map> #include <unordered_set> #include <complex> #include <iterator> #include <array> #include <memory> #include <stack> #define vi vector<int> #define vvi vector<vector<int> > #define ll long long int #define vl vector<ll> #define vvl vector<vector<ll>> #define vb vector<bool> #define vc vector<char> #define vs vector<string> #define ld long double #define INF 1e9 #define EPS 0.0000000001 #define rep(i,n) for(int i=0;i<n;i++) #define loop(i,s,n) for(int i=s;i<n;i++) #define all(in) in.begin(), in.end() template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; } template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; } #define MAX 9999999 using namespace std; #define int ll typedef pair<int, int> pii; typedef pair<double,double>pdd; class edge{ public: int to; int cost; void Init(){to=0; cost=0;} edge(int t, int c):to(t), cost(c){}; }; vi d(100,INF); vector<edge>Edge[100]; void dijkstra(){ d[1]=0; priority_queue<pii,vector<pii>,greater<pii> >que; que.push(pii(0,1)); while(!que.empty()){ pii now=que.top(); que.pop(); int to_v=now.second; if(d[to_v]<now.first)continue; rep(i,Edge[to_v].size()){ edge e=Edge[to_v][i]; if(d[e.to]>d[to_v]+e.cost){ d[e.to]=d[to_v]+e.cost; que.push(pii(d[e.to],e.to)); } } } } signed main(){ int n; while(cin>>n,n){ vector<pair<pii,int>>data; rep(i,100)Edge[i].clear(); rep(i,n-1){ int from,to,cost; cin>>from>>to>>cost; Edge[from].push_back(edge(to,cost)); Edge[to].push_back(edge(from,cost)); data.push_back(make_pair(pii(from,to),cost)); } int sum=0; rep(i,n+1)d[i]=INF; dijkstra(); int maxi=0; for(int i=0; i<data.size();i++){ if(data[i].first.first==1){ if(Edge[data[i].first.second].size()==1)continue; }else if(data[i].first.second==1){ if(Edge[data[i].first.first].size()==1)continue; }else if(Edge[data[i].first.first].size()==1 || Edge[data[i].first.second].size()==1) continue; sum+=data[i].second; } sum*=2; for(int i=1; i<=n;i++){ if(i==1)continue; if(Edge[i].size()==1)continue; cmax(maxi, d[i]); } cout<<sum-maxi<<endl; } }
D-Simple Knapsack
コンテストに参加しなかったのですが、想定解ではない方法で解いたので記事にします。
ABCのD問題、重さを圧縮したらdpで解けるんじゃねと思ってやってるんですが無限にWAを生成してます。なぜ
— yebi (@sigsigma19) 2017年5月2日
解法は,重さの制約が特殊なので最初の重さを引いて動的計画法をします。
個目まで見た時の価値
で
個選んだときの最大値
として、ナップサックのdpをやります。
多次元DPを初めてやったのですが、良い練習になったと思います。
#include <vector> #include <iostream> #include <utility> #include <algorithm> #include <string> #include <deque> #include <queue> #include <tuple> #include <queue> #include <functional> #include <cmath> #include <iomanip> #include <map> #include <set> #include <numeric> #include <unordered_map> #include <unordered_set> #include <complex> #include <iterator> #include <array> #include <memory> #include <stack> #define vi vector<int> #define vvi vector<vector<int> > #define ll long long int #define vl vector<ll> #define vvl vector<vector<ll>> #define vb vector<bool> #define vc vector<char> #define vs vector<string> #define ld long double #define INF 1e9 #define EPS 0.0000000001 #define rep(i,n) for(int i=0;i<n;i++) #define loop(i,s,n) for(int i=s;i<n;i++) #define all(in) in.begin(), in.end() template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; } template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; } #define MAX 9999999 using namespace std; typedef pair<int, int> pii; typedef pair<double,double>pdd; typedef pair<ll,ll>pll; #include<string.h> ll dp[505][105][405]={0}; int main(){ ll N,W; cin>>N>>W; vl v,w; ll lim=0; rep(i,N){ ll value,wegiht; cin>>wegiht>>value; if(wegiht>W)continue; if(!i)lim=wegiht-1; dp[wegiht-lim][i][1]=value; v.push_back(value); w.push_back(wegiht-lim); } for(int j=0;j<N-1;j++){ for(int i=0; i<401;i++){ for(int k=0; k<=N;k++){ if(dp[i][j][k]==0)continue; dp[i][j+1][k]=max(dp[i][j+1][k],dp[i][j][k]); if(i+lim*k+w[j+1]+lim>W)continue; cmax(dp[i+w[j+1]][j+1][k+1],dp[i][j][k]+v[j+1]); } } } ll ans=0; rep(i,401)rep(j,N+1)cmax(ans,dp[i][N-1][j]); cout<<ans<<endl; }
Kansai Camp 参加記
3月26~3月29日にかけて、KMC(京都大学マイコンクラブ)とNAIST、RiPProで行った合同合宿の参加記です。
全部書いてると長くなるので、コンテストの内容とかはおいおい書くつもりです。
1日目
集合場所も知らず、準備も全くせずに11時頃に起きました。幸い15時*1集合だったので間に合いました…が、
迷子のフレンズです(誰か助けて)
— yebi (@sigsigma19) 2017年3月26日
集合場所で誰にも合流できずに15分ぐらい死んでました。
なんとかKMCの方と合流できたあと、民宿に移動 → 自己紹介 という流れに。
自己紹介で合宿参加者のAtcoderの平均レートが1600とかいう異次元の数値*2であることが判明し、人権を喪失しました。
その流れでコドフォ(2時間ぐらい)→(めっちゃ豪華な)晩御飯→ABC
久々のコドフォだったので、(途中コンテスト以外の問題を解いてた) 色々忘れてました。
ちなみに、ABCは全完した人からお風呂に入れるみたいなノリがありました。*3
2日目
朝風呂を無事ACして始まりました。 朝ごはんがめっちゃ美味しかったです。
その後は コドフォ→お昼→ARC →ARC →晩御飯→復習→コドフォ
という流れでした。
まぁコンテストは最下位かそれぐらいでした。悲しかった。
ただ、解いた問題で自分が知ってるアルゴリズムの問題はその日のうちに通せたのが唯一の進捗です。
休憩にcodefightsとかやってました。
最後のコドフォでは無限にWAを生産してました。
C問題のWA生成担当してました。
— yebi (@sigsigma19) 2017年3月27日
コドフォのサンプル弱すぎでは？？
この日が一番コードを書いた気がします。
3日目
朝風呂ACしました。朝ごはんに２日連続で卵かけご飯が出たのが印象的でした。
この日は ARC（でチームを決める） → コドフォ（チーム戦）
みたいな流れです。
ARCの順位は…(察し)。典型DPを再帰で書いてTLEしたり、嘘解法を頑張って実装したりして悲しい事になりました。反省してます。
コドフォは４時間セットで、T.M先輩としょラーさん、KMCの方と４人でチームを組みました。
しょラーさんが解けそうな問題を僕に投げてくれて、２問ぐらい通しました。
ちなみにjudgeの時、WAしたら土下座しようと思ってました。
他の問題はさっぱりで、なんとか解こうとしたものの敗北。
4時間コンテストは流石に辛かったです。
晩御飯を食べた後はひたすら復習をしてました。（主にARC）
KMCの同年代のNさん*4に
こういう解き方や、コンテストの別解だけではなく、セグメントツリーのライブラリや使い方など、本当に色々教えてもらいました。
とても勉強になりました、ありがとうございます。
余談ですが、けものフレンズの最終回を見ました。ハッピーエンドで終わった（？）ようで良かったです。
最終日
最終日は、競プロか周辺を散策するか迷って結局周辺を散歩しました。
近くの山を散歩したり、足湯に入って新歓の話やプログラミングの話をしてました。
合宿の様子です。
— yebi (@sigsigma19) 2017年3月29日
ご査収ください pic.twitter.com/oO3rRhxkNH
足湯がめっちゃ気持ちよかったです。
まとめ
正直なところ、初日は合宿のレベルが高くて、自分は場違いでは？と思うこともありましたが、参加してよかったと思っています。
実装力もアルゴリズム力も無い僕ですが、周囲の方々のレベルが高い&競プロだけをする環境の中で、色々と感じることもあったし、何より競プロに真剣に取り組めたのではないかな、と思います。
合宿期間は健康とは決して言えない生活だったんですが、温泉パワーとご飯*5で乗り切れたのも、合宿ならではだと思いました。
合宿を企画してくださったKMCの皆さん、ありがとうございました。
典型ナップサックを1次元配列で解く。
※一番PV数が多いので、ちょっと直しました(2020/5/24)
例題として、 B - 書き換え（Rewrite）を使います。
まずはこのコードを見てください。
#include<bits/stdc++.h> using namespace std; int main(){ int N,M; cin >> N >> M; vector<int>V(N),T(N); for(int i = 0; i < N; ++i){ cin >> V[i] >> T[i]; } vector<int>dp(M + 1,0); for(int i = 0; i < N; i++) for(int t = M; t >= 0;t--){ if(t + T[i] <= M) dp[t + T[i]] = max(dp[t + T[i]], dp[t] + V[i]); } cout << *max_element(dp.begin(), dp.end()) << endl; }
シンプルですね。時間計算量はですが、空間計算量は
で少しお得です。
まずは2次元で考える。
二次元DPで考えると、
個目の書類を見ている時に,
時間使ったときの最大値
という漸化式になります。
さて、この問題を1次元配列で解くことを考えます。
時間
のときの最大の価値
つまり、どの書類を見ているか、という情報を捨てます。
以下が工夫するポイントです。
後ろ向きに更新する
時間を後ろからなめて、次のように更新します。
for(int t = M; t >= 0; --t)
嬉しいポイントは、値の更新がすでに見たに対して行われます。つまり、
番目の書類を重複して更新されることがありません。
荷物を取らない推移ないけど？
必要無いからです。2次元DPの際は,番目の書類まで見た結果を
番目にも反映させる必要があるますが、この場合はありません。
RUPC 2017 参加記
０日目
基本的に事務的な準備をしてました。
問題文や解法の議論に全く参加できなかったので、来年はそういう積極的に参加したい。
さて、明日のコンテストは立命勢の日ですが今年はなんと阪大勢とのコラボです!!☺️そしていつもよりコンテストが1時間長いです...!!果たして何問コンテストなのでしょうか〜！(知ってる顔
1日目
立命セットだったので、基本的にイスに座ってFAを記録したり、風船係をしてました。懇親会では、会津合宿のときにチームを組んだ somennagasiさんや学生ではない競プロerさんと、新歓の話やプログラミングの話をした。*1
食事が美味しくてびっくりした。
余談ですが、会場に向かっている間に、gccを吹き飛ばす*2という事件がありました。
大変なことになりました。 pic.twitter.com/CPGT1xNXhT
２日目
NCA***さんとmkanさんで、チームGumikanstarで参加しました。
NCA***さんがC、mkanさんがA,僕がB問題を担当しました。
Bがさっと解けそう*3だったので、mkanさんの考察を手伝っている間にNCA***さんがC問題を通す(プロ)。
なんとかB問題を2WAしながら通したものの、その後は全くチームの役に立てずに死亡。
結果はB,C,Eの３完でした。
念のために0.001刻みでループを回しました。#RUPC2017
— yebi (@sigsigma19) 2017年3月23日
Aが本当に辛かったです。
コンテスト後の懇親会ではいろんな大学の競プロerさんとお話することができて、とても楽しかったです。
３日目
Yang33さんとGachoさんとチーム名Gachofriendsで参加しました。
Yang33さんがA問題、僕がB問題、GachoさんがC問題を担当しました。
A問題をYang33がすごいスピードでAC、僕の考察が行き詰まっていたので手伝ってもらいました。
解法はわかったものの、僕の実装力がなさすぎてYang33さんと一緒に実装することに。
コード量が爆発しそう&&バグが発生したので、C,Dを通したGachoさんと合流し３人で解いて無事AC。
結果はA~Dの４完でした。完全に戦犯で悲しい。
まとめ
前回の会津合宿のときよりは、少し成長したかな？と思った反面、実装力、考察力不足を痛感する合宿でした。
これからも精進していきます。
次の合宿では人狼がしたいと思いました。
ABC C - Factors of Factorial
N!の約数の個数を数える問題。
の数字を片っ端から素数で割っていく。
は添字に素数を持ち、N!の素因数の数を持つ。
の値を初めて更新するとき(
)は、
が含まれるから
にしてる。
#include<iostream> #include<string> #include<cstdio> #include<algorithm> #include<stack> #include<queue> #include<vector> #include<cmath> #include<utility> #include<set> #include<complex> #include<map> #define vi vector<int> #define vvi vector<vector<int> > #define ll long long int #define vl vector<ll> #define vvl vector<vector<ll>> #define vb vector<bool> #define vc vector<char> #define vs vector<string> #define ld long double #define INF 1e9 #define EPS 0.0000000001 #define rep(i,n) for(int i=0;i<n;i++) #define loop(i,s,n) for(int i=s;i<n;i++) #define all(in) in.begin(), in.end() #define MAX 1e4 #define MOD 1000000007 using namespace std; typedef pair<int, int> pii; typedef pair<double,double>pdd; typedef pair<ll,ll>pll; vi inde(MAX,0); ll cal(int num, int div){ int ans=1; while(true){ if(num%div==0){num/=div; ans++;} else break; } if(!inde[div])inde[div]+=ans; else inde[div]+=ans-1; return 0; } int main(){ vector<bool>Primecheck(MAX+1,true); vector<int>Primenumber(MAX+1,0); int Primecounter =0; for(int i = 2; i<MAX+1;i++){ if(Primecheck[i]){ for(int j = 2;i*j<MAX;j++) Primecheck[i*j] = false; Primenumber[Primecounter] = i; Primecounter++; } } ll num; cin>>num; ll ans=1; for(int n=(int)num; n>1; n--){ for(int i=0; i<Primecounter;i++){ if(Primenumber[i]>n)break; if(n%Primenumber[i]==0){cal(n,Primenumber[i]);} } } for(int i=0; i<num+1; i++){ if(inde[i]){ans*=inde[i]; ans%=MOD;} } cout<<ans<<endl; }
