想定誤解法らしい．(システムテストに目をつけられたら落ちそう．) 解法 上下の歯は独立しているので，上の歯14本だけを考える． あらかじめ，歯の状態間の遷移確率を計算しておく． 配るdp[年齢][歯の状態(bit表現)]をする．20・2^14・2^14(≒5.3x10^9)でΩ\…

何か解けちゃった． 解法 最大値を伝搬させていく．mx[n] := お菓子n個から最大何個とれるかとする． 最初はmx[n] = nとする．各iに対して， mx[j] = max(mx[j], mx[j+V[i]]) (jはj と更新する． iの選ぶ順序を工夫しなければならないが，T[i]+V[i]の大きい…

3^n系だ．いい問題だと思います． 解法 全探索． 左上から右下に走査し，染められている場所を探す． その場所を(x, y)とすると，そこを染めるには (x, y+1)から「小」を垂らす (x+1, y+1)から「中」を垂らす (x, y+2)から「大」を垂らす の3通りがある．こ…

コードがやばい． 解法 (x, y) -> (x+y, x-y)という変換(45度回転)をすると，施設iと施設jの距離は max{|x[i]-x[j]|, |y[i]-y[j]|} と表されます．以下，変換後の座標系で話をすすめます． まず，x座標とy座標で幅の広い方(最小値と最大値の差が大きい方．同…

これは解ける．223.84pt(Practice) 解法 まず，各整数がgoalをつくるのに使えるかを調べる． 整数nがn | ~goal = 0を満たすならば，nはgoalをつくるのに使える． (等式を満たさないならば，goalにない1の立つビットができてしまう．) 満たす整数のORをとり，…

やるだけ． Flick Input(AOJ 2417) 時代を感じる． #include <iostream> std::string table = " kstnhmyr", table2 = "aiueo", table3 = "TLURD"; int main(){ std::string S, T = ""; std::cin >> S; for(int i=0;i</iostream>

ふんふむ． 解法 かたまりで見る． 例. ooxox -> oxox， xoooox -> xox (1) かたまりが1つ(o, x) 両者はパスするしかないので，そのかたまりの色の方が勝つ．(2) かたまりが偶数個 oが勝つ．(3) かたまりが奇数個 端っこの色のほうが勝つ． 例. oxoxo -> oの…

うさぎ社会の闇． 解法 やるだけ． コード #include <cstdio> int main(){ int N, K; scanf("%d %d", &N, &K); int M[50], bunny[50][50]; for(int i=0;i</cstdio>

やるだけ． 解法 bitDP． コード たまにはループで． #include <cstdio> #include <algorithm> int T[16][17], T_[1<<16][16]; int dp[1<<16][16]; int main(){ int N; while(scanf("%d", &N), N){ for(int i=0;i</algorithm></cstdio>

毎回どうだっけってなる． 解法 1本ずつ直線を足していく．(今までの直線(正方形の辺を含む)と加えた直線の交点)-1だけ領域が増える．但し，正方形内にない交点は含まない． 重複して数えないよう注意する．例えば， から のように直線を加えたとき，交点は3…

ミナリンスキー和． 解法 n>=mとして一般性を失わない．(必要なのは白か黒かという区別だけである．) (1) n=1のとき m=1である．点は重ならないといっているので，適当な直線で分けられる．(2) n=2のとき m=1ならば，黒の2頂点を結ぶ線分内に白い点が入って…

軽い実装ゲー．コピペを頑張る． 最初に やはり今頃感がある． std::string table[10] = {"", ".,!? ", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; 解法 実装する． コード #include <iostream> std::string table[10] = {"", ".,!? ", "abc", "def"</iostream>…

REだったけど，何かstd::cinつかったらできた． 解法 言われたとおりにシミュレーションする． コード 元がC言語で書いてたものだから，C++って感じしない． #include<cstdio> #include<cstring> #include<iostream> #define FOR(i,a,b) for(i=(a);i<(b);i++) #define REP(i,j) FOR(i,0,</iostream></cstring></cstdio>…

ふむふむ． 解法 各xに対し，T-E コード #include <cstdio> int main(){ int N, T, E; scanf("%d %d %d", &N, &T, &E); for(int i=1;i<=N;i++){ int x; scanf("%d", &x); int t; for(t=0;t</cstdio>

iteratorはミスるなあ． 解法 簡単な構文解析(というほど大げさじゃない？) コード #include <iostream> #include <vector> #include <algorithm> #include <cstdio> typedef std::string::const_iterator State; std::string S; int solve(State& s){ s++; if(std::isdigit(*s)){ int n = 0; for(</cstdio></algorithm></vector></iostream>…

いい感じのシミュレーション． 解法 シミュレーション． コード #include <cstdio> #include <algorithm> const int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1}; int H, W = 5; int map[10][5]; int main(){ while(scanf("%d", &H), H){ for(int i=0;i</algorithm></cstdio>

立命館は(どこにあるか知らないレベルで)遠かったので，家から参加しました． 結果はABCDの4完でした． A(Soccer) 問題文はちゃんと読みましょう． 解法 言われたとおりに書く． コード #include <cstdio> #include <cmath> typedef long long ll; ll F0[100], X0[100], Y0[</cmath></cstdio>…

やるだけ． 解法 100,000より大きい正四面体数はいらない．100,000以下の正四面体数は180個で，そのうち45個が奇数である． 数が少ないので，個数制限なしリュックサックナップサック(2015/10/15訂正)問題っぽく解ける． コード #include <cstdio> #include <vector> const i</vector></cstdio>…

計算ミスってた． 解法 幾何+DP． 2円の交点の求め方 円Aと円Bの交点を求める． 上図のように点をとる．AP，BP，ABの長さは既知であることに注意する． このとき，AHとPHの長さが分かればいい． 三平方の定理より ここで，より，連立方程式 が得られる．AHに…

C++さまさま．# 解法 全列挙する．std::set，std::reverseをつかうと楽． コード #include <iostream> #include <set> #include <algorithm> std::set<std::string> set; int main(){ int N; std::cin >> N; while(N--){ std::string S; std::cin >> S; set.clear(); int L = S.size(); for(int i=1;i</std::string></algorithm></set></iostream>

やるだけ． 解法 10^6以下の素数が高々80,000個なので，小さい方から順にa+nd(nは非負整数)の形で表されるかを調べていき，n個目を出力すればいい． コード #include <cstdio> #include <vector> bool isNotPrime[1000001]; std::vector<int> primes; int main(){ primes.push_bac</int></vector></cstdio>…

ちょっと悩んでしまった． 解法 半径1の円がある1点を含むためには，その円の中心がその1点を中心とする半径1の円内になければならない． よって，与えられた点を中心とする半径1の円をつくり，最も重なっているところの円の個数を求めればいい．*1 コード A…

やるだけ． 解法 (どの都市にいるか, 馬券の使用状況)を頂点にしてDijkstra法をする． コード #include <cstdio> #include <vector> #include <queue> #define mp std::make_pair typedef std::pair<int,int> Pair; typedef std::pair<double,Pair> Q; const double INF = 1e20; int N, M, P, A, B; int T[</double,pair></int,int></queue></vector></cstdio>…

やるだけ．# 解法 言われたとおりに書く．最初のカードの状態(下から1,2,...,N)に注意する． 1-indexedで書くと楽かも． コード #include <cstdio> #include <algorithm> int main(){ int N, R; while(scanf("%d %d", &N, &R), N || R){ int cards[51], _a[51]; for(int i=1;i<=</algorithm></cstdio>…

むひゃー． 解法 非負整数nの最右ビットをrms(n)で表す．ただし，rms(0) = 2^30とする． 例. rms(5) = 1 (5 = 0b101)，rms(6) = 2 (6 = 0b110) (n>0ならば，このrms(n)はn & -nと書ける．BITでおなじみ．) 位置sにいるとき，i級快速(iは1rms(|s|)を満たす整…

RE．Ω＼ζ°)ﾁｰﾝ． 解法 経験値は100より多くあっても意味がないことに注意する． dp[i][j] := 樹の残りの耐久力がi，自分の経験値がjのときから何回で樹を倒せるか． これはO(DN)(定数に100がつく)で更新できる． コード #include <cstdio> #include <cstring> #include <algorithm> int D</algorithm></cstring></cstdio>…

多倍長書くだけ． 最初に 以下の文字列をコピペするといいかも．(問題文からコピペできるといいなあ) const std::string units[] = { "", "Man", "Oku", "Cho", "Kei", "Gai", "Jo", "Jou", "Ko", "Kan", "Sei", "Sai", "Gok", "Ggs", "Asg", "Nyt", "Fks", …

やるだけやなあと思ったら，範囲外参照． 解法 記録の数が50,000件以下なので，記録についてループを書けばいい． コード S，T，Eのサイズを50,000にすると，範囲外参照でWAが生えます．ﾅﾆｿﾚｲﾐﾜｶﾝﾅｲ． #include <cstdio> #include <cstring> int main(){ int N, M; scanf("%d </cstring></cstdio>…

やるだけ． 解法 言われたとおりに書く．再帰で書くときはAを優先することに注意する． あとは慈愛で通りそう． コード #include <iostream> int J, Y; void rec(int j, int y, std::string s){ if(j == J && y == Y){ std::cout << s << std::endl; return; } if(j ==</iostream>…

Volume 0がついに残り1問(Blur)．