問題 グラフ上のノード番号が2つずつ入力される。前者から後者のノードへは有向辺が伸びているものとする。このグラフがひとつの木になっているか判定せよ。なお入力は複数のテストケースからなり、0 0がそのケースの入力の終わりを表し、2つとも負の数が与…

問題 n x mの市松模様が与えられる。右下が白の場合はc = 1、黒の場合はc = 0である。 8 x 8のチェスボードはこの中にいくつあるか返せ。 やりかた チェスボードを模様の中で動かすことを想定すると、チェスボードの左上が動ける範囲は、模様の左上から(n - …

問題 n(1自然数の個数を求めよ。 やりかた 包除原理。 nの素因数p[]を求めておく。するとnと互いに素でないn未満の自然数の数は、をn未満のp[i]の倍数の集合とするとで求めることができる。これは包除原理をもとにすぐ計算できる。(Kはnの素因数の個数)以下…

問題 素因数が2,3,5,7のみであるものをHumble Numberという。n番目のHumble Numberを出力せよ。(1 やりかた setにhumble numberを突っ込んでいって一番小さいものから取り出してそれらに2,3,5,7をかけてもう一度setに突っ込んで、また一番小さいものから取り…

問題 N人にM枚ずつカードが配られる。カードには1〜N*Mまでの数字が書かれており、重複はない。各人は毎ターン一枚のカードを場に出し、一番数字の大きいカードを出した人がそのターンの勝ちになる。あなたに配られたカードがわかっているとき、あなたが最低…

問題 素数が2つ与えられる。素数のいずれかの桁の数字を一つ書き換えて別の素数に変える操作を、与えられるひとつ目の素数から始めて、ふたつ目の素数に到達するまで行う。最短の操作回数を求めよ。ただし与えられる素数はともに4桁の素数で、経由する素数も…

問題 マジシャンが1からnまでの数字が書かれたn枚のカードを次のような手順で場にディールしていく。1回目はカードデッキの一番上の1枚をデッキの一番下に移し、新たに一番上になった一枚をディール。 2回目はカードデッキの一番上の2枚をデッキの一番下に移…

問題 symbol = valueという形で変数が与えられるので、その変数を解に持つ最も簡素な形式の数式を出力せよ。 やりかた 最も簡単な形式はsymbol = valueという式そのもの以外にないのでそのまま出力すればいい。要は標準入力をそのまま標準出力にだせばいいだ…

問題 2以上10000以下の整数nが与えられる。nを連続する素数の和で表したい。何通りの方法があるか求めよ。素数一つで表せる場合も該当する。 やりかた エラトステネスの篩をして10000以下の素数の数列を求めておき、それらの部分数列の和を全列挙して該当す…

問題 4以上の整数は2つの素数の和で表せる、という予想をゴールドバッハ予想という。4以上2^15以下の整数nが与えられるので和がnとなるような素数の組数を返せ。ただし(p1,p2)という組と(p2,p1)という組を別々に数えてないけない。 やりかた エラトステネス…

問題 2000年1月1日からの経過日数が与えられる。何年何月何曜日か出力せよ。 やりかた 2000年からはじめて、その年の日数を計上していき与えられた数を超える年が答えとなる年。（コードでは数から日数を引いていき0以下になるとこで止めている） で、与えら…

問題 http://poj.org/problem?id=1338 2,3,5のみが素因数の数をUgly number という。便宜上１もUgly number とする。n番目のUgly number を求めよ。n やりかた プライオリティキューに生成した数を入れていきながら幅優先探索。要long long。 setに発見した…

問題 http://poj.org/problem?id=2262４以上の偶数は２つの奇素数の和で表せるという予想をゴールドバッハ予想という。入力nに対しそのような２つの奇素数を返せ。複数ある場合は絶対値の差が最大になるペアを返せ。 やりかた エラトステネスの篩をしたあと…

問題 http://poj.org/problem?id=1583 文章が与えられる。最も出現頻度が高い単語を列挙し、かつ頻度を求めよ。 やりかた 連想配列に放り込んでいき、最頻度のstringを保存していけばいい。 int main(){ string s, t; while(cin >> t) s += (t + " "); strin…

問題 http://poj.org/problem?id=1455 n人が車座になって座っている。一回の席交換で隣り合う二人が入れ替わる。はじめとは逆順に座るためには席交換を最小で何回行えばいいか。 やりかた n人を半分こしてそれらごとにひっくり返せばいい。 1234|5678 → 4321…

問題文DP強化週間。猫がN匹いる。3種類の命令が存在し、それが「g i」ならi番目の猫の持つピーナツをひとつ増やす。「e i」ならi番目の猫が持つピーナツの数をゼロにする。「s i j」ならi番目とj番目の猫が所有するピーナツを交換する。これらの命令が１セッ…

問題文DP強化週間。街がN個あり、すべての街の間を移動するのに必要な交通費の情報が与えられる。またi日目にjの街にいたときにもらえる金額の情報が与えられる。M回移動するとしたときに得られる最大の金額を求めよ。という問題。dp[j][i]:=(i回移動した後…

問題文DP強化週間。配列が与えられ、毎ターン配列の先頭か最後尾から数字を取り出せる。Tターン目に取り出した数字がaだとすると得点T * a が得られる。全ての数字を取り出したときの最大の得点を求める問題。下の図のように dp[i][j]:=(配列の左からi個、右…

問題文DP強化週間。整数の数列SとFが与えられる。S+Fの部分和の最大値を計算する。しかしそのときのSの部分和、Fの部分和ともに0以上でなくてはならない。という問題。dp[i+1][j]:=(数列のi番目まででSの部分和がjである時のFの部分和の最大値)でDP。メモリ…

問題文となる自然数の組をa 単純に探索すればいい。TLEが怖かったのでなるべく外側ループで探索を少なくした。 int main(int argc, char **argv){ int n; scanf("%d", &n); for(int d = 2; d <= n; d++){ for(int a = 2; a < n; a++){ if(a > d) continue; f…

問題文長さnの数列が2つ与えられる（a,bとする）。この2つの数列の数字同士を全てカップリングさせてaの方の数字が大きれば+200点。bの方が大きければ-200点。得点を最大化せよ、という問題。DP強化週間のつもりが貪欲。=の時をうまく扱えずに人の答えを見て…

問題文DP強化週間。文字列が2つ与えられる。それらの文字列の適切な位置に文字を挟む、消去する、文字を変えるなどして、2つの文字列を同じにしたい。そのために必要な処理の回数を求める問題。要は編集距離。 dp[i+1][j+1]:=(文字列1のi番目と文字列2のj番…

問題文長さPの数列が与えられて偶数秒にはその数列から数字を選んで足す、奇数秒には選んで引く。これを0秒から始める。i+1秒で選ぶ数字はi秒で選んだ数字より数列中で後のものでなくてはならない。最大和を求めよ、という問題。DP強化週間のつもりが、たん…

問題文DP強化週間。問題概要は簡単なので略。問題も小さい方からメモ化して計算していくだけ。 以下ソース。 int a[500001]; int main(int argc, char **argv){ a[0] = 0; set<int> rec; for(int i = 1; i <= 500000; i++){ int t = a[i - 1] - i; int u = a[i - </int>…

問題文DP強化週間。2つのテキストが与えられる。LCSを求めよ。という問題。LCS長のdp表をジグザグと左上に進んでいき、その添字i,jのときに2つに単語s[i],t[j]が等しければ出力。そうでなければdp長が短くなる方向に移動。 こちらを参考にさせていただいた。…

問題文DP強化週間。K種類のブロックがある。種類iのブロックは高さhi、個数ci個ある。 そして様々なブロックを下から積み上げて行った時、この種類のブロックは 必ずai以下に置かれていなくてはならない。積み上げることのできるブロックの 最長の長さを答え…

問題文DP強化週間。長さNの数列が与えられる。数字間を+か-で計算していき、 その結果がKで割り切れるか調べよ、という問題。いかにもなDP。雪だるま式に書くより、メモ化再帰の方が直感的だった。他の人は雪だるま式に書いてるとこが多いみたい。 dp[i+1][j…

問題文DP強化週間。一列に兵が並んでおり、ここから何人か除いた時に、 残りの兵いずれもが少なくとも隊列の左右のどちらかの 端(端の兵ではない)が見通せるようにしたい。端が見通せる条件は 端までに自分より同じか背の高い兵が一人もいない時とする。 取…

問題文DP強化週間。stringが2つ与えられる。LCS長を求めよ。dp[i + 1][j + 1]:=(文字列1のi番目までと文字列2のj番目までのLCS長)でDP。以下ソース。 int dp[1001][1001]; int main(){ string s, t; while(cin >> s >> t){ memset(dp, 0, sizeof(dp)); int N…

問題文DP強化週間。花がF種類あって、一列に並んだ花瓶がV個ある。 花iは花i+1より左側の花瓶に活ける必要がある。 花の種類と各花瓶に対応した点数が与えられる。 点数を最大化せよ。という問題。dp[i + 1][j + 1]:=(花iまでを花瓶jまでにいけた時の最大の…