解法 バブルソートの交換回数（反転数）を求める。 バブルソートして求めるか、あるいはBITするかマージソートするかすればよい。 以下は BIT のコード。 #include <bits/stdc++.h> using namespace std; #define REP(i,a,b) for(int i=a;i<b;i++) #define rep(i,n) REP(i,0,n) typedef long long ll; class BIT { private: vector<int> bit; int size; public: BIT(int </b;i++)></bits/stdc++.h>…

解説 解法が右往左往した問題。 左上半分と右下半分のコストの和を１つのコストとみなして、ダイクストラする。ある状態における最小のコストが更新できなくても等しいのであれば場合の数をカウントする必要がある。その場合にダイクストラの処理を打ち切ら…

解説 爆弾の周りの8方向のカウンタを加算する。実装方法にもよるが、加算する場所が別の爆弾と被らないようにする。 #include <iostream> #include <algorithm> #include <vector> using namespace std; int const dx[8] = {-1,0,1,0,-1,1,1,-1}; int const dy[8] = {0,-1,0,1,-1,-1,1,1};</vector></algorithm></iostream>…

解説 二項加算の繰上げ回数を調べる。加算処理は string よりも vector にするとやりやすいことが多いと思う。 #include <iostream> #include <algorithm> #include <string> #include <vector> using namespace std; int main() { string a, b; while(cin >> a >> b) { if(a == "0" && b == "0") </vector></string></algorithm></iostream>…

解説 平均取って価値を掛けて総和取れみたいなことを言っているが、つまり入力の３つの要素の真ん中を無視して足しあわせろということ。 #include <iostream> using namespace std; int main() { int Tc; cin >> Tc; while(Tc--) { int N; cin >> N; int sum = 0; whil</iostream>…

解法 nHr ＋DP を多倍長整数で実装。 nHr は高校数学によると順列の割り算 or 組合わせから導くことが出来る。

解法 記号を空白に変換して stringstream が吐いた数をカウントする。 #include <bits/stdc++.h> using namespace std; int main() { string s; while(getline(cin, s)) { for(int i=0; i<s.size(); i++) { if(!isalpha(s[i])) { s[i] = ' '; } } stringstream ss(s); int cnt = 0; while(ss >> s) cnt ++; cout << cnt << endl; } return 0; }</s.size();></bits/stdc++.h>

解法 瓶に入れる色を next_permutation で決め打ちする全探索。メモ 瓶とボトルが両方３個なのでわかりにくい？という風な問題。瓶の番号なのか、色つきボトルの入力の並びの番号なのかをはっきりさせる。図に書いても良い。 #include <bits/stdc++.h> using namespace std;</bits/stdc++.h>…

#include<bits/stdc++.h> using namespace std; int main() { for(string s;getline(cin,s);){ for(int i=0; i</bits/stdc++.h>

解法 各データ構造の実際の pop の出力と、入力の出力とを比較する。 push していないのに pop している入力による impossible に注意。 #include <bits/stdc++.h> using namespace std; int main() { int N; while(cin >> N) { queue<int> q; stack<int> stk; priority_queue<int> pq; vec</int></int></int></bits/stdc++.h>…

解法は自明だが prev = 0 の位置を while の外にしていてバグ取りに時間がかかったなどとは言えない。 #include <bits/stdc++.h> using namespace std; int main() { map<char, int> mp; for(char i='A'; i<='Z'; i++) mp[i] = 0; mp['B'] = mp['F'] = mp['P'] = mp['V'] = 1; mp['C'] </char,></bits/stdc++.h>…

まだ考え中。現時点で二回練習に出ている。 続きを読むをすると、多くの人が書く正答コードが見られる。

問題 完全数かどうかを判定する問題。AOJ にも AtCoder Beginner Contest にもほぼ同じ問題がある。 #include <cstdio> using namespace std; int main() { int N; puts("PERFECTION OUTPUT"); while(scanf("%d", &N) && N) { printf("%5d ", N); int sum = 0; for(i</cstdio>…

解法 先に計算すべき配列の要素が、どれも i より小さくなるので、順に計算できる。 #include <cstdio> #include <cmath> using namespace std; #define MAX (1000001) #define MOD (1000000) int x[MAX]; int main() { x[0] = 1; for(int i=1; i</cmath></cstdio>

概要 非負整数 n が与えられる。x. y, z を非負整数として、x+2y+2z = n となるパターン数を求めよ。 ただし n 解答 TLEにならないように一重ループ以内で解きたい。x+Y=n と書き換えると、Y は偶数である必要性が生じる。よって問題文を以下のように解釈し…

概要 問題が足りなくて No problem なのか、問題のストックが十分にあって No problem なのかを出力する。 問題が足りなかった月には一切のコンテストが開かれないので問題は消費しない。その月に作った問題は来月以降にコンテストに出すことが出来る。 #inc…

