土下座しながら探索中

主に競技プログラミング

AOJ

AOJ 2437 : DNA

問題リンク : http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2437&lang=jp問題概要 : 日本語なので略解法: DP + 半分全列挙で解いたまず、i文字目(1 与えられる文法に含まれる非終端記号間の関係をグラフにするとDAGなので、これは再帰などで…

AOJ 2099 : Walk under a Scorching Sun

問題リンク : Walk under a Scorching Sun | Aizu Online Judge問題概要 : いくつかのの道と建物に加え太陽がある。 道、建物、太陽はそれぞれ線分、凸多角形+高さ、点として表される。道の上にあるある点xと太陽を結ぶ直線が建物と交差するなら、 その点xは…

AOJ 1314 : Matrix Calculator

問題概要 : 問題文で定義されている Matrix Calculator を実装せよ シンタックスはBNFで与えられるMatrix Calculator : 行列計算を行うプログラム Matrix Calculator の機能等を適当に列挙 1. +, -, * : 行列の加算、減算、乗算 2. - : 単項演算子のマイナス…

AOJ 2607 : Invest Master

問題リンク : Invest Master | Aizu Online Judge問題概要: n日間の株価の情報が与えられる 初日にx円所持しているので、株の売買を行い最終日の所持金を最大化せよ 株の売買に手数料はかからないものとする また、最終日の所持金の最大値は高々10^5で…

AOJ 1350 : There is No Alternative

問題リンク:There is No Alternative | Aizu Online Judge問題概要: 重み付き無向グラフが与えられる これに対する最小全域木は複数存在しうるが、それら全ての最小全域木に共通して存在する辺の数とそれらの総和を求めよ解法: Kruskal法を用いてMSTを構築す…

AOJ 1229 : Young, Poor and Busy

問題リンク : Young, Poor and Busy | Aizu Online Judge問題概要 : けんさんは函館に住んでおり、けいこさんは東京に住んでいる けんさんとけいこさんは電車を使って合う予定を立てている 電車の時刻表の情報を持っており、その情報は電車が出発する駅の名…

AOJ 0616 : JOI Park

AOJ

問題リンクJOI Park | Aizu Online Judge問題概要 : 日本語なので略解法 : その通りに計算する 愚直にやると遅いので、全ての辺の重みの総和を求め Xを小さい順に見ていき辺の総和を減らしていく まず、ノード1からdijkstraで各ノードへの最短距離を求める …

AOJ 1325 : Ginkgo Numbers

AOJ

問題リンク : Ginkgo Numbers | Aizu Online Judge問題概要 : Ginkgo Number が与えられる 問題文中で定義されている素数の条件を満たすかどうか判定せよ解法 : 一番下に書いてあるヒント的なものの2つめを使った If · = , then (m2 + n2)(x2 + y2) = p2 + q…

AOJ 2073 : The Phantom

問題リンク : The Phantom | Aizu Online Judge問題概要 : 2次元平面上に2枚の鏡と幽霊がいる 鏡と幽霊はそれぞれ線分と点として表される 鏡に映る幽霊の数を出力せよ ただし、その数が100を超える場合は"TOO MANY"と出力せよ解法 :よくあるビームと鏡の反…

AOJ 2067 : Reading Brackets in English

問題リンク : Reading Brackets in English | Aizu Online Judge問題概要 : S-expression は次のように定義される 1. a list of A は (A) に変換され、 2. a list of A and B は (A B) に変換され、 3. a list of A, B, C, ...,Y and Z は (A B C ... Z) に…

AOJ 2594 : Reverse a Road II

問題リンク : Reverse a Road II | Aizu Online Judge問題概要 : V個のノードとE本の有向辺からなるグラフがある それぞれのノードには1から順に番号が割り振られており、 S番からT番に車をできるだけ多くの車を送る ただし、1つの辺を通れる車は高々1台 …

AOJ 2464 : Magic Walls

問題リンク : Magic Walls | Aizu Online Judge問題概要 : 4個以上1500個以下の2次元座標上の点が与えられる その中から異なる4点を選びlそこから作られる四角形の面積の最大値を求めよ 任意の異なる3点が直線上に並ぶことはないし、 任意の異なる2点が同…

AOJ 2167 : Find the Point

問題リンク : Find the Point | Aizu Online Judge問題概要 : n本の直線が与えられる それら全ての直線への最短距離が等しい点を見つけよ そのような点が複数ある場合は "Many" と出力し、 1つも存在しない場合は "None" と出力せよ解法 :まず、直線が2本だ…

AOJ 2605 : Social Monsters

問題リンク : Social Monsters | Aizu Online Judge問題概要 : N匹のモンスターがいる その中からK匹を選んでチームを作る 任意の2匹のモンスター間には仲良し度があり 仲良し度が0の場合、それらのモンスターを一緒にチームに入れることはできない それ以外…

AOJ 2614 : Almost Same Substring

問題概要 : 略解法 : SuffixArray + LCP + RMQ で頑張った与えられた2つの文字列を結合する その際に間には大きな文字を入れる S = S + "$" + T' + "$" この S の SuffixArray, LCP を作成する LCP 内の区間[a,b)の最小値を求めるRMQを用意する左から1つず…

AOJ 1270 : Manhattan Wiring

問題リンク : Manhattan Wiring | Aizu Online Judge問題概要 : h * w の表に'2'と'3'がそれぞれ2つずつ存在する その他は'0'か'1'である '2'と'2'を、'3'と'3'を線で繋ぎたい ただし、それらの線同士が交差してはいけない 線の長さの和が最小となるように…

AOJ 2480 : Blame Game

問題リンク : Blame Game | Aizu Online Judge問題概要 : Alice と Bob は互いを攻め合いたい Alice は n 個の欠点があり、 Bob は m 個の欠点がある ある欠点は 0 個以上の相手の欠点と関係があり、その関係は双方向に成り立つ Alice と Bob は交互に相手の…

AOJ 0299 : Railroad II

問題リンク : Railroad II | Aizu Online Judge問題概要 : 略解法 : 累積和駅は円状になっているが切り離して直線にし、同じものをもう一つくっつける 例えば 7駅あって0と2と6に訪れる必要があるなら、切り離してもう一つ繋げて 0 2 6 0 2 6 とする それに…

AOJ 0254 : Scone スコーン配達計画

問題リンク:Scone | Aizu Online Judge問題概要: 0以上の整数からなる数列と正の整数mが与えられる 数列の連続する部分列の総和%mの最大値を求めよ解法: BIT + 二分探索した(一時期は全探索で通った) 数列の累積和を求め、それらをmで割った余りがそれぞれ…

AOJ 0253 : Ant Nest

問題リンク : Ant Nest | Aizu Online Judge問題概要 : 略解法 : 重心求めてくるくるしながら二分探索して計算するまず最初に、連続した3点以上が平行であるようなものが入力として与えられるので、それらを圧縮して1つの線分にする各辺について、そこをケ…

AOJ 2624 : Graph Automata Player

問題リンク : Graph Automata Player | Aizu Online Judge問題概要 : 有向グラフが与えられる ( 多重辺なし、自己ループあり ) 有向グラフの各ノードには0か1が書かれている 1秒毎に各ノードの数値を更新する 更新の手順は以下のとおり現在の時刻をtとす…

AOJ 1025 : Building Water Ways

問題リンク : Building Water Ways | Aizu Online Judge問題概要 : 日本語なので略解法 : 枝刈り+バックトラック手順 : * 0から順に水源に番号を付ける * 0から順に水源を伸ばしていく ( 0 を伸ばし終わったら 1 へ...といった感じで ) * 全ての町に水が…

AOJ 2246 : Alice and Bomb

問題リンク : Alice and Bomb | Aizu Online Judge問題概要: 建物、人、爆弾があり、建物は2次元平面上の多角形として、人と爆弾は2次元平面上の点として与えられる 爆弾は爆発すると全方位に爆風が広がる 建物に爆風が当たるとそこでそこの爆風は遮られる…

AOJ 0284 : Happy End Problem

問題リンク : Happy End Problem | Aizu Online Judge問題概要 : 略解法 : DP 答えるものが多角形の頂点番号なので経路復元もしなければならない メモ化再帰でも間に合うと思ったが幻想だった 各点を出力に合わせてソートする 下にあるものほど前にくる 同じ…

AOJ 0236 : Alien Messages

問題リンク : Alien Messages | Aizu Online Judge問題概要 : 略解法 : 枝刈り探索 まず、初期状態で次数が1のマスが存在したら No 空のマスの数を数えてその数が奇数だったら No これらに該当しない場合はDFSで探索する h*wのブール型の2次元配列を用意し…

AOJ 2537 : Billiard

問題リンク : Billiard | Aizu Online Judge問題概要 : (0,0)が左下で(w,h)が右上となるような長方形があり、 その内部にn個の半径rの円がおいてある それらは1から順番に番号が割り振られている 1番のボールを(vx,vy)方向に打つ 打たれたボールは10000秒間…

AOJ 2095 : Nagashi Soumen

問題リンク : Nagashi Soumen | Aizu Online Judge問題概要 : (x,y,z)からなるN個の点があたえられる 最大K本の線をひけるのだが、N個の点全てがK本の線のいずれか1つに属するように線を引かなければならない 尚且つ2つの点p1,p2を結ぶ際に、p1.z > p2.z …

AOJ 2121 : Castle Wall

問題リンク : Castle Wall | Aizu Online Judge問題概要 : 単純多角形が与えられる 自分はこの多角形の2頂点を選んで新たに辺を付け加えることができる これを0回以上行うことができるのだが、その際に追加した辺の長さの総和がr以下でなければならない この…

AOJ 2042 : So Sleepy

問題リンク : So Sleepy | Aizu Online Judge問題概要 : S個の駅とT個の電車がある 各電車は決められた時刻に決められた駅を出発し、決められた時刻に次の駅に到着する 自分が最初いる駅とその時刻、最終的に行かなければならないランデヴーである駅と集合時…

AOJ 1288 : Digits on the Floor

問題リンク : Digits on the Floor | Aizu Online Judge問題概要 : 線分の情報が与えられる 0から9の数字がそれぞれ何回現れるか数えよ 細かい制約は略解法 : 最初にunion-findで繋がっている線分をまとめる 各まとまりについて、 各線分の別の線分と交差す…