問題文 正整数w, h(1 解のW, Hはともに150以下であることが保証されているので1以上150以下でH ペアの比較はC++ならpairを使うと最初から比較が辞書式順序になっているので楽です。 #include <iostream> #include <vector> #include <map> #include <algorithm> using namespace std; typedef p</algorithm></map></vector></iostream>…

問題文 模擬国内予選2012問題Bとよく似た問題でコンテストの提出履歴が与えられた時にICPCルールで順位付けをしてチーム番号を順位の高い方から出力します。C++なら比較関数を用意してソートするとよいです。この問題では順位が同一のときには、それらのチー…

問題文 括弧の始まり('[')が来たときに再帰呼び出しをしてその括弧の始まりに対応する括弧の終わり(']')が来た時にその選挙区で必要な最小の得票数を計算してその結果を返せばよいです。 第 1 段階の有権者数で必要な最小の得票数は有権者の過半数の票なので…

問題文 1から m まで(1 素数の個数が最大の経路を求め, その個数と最後に通った素数を出力します。ある整数が素数かどうかO(1)で判定できるようにエラトステネスの篩等で最初に素数を列挙しておきます。次に螺旋状に数字を書きます。バグりやすいので気をつ…

問題文 一つの杭と紐に注目したときに風船が動ける空間は球になっています。(正確にはzn個の杭と紐につながった風船が動ける空間はそれぞれの杭と紐について注目した時に動ける空間の共通部分となっていて、その形は凸になっています。(球は凸集合で、凸集合…

問題文 N*Nの行列で行の中で最大で、列の中で最小のものを求める問題です。 そのような要素がないときは0を出力します。 #include <iostream> #include <vector> #include <map> #include <algorithm> using namespace std; typedef pair<int,int> P; int main(){ int n; while( cin >> n , n ){ // m[y]</int,int></algorithm></map></vector></iostream>…

問題文 整数v, dが与えられます。 v個のノードがあり番号が1..vまで付けられています。ノードiとノードjについて|(f(i)-f(j)) mod 1001| 異なる集合の数を求めます。Union-Findを使うと良さそうな問題でした。 #include <iostream> #include <algorithm> using namespace std; con</algorithm></iostream>…

問題文 史跡と史跡の間に灯篭を100m間隔でおき、すべての史跡がつながるようにしたとき、必要最小限の灯篭の数を求める問題です。灯篭の数をコストと考え、史跡と史跡の間に灯篭をおくとき((史跡と史跡の距離)-100)/100が必要なコスト(灯篭の数)となります。…

問題文 1から9の整数a,b,c,dと演算子+,-,*を使って10になる式を探して出力する問題です。 4つの数字の並び替えが4!=24通り 3種類の演算子を3箇所につかうので3*3*3=27通り括弧のつけかたは( (a+b)+(c+d))と(((a+b)+c)+d)と*1+d)の3通りを試しましたが通りま…

問題文 x,y,zがそれぞれ何回で1に戻ってくるか計算し、その回数をa,b,cとするとa,b,cの最小公倍数が答えになるようです。long int(32bit)ではオーバーフローするので注意が必要です。 #include <iostream> using namespace std; typedef long long int ll; ll gcd(ll a</iostream>…

問題文 覆面算の問題です。Xの部分に0-9のどれかの数字が入るので10通り調べるとよいです。数値に変換するとオーバフローするので文字列のまま足し算しましょう。多倍長整数が標準で存在する言語だと楽ができることでしょう。 #include <iostream> #include <string> #include <algorithm></algorithm></string></iostream>…

問題文 入力された整数nに対しnグラムのそば粉を買うときの最小の金額を求める問題です。入力される範囲が[500,5000]と小さく、すべて100の倍数なので初めに計算しておくとよいです。 #include <iostream> #include <algorithm> using namespace std; const int INT_MAX = 1e+7; i</algorithm></iostream>…

問題文 1,2, ... , NのチーズがN個あり、1から順に食べるとき全部のチーズを食べるのに必要な最短経路を求める問題です(Nは9以下)。必ず全てのチーズが食べられることが保証されているようです。またフィールドの幅と高さw,hは1000以下となっています。幅優…

問題文 探索する必要はなくシミュレーションする問題です。 毎回下端に届いたパッケージの記録からpush_down 命令かpush_right 命令をするか判断します。 最終的に上のラインと左のラインが空になったら右のラインに届いた順に出力します。 今回は文字列でデ…

問題文 n以下で最大の双子素数を求める問題です。エラトステネスのふるいであらかじめ素数を求めておきましょう。 #include <iostream> using namespace std; const int MAX = 100001; char p[MAX] = {0}; int main(){ for(int i=2 ; i < MAX ; i++ ) p[i] = 1; for(in</iostream>…

問題文 AN個の戦闘機とBN個の敵弾があり、それぞれの戦闘機について距離が4*R以内にある敵弾を数える問題でした(距離は戦闘機の中心座標から敵弾の中心座標までの距離で計算)。AN,BN 各戦闘機について自分のいる区画とその周囲8区画だけ調べるようにすると調…

問題文 A = {a[1] , a[2] , ... a[n] }について 回数が|A|/2より多く出現する数字を出力する問題です。(|A|は要素数) #include <iostream> #include <map> using namespace std; int main(){ int n, a; while( cin >> n , n ){ map<int,int> m; for(int i=0 ; i < n ; i++ ){ cin >> </int,int></map></iostream>…

問題文 全探索で解ける問題です。幅優先探索でも深さ優先探索でも解けると思いますが、今回は深さ優先探索で解きました。同じ状態を再び探索しないようにメモしながら探索しました。2枚のカードを取り出したときカードを移動させる処理が少し煩わしいと感じ…

問題文 [1,n]のうちa*i+b*jで表せない数が何個あるか数える問題です。入力a,b,nは10^6以下の整数でi,jは非負整数です。動的計画法で解ける問題でした。dp[x] := 整数xをa*i+b*jで表すことができるかどうか(0 or 1)で計算しました。dp[0]を1で初期化し、iを0…

問題文 DPで解く問題です。ボードが数字であるとき、その数字の後ろに右か下の位置の数字をつなげることができます。dp[y][x]にボードの(x,y)の位置からつくることのできる最大の数字が入るように計算していきます。右下からDPテーブルを埋めて行きましょう…

問題文 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>…