問題文 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テーブルを埋めて行きましょう…