問題 http://poj.org/problem?id=2719解法 4を抜かして数える は 4->5 5->6 6->7 7->8 8->9 と置き換えた9進数で数えることと同じと考える。 つまり、与えられた数の各位に4より大きい数があれば、その位の数から1を引き、できあがった数を9進数とみて10進数…

問題 http://poj.org/problem?id=2704解法 ゴールから逆にたどるように考えるといい。ゴールの方から道をみると下のような漸化式が成り立つ。a[i][j] := そのマスに書いてある数字 dp[i][j] := そこの場所からゴールまで行き方の総数dp[N-1][N-1] = 1 dp[i][…

POJ 2104 を http://www.graco.c.u-tokyo.ac.jp/icpc-challenge/index.php?2010%2F%C6%FC%C4%F8%C9%BD%2F01-17 のスライドを参考にして解こうとしたけどうまくできなかった コードの残骸だけ載せておく(一部分) void init(int d, int l, int r){ if(l == r-1…

解法 やるだけ #include <cstdio> #include <algorithm> using namespace std; const int MAX = 10; int a[MAX+4][MAX+4]; int lx[13]={-2,-1,-1,-1,0,0,0,0,0,1,1,1,2}; int ly[13]={0,-1,0,1,-2,-1,0,1,2,-1,0,1,0}; int mx[9]={-1,-1,-1,0,0,0,1,1,1}; int my[9]={-1,0,1,-1,</algorithm></cstdio>…

問題 http://poj.org/problem?id=2739 はじめ英語の問題文の解釈を間違っていて、 (連続していなくてもいいと思って動的計画法とか試していた) 1時間ぐらい無駄にしてしまった。解法 10000以下の素数の個数は P=1229個だから可能な連続した素数の和をすべて…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0114解法 (x,y,z) = (1,1,1) を {x' = a1*x mod m1 {y' = a2*y mod m2 {z' = a3*z mod m3 で計算していくと、再び(1,1,1)になるという条件から xだけでみたとき、xが再び1になるまでの計算回…

問題 http://poj.org/problem?id=2709 #include <cstdio> #include <algorithm> using namespace std; int main(){ int N; while(scanf("%d", &N), N!=0){ int p[N], g; for(int i=0;i<N; i++) scanf("%d", &p[i]); scanf("%d", &g); while(g > 0){ sort(p, p+N); p[0]++; p[1]++; p[2]++; g--; } sort(p,p+N); printf("%d\n"…</n;></algorithm></cstdio>

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2011解法 T日にスケジュールのあいている子孫の集合をCtとする 子孫cがT日に持っている地図の集合をMctとするMct = Mc(t-1) (c ∈ Ct でない) ∪{Md(t-1) | d ∈ Ct} (c ∈ Ct) を計算していって…

じりきで解けなかった。 漸化式作るのむずかしすぎ(頭悪い) #include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 15; int N, M; int cup[MAX_N]; int main(){ while(scanf("%d %d",&N,&M)&&N!=0){ for(int i=0; i<3; i++){ int K; scanf("%d", &K);</algorithm></cstdio>…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2005 #include <cstdio> #include <algorithm> using namespace std; const int INF = 1<<29; const int MAX_N = 100; int N,M,S,G0,G1; int cost[MAX_N][MAX_N]; int min_cost[MAX_N][MAX_N]; int wf(){ for(in</algorithm></cstdio>…

地道にシミュレーションする。 時間ギリギリだった #include <cstdio> #include <algorithm> using namespace std; int main(){ int N; while(scanf("%d",&N) && N!=0){ int stone[N]; for(int i=1; i<=N; i++){ int t; scanf("%d", &t); if(i%2==1) stone[i-1] = t; else{ for(</algorithm></cstdio>…

yarudake #include <cstdio> #include <cstring> using namespace std; int main(){ char str[11], c; int N, len; char ring[11]; scanf("%s", str); scanf("%d", &N); int ans=0; for(int i =0; i</cstring></cstdio>

問題 http://poj.org/problem?id=2707解法 ほとんどやるだけ 両方とも横長か縦長に揃えて考えるといい。 あとは場合分けを気をつける #include <cstdio> #include <algorithm> using namespace std; int x1, y1, x2, y2; void swap(int *a, int *b){ int t; t = *a; *a = *b; *b</algorithm></cstdio>…

明日テスト…… 簡単なやつをやったテーブルを作るだけの簡単なお仕事 #include <cstdio> using namespace std; const int d[11][7]={ {0,1,1,1,1,1,1}, {0,0,0,0,1,1,0}, {1,0,1,1,0,1,1}, {1,0,0,1,1,1,1}, {1,1,0,0,1,1,0}, {1,1,0,1,1,0,1}, {1,1,1,1,1,0,1}, {0,1</cstdio>…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0213解法 全探索すればいいらしい。実装キツい。 #include <cstdio> #include <algorithm> using namespace std; typedef pair<int,int> P; const int MAX_N = 15; const int MAX_XY = 10; int N, X, Y; int memo[MAX_N];</int,int></algorithm></cstdio>…

