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

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

以下のコードは他の人の解答を参考にした。 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…

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

解法 計算量が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>…

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

問題文 http://uva.onlinejudge.org/external/119/11954.html解法１ 二項演算子に遭遇するたびに両側区間で再帰する。（普通の構文解析と同じ）1000文字までのビットが存在しうるので、数字は deque で各桁の値(1 or 0)を管理する。単項演算子の優先順位は数…

問題文 http://uva.onlinejudge.org/external/120/12001.html解法 問題の否定を取って全体の場合から引けば O(N^2) で答えが出る。 O(N^4) でも通るみたいだけど、多分それだとコードが書きにくくなる気がする。下で組み合わせは パスカルの三角形のDP でな…

問題文 http://uva.onlinejudge.org/external/119/11955.html概要 二項展開せよ。解法 パスカルの三角形のDP（orメモ化再帰） long long 係数、乗数、文字の場合分け 反省 最大ケースに気をつけよ 場合の数は long long にならないか？今回は関係ないが、確…

問題文 http://uva.onlinejudge.org/external/118/11837.html概要 鍵盤が同じ間隔で打たれているとき、譜面Bは譜面Aのメロディを剽窃した疑いがある。疑いがある場合は 'S' そうでない場合は 'N' を出力せよ。（詳しい内容は本文参照）解法 入力の表を配列に…

概要 プレイヤー二人が交互に対戦する。行列から行を選べるので、その行の要素それぞれについて１以外で割り切れる数の内好きな数で割って良い。一つも割り切れる要素がない場合（つまり行の要素が全て１の場合）その行は選ぶことは出来ない。自分の番のとき…

問題 http://uva.onlinejudge.org/external/118/11863.html解法 区間DP（メモ化再帰）左右から区間を狭めていくだけ。 自分がパスしたら相手もパスするので、パス可能最大回数 K という情報に意味は無い。 数列に42が含まれる場合、ワイルドカードなので、は…

問題文 http://uva.onlinejudge.org/external/117/11795.html概要 "Mega Man" であるあなたは "Mega Buster" を使って敵のロボットを倒していく。ただ "Mega Buster" だけでは全ての敵を倒すことが出来ない。倒した敵から武器を奪い、その武器を使うことで倒…

問題文 http://uva.onlinejudge.org/external/118/11870.html概要 テストで英単語の同義語と対義語の試験が出る。対策の手間を省くために、単語の対義語の対義語が元の単語の同義語である場合、少ない関係を覚えるだけで覚えていない単語同士の関係も導き出…

問題文 http://uva.onlinejudge.org/external/118/11860.html概要 アルファベットの小文字と記号で表された文書がある。一つの単語はアルファベットの小文字以外の文字で区切られる。全ての単語を含む区間を出力せよ。解法 尺取り法で解く。 #define INF (1<…

問題 http://uva.onlinejudge.org/external/118/11833.html概要は原文を確認してください。解法 #include <bits/stdc++.h> using namespace std; #define MAX (250) #define INF (1<<29) typedef pair<int, int> Pii; struct Edge { int to, cost; }; vector<Edge> G[MAX]; int dist[MAX]; i</edge></int,></bits/stdc++.h>…

問題 http://uva.onlinejudge.org/external/118/11813.html概要 無向グラフにおいて、グラフの接続情報とコストが与えられる。 全てのノードの内、店のノード番号が複数指定されるので、ノード0から出発して最小コストで全ての店を巡回せよ。制約 ノードとエ…

問題 http://uva.onlinejudge.org/external/118/11818.html概要 3×3のグリッドが有る。各グリッドは合計12本のスティックで区切られている。鼠とチーズがこのグリッド上のいずれかのマスに存在して、鼠はスティックが外されている部分のみ通過できる。 SOHA…

問題文 http://uva.onlinejudge.org/external/117/11736.html大意 RAMに格納されている変数情報とRAMのメモリが与えられる。複数の変数名がクエリとして送られるので、10進数で変数の値を表示せよ。解法 やるだけ。変数の持つバイト分の文字列を1ビットずつ…

問題 http://uva.onlinejudge.org/external/110/11012.html概要 三次元の座標が与えられる。２点間のマンハッタン距離の最大値を求めよ。制約 テストケース 0 点の数 2 解法 人の解説を聞いてコードを見て書いた。まだ良くわかってない。 #include <bits/stdc++.h> using na</bits/stdc++.h>…

問題 http://uva.onlinejudge.org/external/115/11545.html概要 "S...****................***.D" とかいう感じの道を最短時間で進めという問題。 １マスを１時間で移動することが出来る。 夜は '*' の道を通ることは出来ない。あるマスにいるというのは、そ…

問題 http://uva.onlinejudge.org/external/112/11231.html概要 大きな市松模様のうち、８×８の市松模様はいくつあるか。解法 （実はまだよく分かってない） #include <bits/stdc++.h> using namespace std; int countChessBoard(int n, int m) { n -= 7, m -= 7; if(n < 1 </bits/stdc++.h>…

問題 http://uva.onlinejudge.org/external/111/11124.html概要 奇数段目かつ奇数番目のブロックのみの数字が書かれた積み石がある。最下段の数字以外はパスカルの三角形同様の方式で値が決まるので、全ての数字を特定し出力せよ。解法 積み石の一般の位置に…

問題 http://uva.onlinejudge.org/external/115/11553.html解法 Bobが最善の手を取ってきた前提でAliceの得点を最大化する。 #include <iostream> #include <algorithm> #include <limits> using namespace std; int main() { int grid[8][8]; int Tc; cin >> Tc; while(Tc--) { int N; ci</limits></algorithm></iostream>…

問題 http://uva.onlinejudge.org/external/108/10896.html概要 アルファベットのみがシーザー暗号化された暗号文と、平文の一単語が入力として与えられる。暗号鍵を、平文の一文字を 'a' としたときに暗号化された一文字とするとき、あり得る暗号鍵を全てア…

問題 http://uva.onlinejudge.org/external/109/10950.html概要 アルファベットの小文字1文字に対して数字コードが割り当てられる。暗号化した数字列が与えられるので、平文としてあり得る文字列を全てアルファベット順に列挙せよ。ただし候補が100個以上あ…

問題 http://uva.onlinejudge.org/external/9/979.html意訳 伝説の三角形 MGT が忌まわしき略奪者トライアングルマンによって平面世界に隠されてしまった。三角形は自由に回転、平行、反転がなされている可能性があり、加えて無慈悲にも多数の点の上に紛れて…

問題 http://uva.onlinejudge.org/external/9/983.html概要 N×N の正方行列が与えられる。全ての M×M の部分行列において、各値の和を出力せよ。またそれらの合計も出力せよ。合計は 64bit signed integer に収まるものとする。制約 N 解法 （普通の）二次元…