AtCoder ProblemsのBoot camp for Beginnersに掲載されている問題を埋めていきたいと思います。言語は基本的にC++(g++)です。自分の復習用に記録していきますが，公開しておけば詳しい方からアドバイスがもらえたりするかもしれないと思って。AtCoder Proble…

問題はこちら atcoder.jp 方針 個のスイッチのon/off状態の順列は 通り，ということで一目全探索っぽいです。 問題では電球→スイッチの対応関係しか与えられないので，スイッチ→電球の対応関係を表す配列を作っています。あとはbit全探索です。 コード #incl…

問題はこちら atcoder.jp 方針 +が入る場所は， の各数字の間 ヶ所です。それぞれの箇所について，+が入っている状態を1，何も入っていない状態を0とすれば，bit全探索が適用できます。 各数式の値を計算するプロセスはコードを見てください。 コード #inclu…

問題はこちら atcoder.jp 方針 購入する参考書の組み合わせが高々 通りしかないところを見るに，全探索で解くのが本命です。 今回は「bit全探索」を用いていますが，この手法を使った経験がなかったのでたどたどしいコードになっています。 コード #include <bits/stdc++.h></bits/stdc++.h>…

問題はこちら atcoder.jp 方針 基本的な動作は，「各マスについて，周囲8マスの爆弾の数を数える」ということですが，端のマスには調べるべき8マスが存在しないので，それをどう処理するかが一つのポイントだろうと思います。 私は，マス目の周囲にダミーの…

問題はこちら atcoder.jp 方針 簡単のため，上の列をマス ，下の列をマス とします。 動き方のパターンは，どの で と動くかの高々 通りしかないので，全部調べればよいです。 コード #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0; i<(n); </bits/stdc++.h>…

問題はこちら 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リットル入</bits/stdc++.h>…

問題はこちら atcoder.jp 方針 数列 は を並び替えたものなので，題意の操作の結果は， となるほかありません。 このとき，置き換えられるべき要素は 以外の 個であり，1回の操作で最大 個の要素を置き換えることができます。 つまり，求める操作回数は，（ …

問題はこちら atcoder.jp 方針 かかる金額が最小になるような買い方は，一番安い冷蔵庫と一番安い電子レンジを買うか，割引券が使える 種類の買い方のどれか，のいずれかです。 コード #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0; i<(n);</bits/stdc++.h>…

問題はこちら 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</int></bits/stdc++.h>…

問題はこちら atcoder.jp 方針 を降順ソートします。このとき， の中から各チームの2番目の人の強さをできるだけ大きくするには， のようにチーム分けをすれば良いです。つまり，求める和は です。 コード #include <bits/stdc++.h> using namespace std; #define REP(i,n) </bits/stdc++.h>…

問題はこちら 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</bits/stdc++.h>…

問題はこちら 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></int></bits/stdc++.h>…

問題はこちら atcoder.jp 方針 直感で解きました。 以下の証明ミスってます。修正中です。 後付けで証明もしておきます。 求める和は， と表せます。ここで，ある整数を で割った余りは （最大でも ）なので， です。 { } { } と並べ替えたとき，これを満た…

問題はこちら 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.subst</bits/stdc++.h>…

問題はこちら atcoder.jp 方針 題意の操作は，文字列 においてBWをWBにすることと同じです。また， がWW...WBB...Bとなった時点で操作は終了します。 つまり，Wに注目すると， 回の操作で つのWが つ左に動き， 中にWが 個あるとき，一番うしろのWが 番目に…

問題はこちら atcoder.jp 方針 円ちょうどの買い物をできるならば，買う品物の数は 個( は の商) とできます1。 個の商品による合計金額 は なので， がこの範囲に含まれているかを判定すればよいです。コード中では余り を用いてやや工夫しています。 解説P…

問題はこちら atcoder.jp 方針 日後に家に戻ってくるためには，旅程にNがあるならばSが少なくとも1つ必要で，SがあるならばNが少なくとも1つ必要です。W,Eについても同様。個数は関係ありません。 コード #include <bits/stdc++.h> using namespace std; int main(){ string</bits/stdc++.h>…

問題はこちら atcoder.jp 方針 特になし。偶奇の場合分けのやり方はいくつかあると思います。 コード #include <bits/stdc++.h> using namespace std; int main(){ string o,e; cin>>o>>e; string password; for(int i=0; i</bits/stdc++.h>

問題はこちら 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</bits/stdc++.h>

問題はこちら 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;></int></bits/stdc++.h>

問題はこちら 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</h;></char></vector<char></char></vector<char></bits/stdc++.h>…

問題はこちら atcoder.jp 方針 「 の末尾を取得し， の先頭に挿入→ の末尾以外を とする」という操作で， を「回転」させることができます。 を回転させて得られる文字列は高々 種類なので， 回の操作後までに と一致するか調べればよいです。 コード #inclu…

問題はこちら 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.b</n;></string></bits/stdc++.h>…

問題はこちら atcoder.jp 方針 「 を辞書順にソート→ を高い順にソート」という方針で解けそうですが，市名，点数，レストランの番号の3変数をどう扱うか。 ということで，tupleを使ってみました。 解説PDF では，pairを入れ子にして3変数を扱っています。ど…

問題はこちら 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;></int></n;></int></bits/stdc++.h>

問題はこちら atcoder.jp 方針 によって税抜き価格のあたりをつけるのですが，int型は小数点以下切り捨てであるという性質上，本当の税抜価格は，a_sup,b_sup以上の整数です。 a_sup,b_sup以上である周辺の整数のうち，条件を満たすものが見つかり次第それを…

問題はこちら 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<</a+i<<endl;></k;></bits/stdc++.h>

問題はこちら atcoder.jp 方針 構造的に難しい点はありませんが，2点間の距離の公式がやや複雑なのでコードもごちゃごちゃしています。 私は整数かどうかの判定は，「int型とdouble型の値が一致するか」，という発想をよく用いるのですが，他にやっている人…

問題はこちら atcoder.jp 方針 「その単語はまだ発言していない単語である」ことと「その単語の先頭の文字は直前に発言した単語の末尾の文字と一致する」ことを確認しています。計算量が少ないので特に工夫はしていません。 コード #include <bits/stdc++.h> using namespac</bits/stdc++.h>…