問題文 4以上の偶数nについて、n=a+bとなる素数の組(a,b)がいくつあるか数える問題です。(2,3)と(3,2)のように順序が逆の組は区別されないので重複して数えないようにしましょう。この問題もエラトステネスの篩で素数表をあらかじめつくっておきましょう。 #…

問題文 n個の組(1,n)(2,n-1)(3,n-2) ... (n-1,2)(n,1)について、2つの数字がどちらも素数の組の数を求める問題です。エラトステネスの篩で最初に素数表をつくっておきましょう。 #include <iostream> using namespace std; const int MAX = 1000001; char p[MAX] = {0}</iostream>…

問題文 (X,Y)の位置に縦H横Wの建物があり、n匹の猫の座標が与えられたときに建物の中にいる猫の数を求める問題です。大小の比較で(x,y)にいる猫がその矩形(建物)のなかに含まれているか調べられます。 #include <iostream> using namespace std; int main(){ int t; ci</iostream>…

問題文 2人が同じ位置に来るのにかかる最小の時間を求める問題です。幅優先探索(BFS)で解くことができます。必要な情報は2人の位置座標と時間です。気をつけることは 2人は逆の動きをする 2人の位置座標が同じ場所の探索をしないようにフラグをたてるのを忘…

問題文 数列(a_1, a_2, ... , a_n)をAとBの2つに分け、Aの総和とBの総和の差が最も少ないときの差を求める問題です。動的計画法を使う問題かと思いきやnが20以下と小さいので深さ優先探索(DFS)で全探索してもAcceptすることができるようです。 #include <iostream> #in</iostream>…

問題文 ICPCのコンテストのチームの選抜に関する問題です。これくらいの問題は簡単に解けないとICPCでは歯が立たないレベルですね。4つのデータ(正解数,ペナルティ,ID,所属)をpair > >を使ってソートします。ソートしたあとは順位のよい方からみていって条件…

問題文 素数に関する問題です。エラトステネスの篩であらかじめ素数表をつくっておくとよいでしょう。 #include <iostream> #include <vector> using namespace std; const int MAX = 1000001; char p[MAX] = {0}; void f(){ for(int i=2 ; i < MAX ; i++ ) p[i] = 1; for(int </vector></iostream>…

問題文 幅優先探索でスタートからゴールまでの最短経路を求める問題です。 入力の数が偶数行と奇数行で異なり、入力がしんどい問題でした。 2年前はきちんとコードが書けなかったのでそう考えると私も成長しているのかもしれません。 #include <iostream> #include <map> #i</map></iostream>…

問題文 問題文をよく読んで全探索する問題です。同じ色でつながっているパネルはDFSで調べるよいでしょう。 5回までパネルの色を変更できますが5回目は目標の色にするとよいようです。(ソースコードではしていない) #include <iostream> #include <vector> #include <algorithm> using nam</algorithm></vector></iostream>…

問題文 ただ実装するだけの問題ですがとても面倒なので落ち着いてコードを書かないとバグが入り込むかもしれません。 #include <iostream> #include <map> using namespace std; typedef pair<int,int> P; int n,m,f[101][101],s[51][51]; bool search(int sx, int sy){ for(int y=sy</int,int></map></iostream>…

問題文 ワーシャルフロイド法で解ける問題でした。 #include <iostream> #include <algorithm> using namespace std; const int INF = 1e+9; int main(){ int n,m; while( cin >> n >> m , n||m ){ int d[2][101][101]; for(int i=0 ; i < 101 ; i++ ){ for(int j=0 ; j < 101 ; j</algorithm></iostream>…

問題文 ワーシャルフロイド法で解くことができる問題でした。 #include <iostream> #include <algorithm> using namespace std; const int INF = 1e+9; int main(){ int n; while( cin >> n , n ){ int d[11][11], v=0, s[11]={0}; for(int i=0 ; i < 11 ; i++ ){ for(int j=0 ; j </algorithm></iostream>…

問題文 ワーシャルフロイド法で解くことができる問題でした。 ダイクストラ法でも解けるようですが、行きと帰りの最小コストだけ分かればよいのでワーシャルフロイド法を使うほうが楽なようです。(ノード数も少ない) #include <cstdio> #include <algorithm> using namespace st</algorithm></cstdio>…