PCK本選に向けての練習 1日1ACを目標にしている。問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0211解法 d[i], v[i] のときの周回数を m[i] 回とし、周回時間 d[i]/v[i]*m[i]=T 時間とする(Tは一定の値) このとき (m[i]=) T*(v[i]/d[i]) …

http://poj.org/problem?id=1948自力で解けなかった。 なんか、頭いい方法でDPするらしい。 こんなループのまわし方はどうやったら思いつくのだろうか。 #include <cstdio> #include <math.h> #include <algorithm> using namespace std; const int M_N = 40; const int M_L = 40; int N</algorithm></math.h></cstdio>…

PCK参加しました。 bitDP気づいたけど実装力なさすぎでバグりまくったのが悔しい 本選参加できるかどうか微妙(地域枠) 今はコード手元にないから今度のせる(追記) コードはどっかいったPOJ 1936部分文字列かどうか判定する問題 再帰書くだけでよい solve(p, …

コンパイルエラーに悩んでいたらただ using namespace std; を書き忘れただけっていう。 早解きの練習が必要。 712 -> 715 (+3) #include <cstdio> #include <iostream> #include <algorithm> #include <vector> #include <string> using namespace std; class XorBoardDivTwo{ public: int theMax(vector <string></string></string></vector></algorithm></iostream></cstdio>…

スーパーコンはレベル高すぎで、ついていけなかったです…。SRM554に参加しました 解法の勘違いしてEasyしか解けなくて人権ない #include <cstdio> #include <algorithm> using namespace std; class TheBrickTowerEasyDivTwo{ public: int find(int rC, int rH, int bC, int bH)</algorithm></cstdio>…

JOI予選のとき、動的計画法ということには気づいたけど頭悪いのでどうすればよいか分からなかった問題。 教訓：とりあえず再帰関数 問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0568 解法 動的計画法またはメモ化再帰をつかう。 メモ化…

JOI予選のとき、問題文を読む前からあきらめてしまった問題。 今回やってみたら20分でできた。成長したなー。問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0569解法 六角形の移動先配列を持ちながら深さ優先探索 #include <cstdio> #include <algorithm> usi</algorithm></cstdio>…

プログラミングしてて、データを可視化して画像にしたいなーとか思って調べてみた。 bmp は圧縮されてないしなーとか思ってたら、png画像が良さそうなことが分かる。 pngの仕様を調べる え、もしかして圧縮も自前でやらないといけないの？ どんなpngも思いの…

問題 http://poj.org/problem?id=1922 解法 途中で別の人に追い抜かれてからスピードあげるぐらいなら、 最初からその人でいいだろが、という話。 出発時間が負の人には追い抜かれることはないから無視して構わない。 #include <cstdio> using namespace std; int ma</cstdio>…

問題 http://poj.org/problem?id=1915 ナイトの動きで何手で目的地までいけるかを計算せよ解法 BFS 移動先座標を配列で持っておくのがコツ #include <cstdio> #include <algorithm> #include <queue> using namespace std; typedef pair<int,int> P; const int INF = 1 << 29; const int dx[8] =</int,int></queue></algorithm></cstdio>…

解法 座標圧縮+DFS はじめて座標圧縮した。 解説を参考にして解いた #include <cstdio> #include <algorithm> #include <set> using namespace std; const int MAX_N = 1000; int N, h, w; bool a[MAX_N * 2 + 3][MAX_N * 2 + 3]; int dx[4] = { 1, -1, 0, 0}; int dy[4] = { 0, 0, 1</set></algorithm></cstdio>…

問題 花札をシャッフルして、操作を終えたときの一番上を求めよ。 解法 普通にやるだけだった。 調べたら、終わりからシミュレーションするという賢い方法があるらしいので こんどやってみようと思う。 #include <cstdio> using namespace std; int N, R; int cards[</cstdio>…

はじめ、'.'を取り除き忘れていて1WA t1 = "TAKAHASHIKUN" t2 = "Takahashikun" t3 = "takahashikun" main = do ns <- getLine str <- getLine let ws = removedot $ words str putStrLn . show $ foldr (\ cs acc -> if cs==t1 || cs==t2 || cs==t3 then ac…

すごいH本にシーザー暗号がのっていたので、 もっと安全を期すため(?)に多表式暗号を作れるようにしました。 import Data.Char key = [1, 2, 3, 4, 5, 6] decode = code' (map (* (-1)) key) code = code' key code' ky = fst . foldr (\ c (str,n) -> (chr …

問題 解法 最小全域木をつくればいいからプリム法かクラスカル法をつかうといい 僕はプリム法を使いました。 #include <cstdio> #include <queue> #include <vector> #include <algorithm> using namespace std; const int MAX_N = 100; const int INF = 1 << 30; typedef pair<int, int> P; //(cost, v) </int,></algorithm></vector></queue></cstdio>…