解いた問題のソースコードと解説など。


POJ

POJ 2348 Euclid's Game

問題 2つの自然数が与えられ、この自然数についてStanとOllieがゲームを行う。プレーヤは大きい方の数から小さい方の数の倍数を引いて相手プレーヤに渡すことができる。ただし、大きい方から小さい方の倍数を引いて残った数は0以上にならなければいけない。…

POJ 1917 Automatic Poetry

問題 "s1<s2>s3<s4>s5" という形式の文字列が与えられる。もう一つ "s..." という形式の文字列が与えられる。元の文字列からカッコを取り除いた文字列と、もう一つの文字列を "ss4s3s2s5" という形式に直したものを出力せよ。 やりかた Javaであれば正規表現を使える</s4></s2>…

POJ 1384 Piggy-Bank

問題 複数種類の硬貨があり、その重さと価値が与えられる。重みの和がちょうどE-Fになるように硬貨を取り出したときの価値の和を最小化せよ。硬貨は各種類とも無尽蔵にあるとしていい。 やりかた dp[i]:=(重みの和がiであるときの価値の最小値)でDP。硬貨j…

POJ 1606 Jugs

問題 ビーカーAとBの容量Ca、Cbが与えられる。ビーカーに水を入れる操作を行って、どちらかのビーカーに入っている水がNになるようにしたい。行ってよい操作は以下の6種類である。 Aいっぱいに水を入れる Bいっぱいに水を入れる Aを空にする Bを空にする Aの…

POJ 1107 W's Cipher

問題 アルファベットとアンダーバーからなる文字種を[a-i]、[j-r]、[s-zと_]の3グループに分ける。 文字置換による文章の暗号化を行いたい。暗号化の方法は平文の文字を一つずつ見ていき、その文字がグループiに属する時、その文字の右側を見ていって、グル…

POJ 1753 Flip Game

POJ

問題 4x4のオセロの盤面が与えられる。盤上の石を一つひっくり返すと4近傍の石もひっくり返るとする。すべての石が同じ色になるために必要なひっくり返す動作の最小回数を求めよ。どうひっくり返しても達成できない場合は"Impossible"を出力せよ。 やりかた …

POJ 3869 Headshot

問題 リボルバー式の拳銃があり、シリンダー内の弾の装填の情報が与えられる。ロシアンルーレットで遊ぶとして、どの薬室からスタートしたかわからないが相手の手番では発砲しなかった。次の番はあなたで、そのまま打つか、シリンダーをランダムに回転させて…

POJ 2626 Chess

問題 チェス大会のチーム編成を考えたい。各チェスプレーヤについて、白チームとして戦った場合の強さと黒チームとして戦った場合の強さの2つが与えられる。30人以上のプレーヤの強さが与えられる。これらプレーヤから選抜で白チーム15人、黒チーム15人の編…

POJ 2253 Frogger

問題 x,y座標が幾つか与えられる。0番目の点から1番目の点に向かって、直接、もしくはその他の点を経由しながら移動する。点から点へのジャンプにかかるコストは点と点のユークリッド距離で表される。移動中にかかる最長のコストを最小化せよ。 やりかた 二…

POJ 2033 Alphacode

問題 アルファベット大文字からなる平文に対し、A=1、B=2、…、Z=26と置き換える暗号化を行う。この暗号文は一意に復号化できない可能性がある。暗号文が与えられるので何通りの復号化があるか求めよ。 やりかた DP。 dp[i]:=(i桁目までの復号化パターン数)…

POJ 2121 Inglish-Number Translator

