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


POJ 1975 Median Weight Bead

問題 1からNの数字が書かれたビーズがある。2つビーズについての重さの関係の情報がM個ある。N個のビーズのうち重さが中央値になりえないものの個数を求めよ。 やりかた 一種のトポロジカルソート。自分より重いビーズに辺を張って、重さの関係をグラフに置…

POJ 2513 Colored Sticks

問題 両端にそれぞれ色が塗られている棒が複数与えられ、色が同じ棒の端同士を連結して一本の棒にすることができる。与えられた棒をすべて連結することはできるか答えよ。 やりかた やっていることはしりとりと同じ。各色をグラフ上の頂点とみなし、棒を辺を…

POJ 2472 106 miles to Chicago

問題 無向グラフの情報が与えられる。始点から終点まで辺のコストをかけ合わせたものがパスのコストになる。コストを最大化せよ。 やりかた 辺のコストにlogをかければコストの積を和に変換できる。あとはただの最小経路問題。以下ソース。 //ダイクストラの…

POJ 1855 Mint

問題 数種類の長さの棒がある。各種類とも棒は無尽蔵にあるとして良い。棒をつなぎ合わせて4本足の机を作る。各足は同じ種類の木を使い、4本の足の長さが揃うように作る時、決められた高さ以下で作れる最高の高さと、決められた高さ以上で作れる最小の高さを…

POJ 1905 Expanding Rods

問題 長さLの鉄線をn度で熱すると長さがL*(1+n*C)に変化する。Cは膨張係数である。この鉄線を向かい合わせの壁に取り付けて熱すると膨張して弧を描くようにしなる。熱したときの鉄線の中心部の縦方向への変位を求めよ。 やりかた 弧になったときの弧長をL'、…

POJ 1505 Copying Books

問題 要素数mの数列をk個の連続する数列に分割する。分割したそれぞれの数列の要素の和を計算し、そのうち最大となる値を最小化するように数列を分割したい。この条件をみたすように数列を分割して出力せよ。ただし複数の分割方法がある場合には、分割したは…

POJ 1985 Cow Marathon

問題 無向木の情報が与えられる。同じ辺を2度辿らないように頂点間を移動する時、もっとも距離の遠い2点間の距離を求めよ。 やりかた 無向木の直径を求める問題に他ならない。直径の求め方は、てきとうな頂点から深さ優先探索を始めて最遠の頂点uを求める。…

POJ 3510 A Tale from the Dark Side of the Moon

問題 文字列が一行ずつ与えられる。一行ごとに以下の処理を行って出力せよ。 アルファベット小文字とスペース以外は削除 "dd"という文字列があったら"p"に変換("ddd"という入力はないものとする) "ei"という文字列があったら"ie"に変換(ただし直前の文字…

POJ 1129 Channel Allocation

問題 頂点と辺の情報が与えられる。最小で何色で頂点を塗ることができるか答えよ。 やりかた 四色定理から必ず4以下になる。 色を数値で管理して、深さ優先探索でグラフを探索する。探索中に次に訪れる点に隣接している点の色で使っていない色のうち、最も値…

POJ 3233 Matrix Power Series

問題 nxnの行列Aが与えられる。S=A+A^2+A^3+...+A^kを計算し、各要素をmで割ったあまりを求めよ。 やりかた 行列の累乗は繰り返し二乗でできるとしても単純にやったら確実にTLEする。なのでうまく分割統治しつつメモ化しておくことで通すことができる。数列…

POJ 2601 Simple calculations

問題 という漸化式の数列がある。が与えられるのでを求めよ。 やりかた (たぶん嘘解法) に対してがmonotonicalに変化するからに関して二分探索すればいいんじゃまいか(・∀・)!! で通ってしまった。よく考えるとmonotonicalじゃないような。 実験すると一般項…

POJ 2505 A multiplication game

問題 StanとOllieが掛け算ゲームをして遊ぶ。数字を1から始めて毎ターン2から9までの好きな数字をかけていく。数字が与えられた数n以上になった時、そのときのプレーヤが勝ちとする。Stanからプレーを始めて交互に行う。両者が最適にプレーする時、必勝はど…

POJ 2499 Binary Tree

POJ

問題 (1, 1)という値を根に持つ完全二分木があり、各ノード(仮に(a, b)とする)からは左に(a + b, b)という値を持つ子、右に(a, a + b)という値を持つ子が伸びている。 (x, y)というノードから親を辿りながら根まで行くときに左側に移動する回数と右側に移動…

POJ 2613 Choose and divide

問題 二項係数同士の除算C(p,q)/C(r,s)を行い、小数点第五位までを出力せよ。p,q,r,sは10000未満で、答えは常に1e7を超えないとしてよい。 やりかた 素直にやると精度が落ちて誤差死する。なので優先度付キューを2つ用意して式の分母と分子の数字をそれぞれ…

POJ 1450 Gridland

POJ

問題 デカルト座標上にnxmのグリッドがある。グリッドの格子点では上下左右の格子点に加え対角線方向のグリッドにも移動できる。このnxmの格子点について巡回セールスマン問題を解け。 やりかた 巡回セールスマン問題なのでnxm回の辺の移動がある。なので問…

POJ 2248 Addition Chains

問題 要素が一つだけの数列a(a[0] = 1)からはじめて、数列a中の任意の2つの要素の和を取り、それが最終項より大きい場合に最終項の後ろにくっつけるという操作を繰り返して、入力として与えられるnをつくりたい。 操作回数が最小であるときの、最終的な数列…

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の素因数の個数)以下…

POJ 2247 Humble Numbers

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

POJ 1323 Game Prediction

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

POJ 3126 Prime Path

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

POJ 3032 Card Trick

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

しょげないでよBaby 眠れば治る