会員登録後、有料プランで広告を非表示に
詳しくはこちら
話には聞くグラフ理論なるものについて，そろそろ体系的に練習したいと思ったので，Aizu Online Judgeのコース問題を解いてみました。 11_A~C はプログラム上でグラフを扱う練習のような問題だったので，よりアルゴリズムっぽい 11_D~12_C を掲載しています。 問題はこちら onlinejudge.u-aizu.ac.jp 11_D: 連結成分分解 12_A: 最小全域木 12_B: 単一始点最短経路 12_C: 単一始点最短経路 II 11_D: 連結成分分解 コメント 連結成分分解というタイトルですが，連結成分ごとの頂点集合を作ったりするのではなく，Union-Find木と…
問題はこちら atcoder.jp 方針 個のスイッチのon/off状態の順列は 通り，ということで一目全探索っぽいです。 問題では電球→スイッチの対応関係しか与えられないので，スイッチ→電球の対応関係を表す配列を作っています。あとはbit全探索です。 コード #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0; i<(n); i++) bool judge(int bit); int n,m; vector<int> k; vector<vector<int>> s; vector<int> p…
問題はこちら atcoder.jp 方針 +が入る場所は， の各数字の間 ヶ所です。それぞれの箇所について，+が入っている状態を1，何も入っていない状態を0とすれば，bit全探索が適用できます。 各数式の値を計算するプロセスはコードを見てください。 コード #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0; i<(n); i++) long long value(int bit); string s; int n; int main(){ cin>>s; n=s.size()-1; // '+'…
問題はこちら atcoder.jp 方針 購入する参考書の組み合わせが高々 通りしかないところを見るに，全探索で解くのが本命です。 今回は「bit全探索」を用いていますが，この手法を使った経験がなかったのでたどたどしいコードになっています。 コード #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0; i<(n); i++) int n,m,x; vector<int> c; vector<vector<int>> a; bool judge(int bit); int cost(int bit)…
問題はこちら atcoder.jp 方針 基本的な動作は，「各マスについて，周囲8マスの爆弾の数を数える」ということですが，端のマスには調べるべき8マスが存在しないので，それをどう処理するかが一つのポイントだろうと思います。 私は，マス目の周囲にダミーの要素Nを入れる，という方法を取っています。 下のコードでは肝心の爆弾の数を数える処理が冗長になってしまっていますが，解説PDF にうまい手法が紹介されています。 コード #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0; i<(n); i++) …
問題はこちら atcoder.jp 方針 簡単のため，上の列をマス ，下の列をマス とします。 動き方のパターンは，どの で と動くかの高々 通りしかないので，全部調べればよいです。 コード #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0; i<(n); i++) int main(){ int n; cin>>n; vector<int> a(n),b(n); REP(i,n){ cin>>a[i]; } REP(i,n){ cin>>b[i]; } int sum=0,max=0; REP…
問題はこちら atcoder.jp 方針 単位量あたりの価格が安い（コスパが良い）サイズのボトルを優先的に購入します。 コード #include <bits/stdc++.h> using namespace std; int main(){ long long q,h,s,d; long long n; cin>>q>>h>>s>>d>>n; long long sum=0; // 2リットル入り if(d<2*s && d<4*h && d<8*q){ sum+=(n/2)*d; n%=2; } // 1リットル入り if(s<2*h && s<4*q){ sum+=n*s; n=0; }…
問題はこちら atcoder.jp 方針 数列 は を並び替えたものなので，題意の操作の結果は， となるほかありません。 このとき，置き換えられるべき要素は 以外の 個であり，1回の操作で最大 個の要素を置き換えることができます。 つまり，求める操作回数は，（ 以上で最小の整数）です。 操作は を含む部分から始めればよく，操作回数は数列の並びによらず一定なので，実は を受け取る必要もありません。 （簡単すぎて嘘解法かと疑いましたが，解説PDFでも同様の解法が紹介されていました。こちらには証明もついています。） コード #include <bits/stdc++.h> using namespa…
ABC168 C - : (Colon) をベクトル計算で解く
ABC168のC問題ではゴリゴリの幾何問題が出題され，「余弦定理」がツイッターでトレンド入りするなど話題になりました。 私は普通に余弦定理を用いて解いたのですが，結構いろいろな解き方があったようです。ここでは，自分が後で思いついたうちの1つである「ベクトル」を用いた解法を示していきたいと思います（ベクトルの内積の定義に が使われているので，本質的には余弦定理と同じですが）。 問題はこちら atcoder.jp 前提 時計の中心を とし，時針，分針の でない端点をそれぞれ と表す。また， とし（長さが大文字なのは気持ち悪かったので問題文から変更しています）， 軸の正の方向と とのなす角をそれぞれ…
日立製作所 社会システム事業部 プログラミングコンテスト2020 B - Nice Shopping
問題はこちら atcoder.jp 方針 かかる金額が最小になるような買い方は，一番安い冷蔵庫と一番安い電子レンジを買うか，割引券が使える 種類の買い方のどれか，のいずれかです。 コード #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0; i<(n); i++) #define ALL(n) begin(n),end(n) int main(){ int A,B,m; cin>>A>>B>>m; vector<int> a(A),b(B); int lowest_a=100001,lowest_…
問題はこちら atcoder.jp 方針 題意の操作を実際に実行しながら調べます。 コード #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0; i<(n); i++) int main(){ int n; cin>>n; vector<int> h(n); bool judge=true; REP(i,n){ cin>>h[i]; if(i>0){ if(h[i-1]==h[i]+1){ h[i]++; }else if(h[i-1]>h[i]+1){ judge=false; break; }…
AGC012 A - AtCoder Group Contest
問題はこちら atcoder.jp 方針 を降順ソートします。このとき， の中から各チームの2番目の人の強さをできるだけ大きくするには， のようにチーム分けをすれば良いです。つまり，求める和は です。 コード #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0; i<(n); i++) #define ALL(n) begin(n),end(n) int main(){ long long n; cin>>n; vector<long long> a(3*n); REP(i,3*n){ cin>>…
問題はこちら atcoder.jp 方針 各 に対して， if 問題P[i]がAC済{ continue }else{ if 提出iがAC{ 正解数++ ペナルティ数+=問題P[i]のWA数 }else{ 問題P[i]のWA数++ } } という操作を行います。 コード #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0; i<(n); i++) int main(){ int n,m; cin>>n>>m; vector<int> p(m); vector<string> s(m); REP(i…
問題はこちら atcoder.jp 方針 を昇順ソートすると，求める最小値は， のうち最も小さい値です。 コード #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0; i<(n); i++) #define ALL(n) begin(n),end(n) int main(){ int n,k; cin>>n>>k; vector<int> h(n); REP(i,n){ cin>>h[i]; } sort(ALL(h)); int d,d_min; REP(i,n-k+1){ d=h[i+k-1]…
問題はこちら atcoder.jp 方針 なので普通にループを回しています。 コード #include <bits/stdc++.h> using namespace std; int main(){ int x; cin>>x; int ans=1; for(int i=2; i<=sqrt(x); i++){ for(int j=2; j<1000; j++){ if(pow(i,j)>x){ break; } if(pow(i,j)>ans){ ans=pow(i,j); } } } cout<<ans<<endl; }
問題はこちら atcoder.jp 方針 直感で解きました。 後付けで証明もしておきます。 求める和は， と表せます。ここで，ある整数を で割った余りは なので， です。 { } { } と並べ替えたとき，これを満たします。 コード #include <bits/stdc++.h> using namespace std; int main(){ long long n; cin>>n; cout<<n*(n-1)/2<<endl; }
問題はこちら atcoder.jp 方針 問題文通りです。 コード #include <bits/stdc++.h> using namespace std; int main(){ string s; cin>>s; string subs,a="a",b="b"; int i=1; while(a!=b){ subs=s.substr(0,s.size()-2*i); a=subs.substr(0,(s.size()-2*i)/2); b=subs.substr((s.size()-2*i)/2,(s.size()-2*i)/2); i++; } cout<<subs.size()<<e…
AGC029 A - Irreversible operation
問題はこちら atcoder.jp 方針 題意の操作は，文字列 においてBWをWBにすることと同じです。また， がWW...WBB...Bとなった時点で操作は終了します。 つまり，Wに注目すると， 回の操作で つのWが つ左に動き， 中にWが 個あるとき，一番うしろのWが 番目に来た時点で操作が終了します。 中で 個目のWが 番目にあるとき，これを 番目に移動させるためには 回の操作が必要です。 コード #include <bits/stdc++.h> using namespace std; int main(){ string s; cin>>s; vector<int> coor_w; …
三井住友信託銀行プログラミングコンテスト2019 C - 100 to 105
問題はこちら atcoder.jp 方針 円ちょうどの買い物をできるならば，買う品物の数は 個( は の商) とできます1。 個の商品による合計金額 は なので， がこの範囲に含まれているかを判定すればよいです。コード中では余り を用いてやや工夫しています。 解説PDF では3種類の解法が紹介されています。 コード #include <bits/stdc++.h> using namespace std; int main(){ int x; cin>>x; int q=x/100; int r=x%100; cout<<(r<=q*5)<<endl; } (i)買う品物の数が 個以上のとき，…
問題はこちら atcoder.jp 方針 日後に家に戻ってくるためには，旅程にNがあるならばSが少なくとも1つ必要で，SがあるならばNが少なくとも1つ必要です。W,Eについても同様。個数は関係ありません。 コード #include <bits/stdc++.h> using namespace std; int main(){ string s; cin>>s; bool north=false; bool south=false; bool east=false; bool west=false; bool judge=true; for(int i=0; i<s.size(); i++){…
問題はこちら atcoder.jp 方針 特になし。偶奇の場合分けのやり方はいくつかあると思います。 コード #include <bits/stdc++.h> using namespace std; int main(){ string o,e; cin>>o>>e; string password; for(int i=0; i<o.size(); i++){ password.push_back(o[i]); if(e.size()==i){ continue; } password.push_back(e[i]); } cout<<password<<endl; }
問題はこちら atcoder.jp 方針 に現れる最初のAから最後のZまでの文字列が，条件を満たす最長の文字列になります。 コード #include <bits/stdc++.h> using namespace std; int main(){ string s; cin>>s; int firstA=-1; int lastZ=-1; for(int i=0; i<s.size(); i++){ if(s[i]=='Z'){ lastZ=i; } if(firstA!=-1){ continue; } if(s[i]=='A'){ firstA=i; } } cout<<lastZ-fir…
問題はこちら atcoder.jp 方針 レンガが123...と並ぶように，邪魔なレンガを砕いていきます。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; vector<int> a(n); for(int i=0; i<n; i++){ cin>>a[i]; } int count=0; int aim=1; for(int i=0; i<n; i++){ if(a[i]!=aim){ count++; }else{ aim++; } } if(aim==1){ count=-1; } …
問題はこちら atcoder.jp 独り言 画像の引き伸ばしってこういう感じでやってるんかな。 コード #include <bits/stdc++.h> using namespace std; int main(){ int h,w; cin>>h>>w; vector<vector<char>> c(h,vector<char>(w)); vector<vector<char>> d(h*2,vector<char>(w)); for(int i=0; i<h; i++){ for(int j=0; j<w; j++){ cin>>c[i][j]; d[i*2][j]=c[i][j]; d…
問題はこちら atcoder.jp 方針 「 の末尾を取得し， の先頭に挿入→ の末尾以外を とする」という操作で， を「回転」させることができます。 を回転させて得られる文字列は高々 種類なので， 回の操作後までに と一致するか調べればよいです。 コード #include <bits/stdc++.h> using namespace std; int main(){ string s,t; cin>>s>>t; string first; bool possible=false; for(int i=0; i<s.size(); i++){ first=s.substr(s.size()-…
問題はこちら atcoder.jp 方針 を辞書順にソートし，連結すればいいのですが，C++ではsort関数でstringもソートできるので簡単です。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n,l; cin>>n>>l; vector<string> s(n); for(int i=0; i<n; i++){ cin>>s[i]; } sort(s.begin(),s.end()); string min; for(int i=0; i<n; i++){ min+=s[i]; } cout<<min<…
問題はこちら atcoder.jp 方針 「 を辞書順にソート→ を高い順にソート」という方針で解けそうですが，市名，点数，レストランの番号の3変数をどう扱うか。 ということで，tupleを使ってみました。 解説PDF では，pairを入れ子にして3変数を扱っています。どちらが楽かは好みだと思います。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; string s; int p; vector<tuple<string,int,int>> r; for(int i=0; i<n; i++…
ABC050 B - Contest with Drinks Easy
問題はこちら atcoder.jp 方針 コード #include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; vector<int> t(n); for(int i=0; i<n; i++){ cin>>t[i]; } int m; cin>>m; vector<int> p(m),x(m); for(int i=0; i<m; i++){ cin>>p[i]>>x[i]; } for(int i=0; i<m; i++){ int sum=0; for(int j=0; j<n; j++){ if(j==p…
問題はこちら atcoder.jp 方針 によって税抜き価格のあたりをつけるのですが，int型は小数点以下切り捨てであるという性質上，本当の税抜価格は，a_sup,b_sup以上の整数です。 a_sup,b_sup以上である周辺の整数のうち，条件を満たすものが見つかり次第それを出力します。 コード #include <bits/stdc++.h> using namespace std; int main(){ int a,b; cin>>a>>b; int a_sup,b_sup; a_sup=a/0.08; b_sup=b/0.1; int m=max(a_sup,b_sup); bool…
ABC093 B - Small and Large Integers
問題はこちら atcoder.jp 方針 コード #include <bits/stdc++.h> using namespace std; int main(){ int a,b,k; cin>>a>>b>>k; for(int i=0; i<k; i++){ if(a+i>=((double)a+b)/2){ break; } cout<<a+i<<endl; } for(int i=k-1; i>=0; i--){ if(b-i<((double)a+b)/2){ continue; } cout<<b-i<<endl; } }
問題はこちら atcoder.jp 方針 構造的に難しい点はありませんが，2点間の距離の公式がやや複雑なのでコードもごちゃごちゃしています。 私は整数かどうかの判定は，「int型とdouble型の値が一致するか」，という発想をよく用いるのですが，他にやっている人を見たことがありません。何か技術的にまずい点があるのかもしれません。 一応AtCoderの解説PDFもご覧ください。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n,d; cin>>n>>d; vector<vector<int>> x(n,vect…
問題はこちら atcoder.jp 方針 「その単語はまだ発言していない単語である」ことと「その単語の先頭の文字は直前に発言した単語の末尾の文字と一致する」ことを確認しています。計算量が少ないので特に工夫はしていません。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; vector<string> w(n); for(int i=0; i<n; i++){ cin>>w[i]; } bool judge=true; for(int i=1; i<n; i++){ if(w[i-1][w[i…
問題はこちら atcoder.jp 方針 to_stringを使ってみたかったので複雑になっています。 digit_sum+=i_str[j]-'0'の-'0'については，こちらを参考にしました。ASCIIコードでは文字'0'が48に対応しているらしいです。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n,a,b; cin>>n>>a>>b; int sum_total=0; int digit_sum=0; string i_str; for(int i=1; i<=n; i++){ digit_sum=…
問題はこちら atcoder.jp 方針 各都市ではなく道路に注目しています。C. Peaks（記事にする予定）と似た発想です。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n,m; cin>>n>>m; vector<int> a(m),b(m); for(int i=0; i<m; i++){ cin>>a[i]>>b[i]; } vector<int> count(n); for(int i=0; i<m; i++){ count[a[i]-1]++; count[b[i]-1]++; } for(i…
問題はこちら atcoder.jp 方針 ボタンの挙動は問題分の通りに作ります。 問題はボタン が点けられるかの判定ですが， 回の操作後までにボタン が光らない場合，初期のボタン も含めてこれまでに 回ボタンが光っています。ボタンの数は 個なので，少なくとも 個のランプが 度光っています。つまりループしています。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; vector<int> a(n); for(int i=0; i<n; i++){ cin>>a[i]; } int count=…
問題はこちら atcoder.jp 方針 あらかじめ縁のための配列を確保しておきます。 コード #include <bits/stdc++.h> using namespace std; int main(){ int h,w; cin>>h>>w; vector<vector<char>> a(h+2,vector<char>(w+2)); for(int i=1; i<h+1; i++){ for(int j=1; j<w+1; j++){ cin>>a[i][j]; } } for(int j=0; j<w+2; j++){ a[0][j]='#'; a[h+1][j]='#'; } f…
問題はこちら atcoder.jp 方針 以上の整数 について， 未満のすべての素数で割り切れなければ， は素数である，という普通の素数判定。 コード #include <bits/stdc++.h> using namespace std; int main(){ int x; cin>>x; vector<int> p={2}; bool not_prime=false; int i=2; while(i<=x (not_prime==true && i>x)){ not_prime=false; for(int j=0; j<p.size(); j++){ if(i%p[j]==0…
問題はこちら atcoder.jp 方針 のように を小さくしながら考えます。それぞれの に対して を最大にする貪欲法を用いています。ある A_i は B_i-1, B_i にのみ制約されるので，貪欲法で最適解が求まります。 （アルゴリズムがほぼ分からないので雰囲気で言ってます。間違い等あればご指摘ください。） コード #include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; vector<int> a(n),b(n-1); for(int i=0; i<n-1; i++){ cin>>b[i]; } in…
問題はこちら atcoder.jp 方針 まず の桁数を比較し，それが同じ場合には大きい位の値から比較していきます。 コード #include <bits/stdc++.h> using namespace std; int compare(string x,string y,int i); int main(){ string a,b; cin>>a>>b; int i=0; if(a.size()>b.size()){ cout<<"GREATER"<<endl; }else if(a.size()<b.size()){ cout<<"LESS"<<endl; }else{ compare…
問題はこちら atcoder.jp 方針 番目のマスから順に試していき，最大値が出るたびに暫定の最大値を更新しています。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; vector<long> h(n); for(int i=0; i<n; i++){ cin>>h[i]; } int count=0,count_temp=0; for(int i=1; i<n; i++){ if(h[i-1]>=h[i]){ count_temp++; if(count_temp>count){ co…
問題はこちら atcoder.jp 方針 普通に足すだけ。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; vector<long long> l(n+1); l[0]=2,l[1]=1; for(int i=2; i<=n; i++){ l[i]=l[i-1]+l[i-2]; } cout<<l[n]<<endl; }
ABC124 C - Coloring Colorfully
問題はこちら atcoder.jp 方針 「どの隣り合う 枚のタイルも異なる色で塗」るということは，10101...か01010...のいずれかです。 コード #include <bits/stdc++.h> using namespace std; int main(){ string s; cin>>s; int count_1=0,count_2=0; //10101... for(int i=0; i<s.size(); i++){ if(i%2==0){ if(s[i]=='0'){ count_1++; } }else{ if(s[i]=='1'){ count_1++; } } …
問題はこちら atcoder.jp 方針 回ループを回せば良いのですが， 秒（ 年）かかってしまいます。 対称性があるので綺麗に消えそうだなと思いつつ，与 をそれぞれ ， 回の操作後の を として式をいじっていると， すごいですね。 は に全く関係ないようです。 コード #include <bits/stdc++.h> using namespace std; int main(){ long long a,b,c,k; cin>>a>>b>>c>>k; cout<<(k%2==0 ? a-b : b-a)<<endl; } 補足 ACを通してから， ただし、答えの絶対値が を超える場合は、代…
問題はこちら atcoder.jp 方針 いっぱいループしました。 コード #include <bits/stdc++.h> using namespace std; int main(){ string w; cin>>w; vector<int> count(26); bool check=true; char c='a'; for(int i=0; i<26; i++){ for(int j=0; j<w.size(); j++){ if(w[j]==c){ count[i]++; } } c++; } for(int i=0; i<26; i++){ if(count[i]%2!=0)…
ABC118 B - Foods Loved by Everyone
問題はこちら atcoder.jp 方針 ゴリゴリ調べる。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n,m; cin>>n>>m; vector<int> k(n); vector<vector<int>> a(n, vector<int>(m)); for(int i=0; i<n; i++){ cin>>k[i]; for(int j=0; j<k[i]; j++){ cin>>a[i][j]; } } bool check=false; int count=0,loved=0; for(int i…
5月になりました。みなさんいかがお過ごしでしょうか。 ピカピカの新大学生の私はずっと家にいて，まだ1回しか登校していません。京アニでも見た鴨川の桜がとても綺麗だったのを覚えています。 とは言えいい加減春休みも終わるので，ブログに関係する今やっていること，やりたいことをまとめておこうと思います。 やっていること 読書 今現在，以下の二冊を読んでいます（授業の教科書とサブテキストなんですが…）。 宮崎修一『アルゴリズム理論の基礎』 内田賢德 乾善彦 編『万葉仮名と平仮名: その連続・不連続』 いずれもいい本なので，感想とかを書いて記事にしたいと思っています。特に下の本みたいなやつはこのブログのメイ…
問題はこちら atcoder.jp 方針 「任意の整数 に対して，」「（ の最小値）」です。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; vector<int> p(n); for(int i=0; i<n; i++){ cin>>p[i]; } int temp_min; int count=1; // i=1は常に条件を満たす temp_min=p[0]; for(int i=1; i<n; i++){ if(p[i]<temp_min){ count++; temp_min=p[…
「ブログリーダー」を活用して、shadekyunさんをフォローしませんか？
指定した記事をブログ村の中で非表示にしたり、削除したりできます。非表示の場合は、再度表示に戻せます。
画像が取得されていないときは、ブログ側にOGP(メタタグ)の設置が必要になる場合があります。
