土下座しながら探索中

主に競技プログラミング

AOJ

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で繋がっている線分をまとめる 各まとまりについて、 各線分の別の線分と交差す…

AOJ 1233 : Equals are Equals

問題リンク : Equals are Equals | Aizu Online Judge問題概要 : 複数の数式が与えられる 一番最初の式が正しい答えで、その他の式がそれと同じかどうか判定せよ 細かい制約は略解法 : 各変数に対してランダムに値を割り当て、式の結果が一致するかどうかチ…

AOJ 1238 : True Liars

問題リンク : True Liars | Aizu Online Judge問題概要 : 自分今、伝説の島にいる その島には正直者と嘘つきがいて、自分はその正直者に用事がある 以前の調査で正直者はp1人、嘘つきはp2人いることが分かっている 今、各人に1から昇順に(p1+p2)まで番号を…

AOJ 2063 : TV Watching

問題リンク : TV Watching | Aizu Online Judge問題概要 : N本のテレビ番組の情報が与えられる 同じ時刻に複数の番組を同時に見ることは不可能なので、自分はそのテレビ番組をリアルタイムで見るか録画して後で見るかを選べる リアルタイムで見た時の満足度…

AOJ 1047 : Crop Circle

問題リンク : Crop Circle | Aizu Online Judge問題概要 : n個の円の中心点の座標と半径が与えられる 円周上で他のどの円にも囲まれていないような部分の長さの総和を求めよ解法 : 各円について、他の円との交点で細分化する 例えば円0については以下通りに…

AOJ 1219 : Pump up Batteries

問題リンク : Pump up Batteries | Aizu Online Judge問題概要: N人のボディーガードは1から順にNまで番号が割り振られており、それぞれがウェアラブルコンピュータを身につけている 各ウェアラブルコンピュータは使える時間とその後充電にかかる時間を周期…

AOJ 2040 : Sort the Panels

問題リンク:Sort the Panels | Aizu Online Judge問題概要: 長さの同じ文字列が2つA、Bが与えられる それぞれの文字列は'B'または'W'のみを要素としてもつ 文字列上のどこかにポインタが存在し、自分はそのポインタを1つ左か1つ右かに動かすことができ…

AOJ 1128 : Square Carpets

問題リンク:Square Carpets | Aizu Online Judge問題概要: 最大10*10のマスがあり、それらの中には0か1が書かれている 値が1であるようなマスを全てカーペットで覆いたい カーペットは正方形で、長さは自由に決めれる ただしカーペットで覆うマスの値は…

AOJ 1118 : Nets of Dice

問題リンク:Nets of Dice | Aizu Online Judge問題概要: 5*5のセルには0から6までの数字がかかれている これがサイコロの展開図になっているかどうか判定せよ解法: 小さいので実際にDFSで展開図になっているかどうか確かめるまず最初に明らかに駄目なケー…

AOJ : 2449

問題リンク:Connect | Aizu Online Judge問題概要: 略解法: 1行覚えるタイプの動的計画法 dp[r][c][bit] := (c,r)までで使用する文字列の状態がbitの時の最大値 としてDPする bitの数を数えてその行の文字列よりも多く使用する場合などはcontinueする 2重…

AOJ 2286 : Farey Sequence

問題リンク:Farey Sequence | Aizu Online Judge問題概要: 略解法: オイラーのΦ関数を使う i == 0 のとき、F_0 = 2 その他のとき、F_i = F_i-1 + (iと互いに素なものの数) となる iと互いに素なものの数はオイラーのΦ関数で求める 前処理でFを作っておいて…

AOJ 2285 : Anipero

問題リンク:Anipero | Aizu Online Judge問題概要: 略解法: 動的計画法 pre[使用した金額][選んだシークレットアーティストの数(0,1,2人のみ)] := この時得られる最大の満足度 pre2[使用した金額][選んだスタンダードアーティストの数] := この時得られる最…

AOJ 2178 : Futon

問題リンク:Futon | Aizu Online Judge問題概要: n枚の布団の位置情報が与えられる それらの布団に人が寝るわけだが、 人の頭のに隣接する部分に他の人の足があってはならない そのような寝方があるかどうか判定せよ解法: グラフを構築して2色でそれらの…

AOJ 1236 : Map of Ninja House

AOJ

問題リンク:Map of Ninja House | Aizu Online Judge問題概要: 無向グラフが存在する 自分は最初そのグラフのノード番号0のノードにいる 入力が正のとき、それは今いるノードの次数を表す 入力が負のとき、それは(今いるノードの深さ)ー(1つ前にいた…

AOJ 2091 : Petoris

問題リンク : Petoris | Aizu Online Judge問題概要: h * w のピースと H * W のボードがある ピースとボードは'.'または'#'からなる '.'はそこが空であることを意味し、'#'はそこが埋まっている亊を意味する ピースをボード上に置きたい 置く際には、ピー…

AOJ 2090 : Repeated Subsequences

問題リンク:Repeated Subsequences | Aizu Online Judge問題概要: 長さが300以下の文字列があたえられる この文字列を空でない2つの文字列に分ける こうしてできる2つの文字列のLCSの中で最も長いものを出力せよ 複数ある場合はどれを出力しても良い解法…

AOJ 2097 : Triangles

問題リンク:Triangles | Aizu Online Judge問題概要: 1辺の長さが1の正三角形をn個、任意の点を中心として 360/n 度間隔で置いていく この時n個の正三角形が覆う面積はどのくらいか?解法: 正多角形から余計な部分を引いて面積を出した上の図の黒い矢印…

AOJ 1254 : Color the Map

問題リンク:Color the Map | Aizu Online Judge問題概要: 10個以下の国の情報が多角形として与えられる それらの国に色を塗っていきたいのだが、隣接する国同士は異なる色で塗りたい 同じ国であるならば同じ色で塗らなければならない 最低何色必要か解法:…

AOJ 1143 : Hexerpents of Hexwamp

問題リンク : Hexerpents of Hexwamp | Aizu Online Judge問題概要 : 略解法:A*(移動した回数) + (大蛇の頭からゴールまでの距離) > 20 なら枝刈りをしたこの問題での2つの6角座標の距離は以下のように計算する (x1,y1) から (x2,y2) への距離distを求める…

AOJ 1291 : Search of Concatenated Strings

問題リンク:Search of Concatenated Strings | Aizu Online Judge問題概要: n個(1 n個の文字列を任意の順で全てつなげた文字列がtのなかにどのくらい存在するか? ただし、n個の文字列をつなげた際に同じものが複数できた場合はそれらを1つとみなす解法:…

AOJ 1243 : Weather Forecast

問題リンク:Weather Forecast | Aizu Online Judge問題概要: 略解法: メモ化再帰をした 今何日かと今どこかと1,3,9,11を最後に雨を降らしてから何日訪れていないかを記録した初期化で毎回365*9*7*7*7*7してたらTLEをくらってしまったコード: #define REP…

AOJ 2366 : Elevator

問題概要:Elevator | Aizu Online Judge問題概要: 日本語なので略解法: 動的計画法を行う 荷物があるフロアの中で最も上にあるフロアから1フロアずつ全ての荷物をもっていきながらおりていく そのフロアにある荷物を全て1つ下のフロアに持っていくため…