#include <bits/stdc++.h> using namespace std; int main() { int N, M; while(cin >> N >> M && (N|M)) { vector<int> vec(N); for(int i=0; i<N; i++) { cin >> vec[i]; } int sum = 0; for(int i=0; i<M; i++) { int x; cin >> x; sum += binary_search(vec.begin(), vec.end(), x); } cout << sum << endl; } return</m;></n;></int></bits/stdc++.h>…

問題概要 n の偶奇で計算を分ける。整数 i と j を含む間の数の中で計算を繰り返した結果 1 になる回数が最大のものを求めて、その回数を出力せよ。解答 UVa の中で最も手を付けられるだろう問題の割にはメモ化再帰しないと恐らく解けない。 奇数の計算をし…

問題 首都(ノード1)から他の都市(ノード2〜n)にアクセス可能なように辺を建設する。各辺に建設コストがあり、建設に使える総コストは K 以内に収める必要がある。各ノードに人口が与えられるので、首都にアクセス可能な人口を最大化せよ。解法 アクセス可能…

解法 問題文に載っているコードのままでも通るが、同じ計算の無駄を省いて少し高速化する。(0.019秒) #include <bits/stdc++.h> using namespace std; int main() { int G[510]; G[0] = 0; for(int i=1; i<501; ++i) { G[i] = G[i-1]; for(int j=1; j</bits/stdc++.h>

解説 この問題では 1 は素数として扱っている。 #include <bits/stdc++.h> using namespace std; #define REP(i,a,b) for(int i=a;i<(int)b;i++) #define rep(i,n) REP(i,0,n) inline bool isPrime(int x) { int y = x; for(int i=2; i<=sqrt(x); i++) { if(y % i == 0) ret</bits/stdc++.h>…

以下のコードで解ける問題 #include <bits/stdc++.h> using namespace std; int main() { for(long long a,b;cin>>a>>b;){ cout << llabs(a-b) << endl; } return 0; }</bits/stdc++.h>

解法 テストケースごとに辞書順で出力する必要がある。順序の基準は、大文字小文字の区別なしで辞書順ソート、同じ文字なら大文字が小文字より先に来る。元の文字列のままだと、アスキーコードが早い順でソートされてしまい、必ず大文字が小文字より先に来て…

解法 クォーテーションを交互に切り替えるので、フラグ管理をすればよい。 #include <bits/stdc++.h> using namespace std; char buf; int main() { bool flg = 0; while(~scanf("%c", &buf)) { if(buf == '"') { if(!flg) { printf("``"); } else { printf("''"); } flg ^=</bits/stdc++.h>…

解法 ソートして、O(N) 程度の貪欲。反省 入力で [ max(0, X-R), min(L, X+R) ] と端を切る処理が抜けていたためずっとTLEしてた。 int L, G; int solve(vector<pair<int, int>>& vec) { int l = 0, r = 0; int idx = 0; int cnt = 0; while(1) { while(1) { if(G <= idx ||</pair<int,>…

概要 与えられた無向グラフを、与えられた有向グラフ（片方向の向きを削ったもの）にしたとき、有向グラフの任意の二点の距離は A*x+B（xは無向グラフの距離）以内に収まるかどうか判定せよ。解法 ワーシャルフロイドをそれぞれのグラフについて行った後、任…

問題 入力のの順番で、グリッドを渦状に埋め尽くすようにボールを埋める。ただし同じ列は同じ色である必要がある。 グリッドのサイズを N*M としたとき、最大の N+M を求めよ。条件を満たす N,M が存在しない場合は -1 を出力せよ。解法 ぐるぐる巻きを実装…

問題概要 三角形が与えられる。九点円の中心と半径を求めよ。解法 三角形の各辺の中点を通る円を求めればよい。 中点は３つあるので、３点を通る円を垂直二等分線の交点から求める。 #include <iostream> #include <algorithm> #include <complex> #include <cstdio> using namespace std; typedef </cstdio></complex></algorithm></iostream>…

解法 位置をソートして、隣との幅が W 以内かを見ていく、かつ芝を端まで刈れているかを調べるだけ。 #include <bits/stdc++.h> using namespace std; #define REP(i,a,b) for(int i=a;i<(int)b;i++) #define rep(i,n) REP(i,0,n) #define allof(c) (c).begin(), (c).end() </bits/stdc++.h>…

#include <iostream> using namespace std; int main() { int N; while(cin >> N && N) { long long dp[55] = {}; dp[1] = dp[2] = 1; for(int i=1; i<50; i++) { dp[i+1] += dp[i]; dp[i+2] += dp[i]; } cout << dp[N] << endl; } return 0; }</iostream>