StarrySkyを解こうとしました． 枝刈りしていないので半分ぐらいTLEします． #include <cstdio> #include <string.h> #include <algorithm> #define X first #define Y second using namespace std; const int MAXN = 4096; typedef pair<int, int> P; typedef pair<P, int> STAR; int N; int cx[MAXN], cy[M</p,></int,></algorithm></string.h></cstdio>…

通っていました。 4が全滅して悲しかった。 1,2,3完+5の部分点(60)で360点 本選ではこんなことにならないようにします。

http://poj.org/problem?id=3252 パスカルの三角形をあらかじめ計算しておく。 まず、((数字の桁数) - 1)桁以下の2進数についてRound Numberを求める。 これは、iを桁数、jを0の個数として iCj - (i-1)C(j-1) の和を計算すればよい。次に(数字の桁数)桁の2進…

easy 和sとして、「和がsになる2つの数字の組合せ」を3つ取ってくる円順列を考えて、sがmax(7,K)から2N-5までの円順列の和を求めればよい。 #include <cstdio> #include <algorithm> #include <vector> #include <string> using namespace std; class FoxMakingDice{ public: long long c3(long </string></vector></algorithm></cstdio>…

1299 -> 1357 easyだけ解けたeasy 2^(最終的な色に関係ある区間の数)を計算すればいい #include <cstdio> #include <algorithm> #include <vector> #include <string> #include <queue> using namespace std; class LittleElephantAndIntervalsDiv1{ public: long long getNumber(int M, vector <int> L, vec</int></queue></string></vector></algorithm></cstdio>…

いもす法をする [a,a]みたいな区間を忘れないようにする #include <cstdio> #include <algorithm> using namespace std; int s[1000002]; int single[1000002]; int main(){ int N; int mi = 1000002, ma = 0; scanf("%d", &N); for(int i = 0; i < N; i++){ int a, b; scanf("%</algorithm></cstdio>…

正方形の2つの頂点を決めてしまってから、残りの2頂点が存在するかを二分探索する #include <cstdio> #include <algorithm> using namespace std; #define X first #define Y second typedef pair<int, int> P; int N; P stars[1000]; int main(){ while(scanf("%d", &N) && N != 0){ int </int,></algorithm></cstdio>…

3完で 1570 -> 1721 (+151) でした 紫色になりましたA 式を簡単にするとソートして最初と最後だけ入れ替えればいいことがわかる #include <cstdio> #include <algorithm> #include <vector> using namespace std; int N; int a[100]; int main(){ scanf("%d", &N); int ma, mi; for(int </vector></algorithm></cstdio>…

解きました 解法 都市の隣接関係のグラフができれば幅優先探索でO(N)で計算できるので、効率よくグラフを構成する方法を考えればいい。 バケット法を使うとうまくいくらしいが二分探索を2d回行うことでもできた。 計算量はO(d N log N) #include <cstdio> #include <vector> </vector></cstdio>…

SuperCon2013 本選に行ってきました。 4位でした。実力は出せたものの詰めが甘いです。 解法は主催者が想定していた通りな感じです。 解法 がんばって逆にたどるだけ GK表とかいう粒子の衝突が起こった時の次の粒子の移動方向の表の変な性質はまったく使って…

