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

class RevealTriangle { public: vector <string> calcTriangle(vector <string> Q) { int N = Q.size(); int cnt; do { cnt = 0; for(int i=0; i</string></string>

解法 メモ化再帰 class RandomSort { public: map<vector<int>, double> mp; double getExpected(vector <int> permutation) { if(mp.count(permutation)) { return mp[permutation]; } double ret = 0.; double cnt = 0.; for(int i=0; i</int></vector<int>

class TheLuckyNumbers { private: int solve(long long n, int a, int b) { if(n > b) return 0; return solve(10*n+4, a, b) + solve(10*n+7, a, b) + (a<=n&&n<=b); } public: int count(int a, int b) { return solve(0, a, b); } };

解法 与えられたデータを用いたとき、最大の対象な分割のための線分の数を求める。 要素数が8までなので、next_permutation で回して累積和を取り+50となる要素のペアを数え上げる。 #define ALL(x) (x).begin(), (x).end() class SymmetricPie { public: in…

以下のコードは他の人の解答を参考にした。 int ps[3], pr[2], now[3]; bool cards[53]; int main() { while(1) { memset(cards, 0, sizeof cards); for(int i=0; i<3; i++) cin >> ps[i], cards[ps[i]] = true; for(int i=0; i<2; i++) cin >> pr[i], cards…

解法 カタラン数を求めるとよい。 http://mathworld.wolfram.com/CatalanNumber.htmlWikipediaの格子状の経路数え上げの項目が参考になる。Nを1増加して計算したうえで、はじめの経路分を引けばよい。 class FIELDDiagrams { public: ull nCr(ull n, ull r){…

解法 テストケースが書いていないが、３点より特定した一つの円の周上に１点が乗っかるか調べる O(N^4) の解法で正答できるようになっている。３点から一つの円を特定する方法は垂直二等分線の交点である。 ２点のペアの中点と、その２点のペアのベクトルを9…

解説 乗数決め打ちして二分探索で解こうとしていたけど、乗数の大きい物から計算していけばその必要はなかった。2^60 = 1.1529215e+18 > 10^18 は覚えておいたほうが良い。 また、桁落ちを考慮してEPSを挟む必要がある（正答コード見てわかりました） class …

解法 計算量が3*10^9くらいになるので嘘解法かもしれないが、いもす法で解いた。 #include <bits/stdc++.h> using namespace std; #define MAX (1000000) int main() { int N, M; while(cin >> N >> M && (N|M)) { int arr[MAX+1] = {}; for(int i=0; i<N; i++) { int s, t; cin >> s >> t; arr[s] ++;</n;></bits/stdc++.h>…

解法 #include <bits/stdc++.h> using namespace std; int main() { int K; while(cin >> K && K) { int N, M; cin >> N >> M; for(int i=0; i<K; i++) { int X, Y; cin >> X >> Y; if(N == X || M == Y) { cout << "divisa" << endl; } else { if(N < X && Y > M) cout << "NE" << endl; if(N > X && </k;></bits/stdc++.h>…

解法 dp[MICROの作業をした日数][GOOの作業をした日数][連続日数][現在取りかかっているプロジェクト 0 or 1] := パターン数 としてメモ化再帰。 #include <bits/stdc++.h> using namespace std; typedef long long ll; int D, G; ll memo[35][35][35][2]; ll solve(int mfi</bits/stdc++.h>…

解法 直径を大きい順にソートして(1)r,b,r,b,... or (2)b,r,b,r,...の順で貪欲でつめる。red or blue の要素で直径が H 以上のものが尽きたら -1 を出力。そうでなければ長方形の残りの幅を越えた時点で最適。(1)と(2)の小さい方が答え。 class ColoringRect…

概要 簡易的なXMLを解析せよ。タグに複数のプロパティが割り当てられている場合があるので、クエリで呼びだそうとしているプロパティが存在するものならその値を、存在しないなら代わりに "Undefined" を出力せよ。解法 木を作って走査するだけ。 #include <bits/stdc++.h> </bits/stdc++.h>…

#include <bits/stdc++.h> using namespace std; #define ALL(x) (x).begin(), (x).end() class AmebaDiv1 { public: int count( vector <int> X ) { int N = X.size(); set<int> st1(ALL(X)), st2; for(int i=0; i</int></int></bits/stdc++.h>

問題概要 K個以上の座標を完全に包含できる正方形の最小面積を求めよ。制約 座標の要素数：2〜100個 -10^9 解法 与えられた座標のうち「『1点の座標(X, Y)』または『2点の x, y それぞれの min を取った座標(X, Y)』」から一回り大きい座標(X-1, Y-1) を始点…

解法 与えられた配列をソートしたとき、要素 0 番目から順に見てある要素の猫までは右に進み、ある要素の猫からは左に進む。その区切りの位置を全探索する。 #include<bits/stdc++.h> using namespace std; #define INF (1<<29) #define ALL(x) (x).begin(), (x).end() #def</bits/stdc++.h>…

問題概要 はじめからある 1文字を「コピー」「ペースト」「1文字削除」の三操作を用いて、目的の個数にする最小操作回数を求めよ。解法 dp[i] := i個の文字が描画されるための最小操作回数 j ( 1 #include<bits/stdc++.h> using namespace std; #define INF (1<<29) class E</bits/stdc++.h>…

問題概要 'P'のみで作られる長方形区間の面積の最大値を求めよ。ただし、K回まで 'A' または 'P' を取って '.'(空) に置く操作ができる。解法 1. 全ての 'A', 'P', '.' の数を数える。 2. 全ての長方形Rを全探索する。 3-1. '.' が全体の正方形のグリッドに…

解法 ソートして累積和とった上で全探索。O(N^2) 元の配列に番号付けがされているが、全ての番号の数だけ最小のフロアを集めるので番号付けに意味がなく、いきなりソートして良い。 #include <bits/stdc++.h> using namespace std; #define INF (1<<28) class BuildingHeigh</bits/stdc++.h>…

解法 個数制限なしナップサック問題を3パラメータそれぞれについて解く。割と問題文読解ゲー。 配列を再利用すると、0-1ナップサックと個数制限なしナップサックの違いはループの方向のみとなる（蟻本） という意味を確認しておく。0-1の場合は、j のループ…