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

#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>

解法 FizzBuzz系の問題 #include <bits/stdc++.h> using namespace std; inline bool inDigit7(int cnt) { stringstream ss; ss<<cnt; return ss.str().find('7') != string::npos; } int main() { int N, M, K; while(cin >> N >> M >> K && (N|M|K)) { int k = 0, cnt = 0; bool S = 1; while(1) { for(int m=(S?1:N-1); (S?m<=…</cnt;></bits/stdc++.h>

問題文 難易度を示す正の整数列が与えられる。この数列から EasyとMediumとHard の問題を選びたい。EasyとMediumの難易度の差とMediumとHardの難易度の差とが出来るだけ近くなるように選べ。複数買いがある場合は、より簡単なEasy より難しいHard より簡単な…

問題文 'A', 'B', 'C' のみの文字を用いて、長さ n の文字列が構成される。文字列のうち、その部分文字列において 'A', 'B', 'C' の文字が順不同で１つずつ連続しているようなものがあるものは、禁止文字列と定義する。禁止文字列でない長さ n の文字列の総…

解法 BITDP。 leading0を除くために数字は先頭から埋めていくと考えてdpの初期状態から i=0 をはじくと良い。ここで結構詰まった。 また、和においてMODを取る問題ではオーバーフロー対策のために数値を加算するたびにMODを取っていくことを忘れない。 #incl…

問題 任意の文字の位置を入れ替えた部分文字列の候補が複数与えられる。 重複を許してこれらを接続して、与えられた元の文を構成するものを考える。そのために部分文字列の文字位置の入れ替えが必要であるが、その回数の総和が最小であるものを答えよ。ただ…

問題文 ある文字列の部分文字列の配列が渡される。この時元の文字列の最小の長さを求めよ。 ただし各々の部分文字列は、それらの先頭の文字の座標が一つ前の部分文字列の座標以上の位置になっている。解法 前の座標を記録しながら部分文字列の一致をみる。は…

解法 いくらかパターンをイメージすると、長いのから順に消費していけば良いことが分かる。 class OlympicCandles { public: int numberOfNights(vector <int> C) { int cnt = -1; for(int i=0; i<C.size()+1; i++) { sort(ALL(C), greater<int>()); for(int j=0; j<i; j++) { if(C[j] > 0) C[j] --; else goto EXIT; } cnt ++; } EX</i;></c.size()+1;></int>…

解法 各々についてDFSして足し合わせる。メモ化すると良い。 typedef long long ll; class CorporationSalary { public: ll memo[55]; ll dfs(vector<string> &R, int idx) { if(memo[idx]) return memo[idx]; ll& ret = memo[idx]; int cnt = 0; for(int i=0; i</string>

解法 先にstringの階層構造をvector化すると扱いやすくなる。 class RelativePath { public: vector<string> make(string str) { int N = str.size(); for(int i=0; i<N; i++) { if(str[i] == '/') { str[i] = ' '; } } stringstream ss(str); vector<string> ret; ret.push_back("ROOT"); while(ss >> str) ret.push_back(str); return ret; } st…</n;></string>