easy撃墜されて0pointだった 1225 -> 1194easy N=1のケースで撃墜されるコードを書いてしまった。 DP思いつかない人なので貪欲で解いた。 最大m個の歌を歌えるとして a1, a2, a3, ... , am の歌を歌うのにかかる時間Sは S = Σ(duration) + Σ(wait_time) = Σ(…

問題 http://poj.org/problem?id=1029解法 N枚のコインをそれぞれ偽のコインと仮定したとき矛盾が生じるかどうかで判定する 実装ですこしつまずいた #include <cstdio> #include <vector> #include <algorithm> using namespace std; const int MAX_N = 1000; int N, K; vector<vector<int> > L(100)</vector<int></algorithm></vector></cstdio>…

いまごろですが、通過していました。 西日本のsakataで出場します。 よろしくお願いしますー。 コードと解説をはっておきますコード #include <stdio.h> #include <string.h> #include "sc13.h" #define N 30 #define INF 1000000 int a[N]; int path[N], best, n, path_[N]; in</string.h></stdio.h>…

以前まったく分からなかったが、久しぶりにやってみると解法がすぐ思いついて驚いた。問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0542解法 ある事務所で認証レベルを順番にあげていって、入れる部屋の総数とレベルの表をつくる 最初の…

問題 http://poj.org/problem?id=2019解法 segment tree の二次元版みたいなやつを作ると各クエリに対してO(log N)で処理できる #include <cstdio> #include <algorithm> using namespace std; typedef pair<int, int> P; const int N_ = 256; const int TREE_SIZE = 87381; // A_1 = 0, A</int,></algorithm></cstdio>…

初めての div1 1217 -> 1225 easyだけ解いてなんとかレートを維持した。 いろいろライブラリをつくっていく必要がありそう。easy グラフの連結成分が2つ以上ある場合は無限に差を大きくできる。 連結成分が1つだけのときは2頂点間の最短経路のうち最長の長さ…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0519解法 トポロジカルソートする。 途中で候補の頂点が複数あらわれた場合、順位表が複数ありえる。 O(V+E)だけど実装下手なせいでO(V^2)になった #include <cstdio> #include <vector> #include <algorithm> using nam</algorithm></vector></cstdio>…

1116 -> 1217 青色になりました。 当面の目標は緑に下がらないこと。easy #include <cstdio> #include <string> using namespace std; class SemiPerfectSquare{ public: string check(int N){ bool f = 0; for(int a = 1; a <= N; a++){ for(int b = a + 1; a * b * b <= N;</string></cstdio>…

1015 -> 1115 (+100) DIV1にあと2回ぐらいでなりたいeasy すべてのうさぎの組み合わせに対して、時間が重なっているかどうかをみるだけ #include <cstdio> #include <vector> #include <string> #include <algorithm> using namespace std; class ShoutterDiv2{ public: int count(vector <int> s, ve</int></algorithm></string></vector></cstdio>…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0270 解法 去年のパソコン甲子園の問題。去年の本選のとき解けなかった。 解説にのっているやり方とはちょっと違うやり方でやった。 アルゴリズムは解説のものより log N 倍ぐらい遅いはずだ…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0230 解法 幅優先探索（BFS）する はしごを登ったり、滑ったりする処理をミスってバグりまくった #include <cstdio> #include <algorithm> #include <queue> using namespace std; typedef pair<int, int> P; typedef pair<P, int> PP; in</p,></int,></queue></algorithm></cstdio>…

D言語を使う練習として解いた D言語っぽいことはやっていない import std.stdio; import std.array; import std.conv; void main(){ bool[60000] p; p[0] = false; p[1] = false; for(int i = 0; i < 60000; i++) p[i] = true; for(int i = 2; i * i < 60000…

easyだけ解いた 二分探索してレベルを決定して、コーナーケースに気をつけながら表面積を計算する。 コーナーケースありすぎorz #include <cstdio> #include <algorithm> #include <vector> #include <string> using namespace std; typedef long long ll; class PyramidOfCubes{ public: ll k; </string></vector></algorithm></cstdio>…

917->1014 DIV2で59位でした。easy #include <cstdio> #include <algorithm> #include <vector> #include <string> using namespace std; class DeerInZooDivTwo{ public: vector <int> getminmax(int N, int K){ vector<int> ans; ans.push_back(max(0, N - K)); ans.push_back(N - (K + 1) / 2); return </int></int></string></vector></algorithm></cstdio>…

medの方がeasyより簡単だと思ったkに近い4の倍数と7の倍数は [k/4]*4 [k/4+1]*4 [k/7]*7 [k/7+1]*7 ([x]はガウスの記号(整数型の割り算)) のうちいずれか #include <cstdio> #include <vector> #include <algorithm> #include <cmath> using namespace std; class TheSequencesLevelOne{ public</cmath></algorithm></vector></cstdio>…

ルールを変えたNimでAliceとBobのどちらが必勝かを判定する問題 ルール： 石が1個以上ある山がいくつかある。 プレイヤーは毎回、一つの山から石を1個以上とる。 山は順番に並んでおり、1個以上石が存在する山のうち一番左の山からしか石をとることはできな…

問題 http://poj.org/problem?id=2378 解法 適当な頂点を選んで根にしてDFSして子を数えてやるとできる。 #include <cstdio> #include <algorithm> #include <vector> using namespace std; int N; vector<int> T[10001]; vector<int> ans; int dfs(int p, int q){ int sum = 0; bool f = true; fo</int></int></vector></algorithm></cstdio>…

問題 http://poj.org/problem?id=2456 解法 距離で二分探索。はじめ再帰で書いたが終了条件がよくわからなくてWAになったのでループ回した。 #include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 100000; int N, C; int a[MAX_N]; bool c(int d){ /</algorithm></cstdio>…

問題 http://poj.org/problem?id=1989 (翻訳)K種類の整数N個からなる整数列が与えられるので、その部分列とならない整数列のうち最短のものの長さを答えろ。 解法 整数列の先頭から、K種類の整数が一通り出るところまで進み、さらにその場所からまたK種類の…

昨日の夜、解いた。漸化式むずかしい #include <cstdio> #include <algorithm> using namespace std; const int INF = 1<<29; const int MAX_N = 10000; int N; int a[MAX_N]; int dp[2][MAX_N][2]; int main(){ scanf("%d", &N); a[0] = 0; for(int i = 1; i < N; i++) scanf("</algorithm></cstdio>…