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


POJ

POJ 3494 Largest Submatrix of All 1’s

問題 0と1からなるnxmのマスが与えられる。この中に含まれる1のみからなるx軸とy軸に平行な長方形で最大の長方形の面積を求めよ。 やりかた ヒストグラム内の最大長方形の面積を求めるアルゴリズムを応用する。マスから一行読むごとにこのアルゴリズムを実施…

POJ 3390 Print Words in Lines

問題 N個の文字があり、各文字の文字数が数値として与えられる。文字は与えられた順に(間にスペースを一つ入れて)連結して出力することができ、一行あたり最大でM文字出力する事ができる。ただし文字の途中で改行してはいけない。 出力する各行には(M-行の…

POJ 3275 Ranking the Cows

問題 牛がN匹いて、それぞれの牛の牛乳の生産量は異なっている。2匹の牛の牛乳の生産量の大小を表すクエリがM個与えられる。生産量の順番を確定するために必要になる追加のクエリ数を求めよ。 やりかた 牛がN匹いるとすると順番を確定するための関係はになる…

POJ 2773 Happy 2006

問題 自然数m, Kが与えられる。mと互いに素なK番目の自然数を返せ。 やりかた 逐一調べると当然間に合わない。ここは二分探索+包除原理。まず二分探索で解の候補を上げ、その解の候補に対して、それ以下の自然数でかつmと互いに素なものの個数を計算し、その…

POJ 2420 A Star not a Tree?

問題 二次元座標上に点がN個与えられる。この座標上から一点を指定し、N個の点との距離の総和を最小化せよ。 やりかた 解析的に答えが求まりそうにないので、数理最適化。自分は最急降下法でやった。 選んだ座標をとし、与えられたN個の点の座標をすると距離…

POJ 3422 Kaka's Matrix Travels

問題 NxNのグリッドがあり、各マスに0以上の整数が書かれている。グリッドの左上のマスからスタートして右か下に一つずつ移動して右下のマスまでたどり着きたい。通ったマスの数字は得点となり、一度通ったらそのマスの数字は0になる。K回スタートからゴール…

POJ 3790 Recursively Palindromic Partitions

問題 与えられた自然数を、それ以下の自然数の数列の和で表現する。これを自然数の分割と呼ぶ。回文となるような分割をPalindromic Partitionという。そのうち以下の条件を満たす分割をRecursively Palindromic Partitionsという。 条件:分割の左右それぞれ…

PKU 3182 The Grove

問題 グリッド上に連結した池がある。これをぐるっと回って戻ってくるための最短経路を求めよ。ただし8連結方向に移動できる。 やりかた 通ったけど多分嘘解法。凸包。まず池の周りを4連結で囲むように印をつける。その印にたいして凸包を計算して池を一周す…

POJ 1387 Labyrinth

問題 やりかた 木の直径を求める問題。グラフ上の適当な点からはじめて最も遠い点を見つける。続いてその点から最も遠い点を探すとその間が直径になる。 メモリ量、制限時間ともにシビア。グラフは隣接リストで持たずに、ある頂点に対する4方向の連結情報を…

POJ 1376 Robot

問題 グリッド上の格子点を直径1.6mの円形のロボットがスタート地点からゴール地点まで移動する。グリッドの一部に障害物があり、ロボットを障害物にぶつけてはいけない。ロボットは一回の移動で左右に向きを変えるか、1~3つ分の格子点を直進することができ…

POJ 2341 Spell Checker

問題 アルファベットと.,;:-!?とスペースからなる文章が与えられる.文の区切りは.か!か?である.文章中の不整合な箇所の個数を答えよ. ただし不整合なケースとは以下の2種類を指す. 文頭が大文字でない 単語の途中に大文字がある やりかた 文意を正確に汲…

POJ 2782 Bin Packing

問題 アイテムがN個あり、それぞれの重さが与えられる。これらのアイテムをビンに詰めたいとする。一つのビンにたいして最大で2個までのアイテムを詰められる。このとき必要な最小のビンの数を求めよ。ただし一つのビンに詰めるアイテムの重さの和がLより大…

POJ 3862 Business Center

問題 エレベータがm台あり、各エレベータには昇降用のボタンが2つだけついている。エレベータiの上昇ボタンを押すとu[i]階上がり、下降ボタンを押すとd[i]階下がる。階数は無限にあるが、0階より下の階はない。m台のエレベータのうちのいずれか一台のエレベ…

POJ 2342 Anniversary party

問題 N人のうちから何人かパーティに招待したい。N人には上司部下の関係が存在し、これらは一つの木構造をなしている。(つまり、ある一人にたいして上司はせいぜい一人しかおらず、上司のいない人間はただ一人である) パーティには部下とその直属の上司が…

POJ 2536 Gopher II

問題 n匹のネズミの位置と、m匹のネズミ穴の位置が与えられる。タカがネズミを狙っており、s秒たった時点で穴に隠れていないネズミは捕食される。すべてのネズミは速度vで動くことができ、一つの穴には一匹のネズミだけが隠れることができる。捕食されるネズ…

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回の辺の移動がある。なので問…

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