問題 アルファベット表記された数字を英数字に変換して表示せよ。 やりかた 数字をthousand未満、thousandの桁、millionの桁に分けて各桁を英数字に直して、桁の数字をかけて足し合わせた。以下ソース。 int main(int argc, char **argv){ map<string, int> p; p["negativ</string,>…

POJ 1265 Area

問題 ロボットが2次元座標上で原点から出発して左回りに動いて再び原点に戻ってくる。動作は格子点から格子点への直線運動の繰り返しで行われ、毎回の移動量dx, dyが入力として与えられる。この一周の動作で囲われた領域の内部にある格子点の総数、動作した…

POJ 2537 Tight words

問題 [0...k](0 やりかた DP。 dp[i][j]:=(長さiの文字列で最後の文字がjであるようなtightな文字列が発生する割合(百分率))とする。dpでtightな文字列の総パターン数を求めて(k+1)^nで割ることもできるが、C++では多倍長整数を使わないとできないのでこ…

POJ 2954 Triangle

問題 3つの格子点の座標が与えられる。この格子点からなる三角形の内部にある格子点数を求めよ。ただし、辺上の格子点は数えない。また、与えられる三角形の面積は必ず0より大きい。 やりかた ピックの定理を使った。(ピックの定理) 頂点がすべて格子点上…

POJ 2295 A DP Problem

問題 'x'を変数とする1次方程式が文字列形式で与えられる。この方程式をxについて解き、解を床関数にかけたものを出力せよ。ただし解が不定の場合は"IDENTITY"を、不能の場合は"IMPOSSIBLE"を出力せよ。なお入力文字列は空白を含まない。 やりかた 単にやる…

POJ 2005 Blackjack

POJ

問題 トランプがnセット(1セットあたりジョーカーなしの52枚)与えられ、このカードデッキを使ってブラックジャックを行う。 この中からディーラーが1枚、あなたが2枚をランダムにピックアップし、場にお互いが見えるように置く。ディーラーがランダムにも…

POJ 2418 Hardwood Species

POJ

問題 木の名前がいくつか入力される。各木の種類について、それが入力された総数のうち何%を占めているか木の名前のアルファベット順にパーセンテージで出力せよ。 やりかた mapに木の名前と出現数を入れて総数で割って、、、というだけ。入力はgetsを使えば…

POJ 1730 Perfect Pth Powers

問題 整数Xが与えられる。X=b^pを満たすような整数bおよび自然数pが存在するとき、Xをp-th perfect numberという。pの最大値を求めよ。 制約: やりかた 例えばなのでmax(p)=4となるように、Xを素因数分解して、各素因数の指数の最大公約数が答えになる。答え…

POJ 2402 Palindrome Numbers

問題 自然数Nが与えられる。N 1から数えてN番目に出現する回文形式の整数を返せ。 やりかた ある桁数の整数中に回文整数がいくつあるかというと、 1桁:1 ~ 9 9個 2桁:11 ~ 99 9個 3桁:101 ~ 999 90個 4桁:1001 ~9999 90個 5桁:10001 ~ 99999 900個…

POJ 3270 Cow Sorting

問題 要素のスワップを繰り返して数列を昇順にソートしたい。数列中のXとYを入れ替える時のコストをX+Yとする。ソートに必要な最小コストを求めよ。 やりかた 数列を巡回置換のまとまりに分解する。 例えば(3,5,7,4,2,1,6)であれば(3,7,1,6)(5,2)(4)となる。…

POJ 2959 Ball bearings

問題 直径Dの円に内接する複数の直径dの小円を考える。小円同士の中心が少なくともs+d以上離れているように配置したい。最大でいくつの小円を配置できるか。 やりかた 配置する間隔は等間隔にする。間隔は円の個数に対して単調減少なので二分探索できる。C個…

POJ 2437 Muddy roads

問題 一直線の道路上にN個のぬかるみがありそれが[s,e)の形で与えられる(s,eは非負整数)。なお与えられる範囲に重複はない。長さKの木板が無数にあり、これらを使ってぬかるみをすべて覆いたい。最小でいくつの木板が必要か。 やりかた 貪欲。 領域の左端…

POJ 1313 Booklet Printing

POJ

問題 略 やりかた 見開きのページ番号の和はどの見開きであっても一定(ページ数以上の最小の4の倍数+1になる)になるので片一方の番号がわかれば見開きのもう片方の番号は自動的に決まる。コード上では見開き上の若番の番号から老番のページ番号を求めて、…

POJ 1248 Safecracker

問題 やりかた 与えられる文字列の長さはせいぜい12文字なので、全探索でも1ケースあたり程度の計算でOKなので全探索で。 ただvectorやstringを引数に関数の値渡しをすると簡単にTLEしてしまった。参照渡しにしたら簡単に通った。以下ソース。 vector<ll> c(5); </ll>…

POJ 3670 Eating Together

問題 1~3の数字からなる数列がある。この数列を単調非減少もしくは単調非増加にするために書き換える必要のある数字は最小でいくつか求めよ。なお数字は1~3にしか書き換えられない。 やりかた DPでやった。 数列のうちの単調非減少なLISの長さをもとめると…

POJ 3660 Cow Contest

問題 1からNまでのラベルが付いたノードが与えられる。このグラフの有効辺がM個与えられる。トポロジカル順序が厳密に決まっているノード数を返せ。 やりかた トポロジカルソートできるグラフだとして、あるノードのトポロジカル順序が厳密に決まっている場…

POJ 3194 Equidivisions

問題 nxnのマスに1~nまでの数字がn個ずつ割り振られている。同じ数字が割り振られているマスがすべて4-連結しているか判定せよ。入力形式が少しわかりにくくて、各テストケースのi行目が数字iを持つマスのy座標、x座標を連続で表している。テストケースはn-…

POJ 1308 Is It A Tree?

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

POJ 3364 Black and white painting

POJ

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

POJ 2407 Relatives

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

罪を憎んで人は憎まずにセクシー