#include <bits/stdc++.h> using namespace std; // rep #define REP(i,a,b) for(int i=a;i<b;i++) #define rep(i,n) REP(i,0,n) struct Edge { int to, cost; }; // typedef typedef vector<Edge> Edges; typedef long long ll; int N; Edges G[2010]; bool notuse[2010]; typedef ll Weight; typedef pair<Weight, int> R…</weight,></b;i++)></bits/stdc++.h>

問題文 本来の授業時間 d が与えられる。授業の開始を t 遅らせるとき、更に t^2 の時間だけ授業時間が少なくなる。授業時間をできるだけ少なくするための t を求めよ。解説 入力が10^18なので普通に線形探索は不可。二分探索しても良いが、整数型で探索範囲…

解法 入力の文字列を next_permutation() して、順に重ねあわせていく。２つの文字列に対して重ね合わせをして、末尾文字列から一致した部分を引いたものを返す関数 concat() を用意した。 #include <bits/stdc++.h> using namespace std; #define REP(i,a,b) for(int i=a;i</bits/stdc++.h>

問題文 http://ch.nicovideo.jp/programing/blomaga/ar583624解答 __builtin_popcount() + 幅優先探索 する。最短経路問題である。 #include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; int const INF = 1<<29; bool vis[10001] = {}; queue<pair<int, int> > q;</pair<int,></bits/stdc++.h>…

問題文 http://yukicoder.me/problems/a14e51c14f78a730解法 DFS + メモ化再帰（＝貰うDP）コメントアウトはBFSでやろうとしてる。最短路をメモしないのでTLEする。 #include <bits/stdc++.h> using namespace std; #define REP(i,a,b) for(int i=a;i</bits/stdc++.h>

問題文 http://ch.nicovideo.jp/programing/blomaga/ar625916解説 まず A, B, C を [1,30] の範囲でそれぞれ全探索し、値を固定する。 dp[i] := A, B, C を用いて整数 i を作るための最小数 として DP すると、V0, V1, V2, V3 のそれぞれについての必要な最…

問題文 http://jag2014autumn.contest.atcoder.jp/tasks/icpc2014autumn_h感想 問題文には左優先で計算すると書いてあるが、自分は初めは、順序は任意に決定されるかつ幾何的制約を満たすものが最終的な解になるのでは、と思ってしまった。以下の参考問題の…

#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) int main() { string str; while(cin >> str) { if(str == "#") break; vector<int> order; rep(i, str.size()) { if(str[i] == 'n') { order.push_</int></bits/stdc++.h>…

解答 根付き木において、頂点 a, b 間を辿る最短パスはの最も近い共通祖先の頂点である。よって LCA を用いて、頂点 a までの深さ + 頂点 b までの深さ - 2*共通祖先の頂点 + 1 が答えとなる。 まだ自力でLCAを書くことが出来ないので蟻本そのままのコードを…

解説 いもす法。 まず一次元で状態が変わる点をイベントとしてみて、カウンタ +1, -1 の増減を設定する。O(N) 累積和を取り、実際の状態の遷移状況を求める。O(N) よって全体で O(N) #include <bits/stdc++.h> using namespace std; #define MAX (1000000) int imos[MAX+10]</bits/stdc++.h>…

解説 状態を２進数値化して考えて、指定の位置にビットが立っているかどうかで N 個の ON / OFF を調べる手技。 X と (1 論理積が 0 でないなら、i 番目にビットが立っている。 #include <bits/stdc++.h> using namespace std; int main() { int N, X; cin >> N >> X; int s</bits/stdc++.h>…

解説 足りない分は b - (a を b で割った余り) である。 数が余らない時は 0 を出力するのに気をつける。 #include <bits/stdc++.h> using namespace std; int main() { int a, b; cin >> a >> b; cout << ((a%b) ? b-a%b : 0) << endl; return 0; }</bits/stdc++.h>

問題文 http://ch.nicovideo.jp/programing/blomaga/ar620922解説（と考えた過程） 有限小数で表せるということは、分子を整数、分母を 10^n で表せるということである。 分母が 10^n すなわち (2^n) * (5^n) で表せるためには、M が 2 または 5 の素因数の…

解説 描画する文字の位置に対応する文字を探してやれば、描画する長方形の範囲の計算量 40000 × テストケース 125 で解ける。 #include <bits/stdc++.h> using namespace std; #define SIZE_N (2*N-1) char change(int x, int y, int N) { int ax = N, ay = N; x %= SIZE_N;</bits/stdc++.h>…

解法 バブルソートの交換回数（反転数）を求める。 バブルソートして求めるか、あるいは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>…

解答 K = 30 までで O(2^K) なので、多少枝刈りすれば通るだろうと思っていたが TLE がなかなか取れなかった。決め手は solve() 関数内の 2行目の枝刈り。条件式を満たすとき今の確率を P倍 と (1-P)倍 に分割する必要がなくなる。コメントアウトしてある条…

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

解説 爆弾の周りの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>…

問題文 サイコロを N 回振ったとき、出た目の積が D の倍数となる確率を求めよ。 1≤N≤100 1≤D≤10^18解説 https://github.com/osak/Contest/tree/master/AtCoder/TypicalDP を見てから自分で書いてみた。サイコロによってできる積の素因数の種類は 2, 3, 5 に…

両者が最大化しながらメモ化再帰 互いに同じアルゴリズムで選択を繰り返している

解法 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>…

問題概要 ３×３のチョコがある。左下端のチョコは毒である。２人でプレイして交互に食べていく。選んだ位置を含めて右上は除去される。左下端を選ばざる得なくなった時点で負けである。初めの状態が与えられるので、最善の手を尽くすとき、はじめはどこを食…

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