問題 完全数かどうかを判定する問題。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>

解答 全探索。Sの先頭からとprefixの末尾からの一致と、Sの末尾とsuffixの先頭からの一致をみるループを回せばよい。反省 誤読しまくってやばかった。

概要 非負整数 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 Tc; cin >> Tc; while(Tc--) { int Tcnt; cin >> Tcnt; vector<int> vec(15); for(int i=0; i<15; i++) cin >> vec[i]; int ans = 0; for(int i=0; i</int></bits/stdc++.h>…

#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 の中で最も手を付けられるだろう問題の割にはメモ化再帰しないと恐らく解けない。 奇数の計算をし…

問題 フィボナッチ数列の mod M をとる。数列で出来る周期の長さを求めよ。 フィボナッチ数列が 0 からはじまるものと考えた時、周期ははじめから見て次に 0, 1 が現れるときで区切れる。（部分列の最後が 1, 0 であるともみれる）反省 適当な数値や素数を用…

問題文 http://ch.nicovideo.jp/programing/blomaga/ar612968解答 #include <iostream> #include <cmath> #include <vector> using namespace std; #define allof(c) (c).begin(), (c).end() int main() { int N, K; cin >> N >> K; vector<int> ns(N); for(int i=0; i<N; i++) cin >> ns[i]; cout << *ma</n;></int></vector></cmath></iostream>…

問題 首都(ノード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>

解法 誤差のない解法を目指す。 #define INF (1<<29) #define EPS (1e-9) class ArithmeticProgression { public: double minCommonDifference(int a0, vector <int> seq) { if(seq.empty()) { return 0.; } for(int i=0; i</int>

解法 開始時間の全探索なのだけれど問題文読めなくて自力で出来なかった。 class Embassy { public: int visaApplication(vector <int> forms, int dayLength, int openTime) { int N = forms.size(); int ans = INF; rep(st, dayLength) { int sum = 0; int time</int>…

解説 この問題では 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,>…

問題 与えられた 整数 N(32-signed integer. 1解法 ビット化して辞書順で次に現れるビット列を持つ数字が答え。editorial解。反省 はじめビットの小さい桁から見て 1 と 0 とを一度入れ替える、みたいなことして解こうとしていた。next_permutation() を一回…

#include <iostream> #include <vector> #include <algorithm> #include <set> using namespace std; struct Edge { int to, cost; }; typedef vector<Edge> Edges; typedef vector<Edges> Graph; typedef long long ll; typedef pair<ll, ll> Pll; int N; int p[810]; // p[0] no use ll allcost, delcost; Graph G;</ll,></edges></edge></set></algorithm></vector></iostream>…

概要 与えられた無向グラフを、与えられた有向グラフ（片方向の向きを削ったもの）にしたとき、有向グラフの任意の二点の距離は 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>…

解法 dp[文字数] := 覚えている呪文全てを考慮したとき、新しい呪文の先頭から文字数分の文字列を生成する場合数 反省 自分で文字を決めるとき、 N, M とかだと字面が似てて間違えやすい。本番は以下の NEWSIZE を M と書いていて、そのバグで詰まっていた。…

解法 一行目の色は適当に決定して構わない。一行目の決定に従う形で二行目以降は繰り返しに色が定まっていく。これは蟻本の反転と同じ要領の考え方。今、色を決めようとしている場所 (j, i) は、既に決定した上のマス (j, i-1) の色が成立するように帳尻を合…

問題文 http://ch.nicovideo.jp/programing/blomaga/ar604305解法１ 繰り返し二乗法を適用する。 #include <iostream> #include <algorithm> using namespace std; typedef unsigned long long ull; #define MOD (1000003) ull pow(ull x, ull n) { if(n == 0) return 1; ull ret </algorithm></iostream>…

問題文 http://ch.nicovideo.jp/programing/blomaga/ar607615解法 WF + 全探索（中継点決め打ち）類題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2200 #include <iostream> #include <algorithm> using namespace std; #define REP(i,a,b) for(int i=a;i<(int)b;</algorithm></iostream>…

DFS UVa12291 Polyomino Composer http://uva.onlinejudge.org/contests/283-a53db897/12291.html上を読解ミスして考えてた問題に近いもの UVa12292 Polyomino Decomposer http://uva.onlinejudge.org/contests/283-a53db897/12292.htmlUVa12295 Optimal Sym…

解法 位置をソートして、隣との幅が 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>…