問題リンク : Problem - 498A - Codeforces問題概要 : ２次元平面上の異なる２点とn本の直線が与えられる ２つの直線が同一であることはないし、２点が線分上に存在することもない ２点のうち片方からもう片方へ移動する際にまたがなければならない線分の数…

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

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

問題リンク : http://uva.onlinejudge.org/external/128/12856.pdf問題概要 : 長さ10^6以下の文字列が与えられる 文字列の部分文字列のうち、数字のみを含み、それを10進数の数として見たときにその値が3の倍数であるようなものを数えよ リーディング０も許…

問題リンク : http://uva.onlinejudge.org/external/105/10593.pdf問題概要 : n * n の char のシートが与えられる それに含まれる要素は 'x' か '.' のいずれか この中に含まれる大きさが１より大きい正方形とダイアモンドの数を数えよ解法 : 動的計画法 正…

問題リンク : No.75 回数の期待値の問題 - yukicoder問題概要 : 日本語なので略解法 : これまでの目の合計をノードとする ( つまり0,1,2,...,K がノードとなる ) 各ノードから遷移できるノードに対して辺を張り、有向グラフをつくる 各辺の重みは１とする ( …

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

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

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

問題概要 : 短いし分かりやすいので略解法 : 素因数分解 + ローリングハッシュで通せたが怪しい気がしなくもない 愚直に値を計算すると当然オーバーフローするので、素因数分解してからq1,q2の各素因数の数だけを増やしていく感じにした setにmapを詰めたと…

SRMの進捗を記録したかった SRM 進捗情報とメモ ディビジョン ラウンド easy medium hard 一言 Div2 500 o o SRM 500 Div2 Hard : GeometricProgressions - 土下座しながら探索中 mediumが読めない Div1 500 Div2 501 Div1 501

問題リンク : http://uva.onlinejudge.org/external/16/1674.pdf問題概要： N個のノードからなる木が与えられる 各ノードは0からN-1まで番号が付けられている Q個のクエリーが与えられる クエリは次の形式で与えられる a b c これは、aからbまでの経路に属す…

問題リンク : http://uva.onlinejudge.org/external/127/12708.pdf問題概要 : 正の整数Nが与えられる。 N以下の任意の異なる２つの正の整数を選び、その最大公約数を求める こうして得られる最大公約数のうち、最大のものを出力せよ解法 : Nが偶数のとき、N/…

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

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

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

問題リンク : http://uva.onlinejudge.org/external/119/11908.pdf問題概要 : いくつかの重み付きの線分が与えられる それらの内いくつかを選択し、その重みの総和を最大化せよ ただし、ある点が複数の線分におおわれてはならない解法 : 重み付き区間スケジ…

問題リンク : Problem - 1693問題概要: h*w のグリッドがあり、各マスには木が生えているかなにもないかのどちらかである 化け物が木の生えているマスに現れ、隣接するマスで木が生えているマスに移動しどんどん木を食べて、その後に消える 移動経路が円にな…

問題集 : ( タグはネタバレを含むため白文字 ) ・ AOJ 2171 Strange Couple : Strange Couple | Aizu Online Judge タグ : 期待値、連立1次方程式・ yukicoder No.75 : No.75 回数の期待値の問題 - yukicoder タグ : 期待値、連立1次方程式・ AOJ 2172 Queen…

問題リンク : http://uva.onlinejudge.org/external/120/12086.pdf問題概要 : 長さNの数列とクエリーが与えられる クエリーの種類と効果は次の通り 1. S x y 数列のx番目の要素 ( 1-indexed ) を y に変更する2. M x y 数列のx番目の要素からy番目の要素まで…

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

問題リンク : http://uva.onlinejudge.org/external/125/12509.html問題概要： n本の線分が与えられる 線分はx軸かy軸に平行である 外側から到達可能な線分の部分の長さの総和を求めたい解法 : 線分アレンジメント + 座標圧縮 + DFS 線分をアレンジメントし…

問題リンク : http://uva.onlinejudge.org/external/122/12294.html問題概要 : ゲームの主人公の初期の力はpであり、これからn個のステージを全て入力で与えられた順番でクリアしなければならない ( できない場合は"Impossible"と出力 ) 各ステージは p1, p2…

問題リンク : http://uva.onlinejudge.org/external/122/12295.html問題概要 : n * n のセルがあり、セルの中には1以上9以下の数字がかかれている 左上を(0,0), 右下を(n-1,n-1)としたとき、左上から右下へ移動する経路のうち、通ったセルの数字の和が最小と…

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

問題リンク : D: 禁止された数字 - AtCoder Beginner Contest 007 | AtCoder問題概要 : A以上B以下の整数で４か９を含むものの数を求めよ解法： 桁DP dp[桁][ぎりぎりかどうかをboolでもつ] := 総数 間違えて４も９も含まない数字を数え上げてしまったので全…

問題リンク : http://uva.onlinejudge.org/external/17/1707.pdf問題概要 : 凸多角形の建物がある それはn枚の壁からなり、壁は１からnまで番号がつけられている k個のカメラがその建物のまわりに設置してあり、i番目のカメラはs[i]からt[i]までの壁を撮影で…

UVa演習 2014/7/14 (月) 問３問題リンク : http://uva.onlinejudge.org/external/103/10328.html問題概要： n回コインをなげたとき、2^nだけコインの状態がある そのうち連続でk回以上表がでているようなものはいくつあるか？解法: 動的計画法 dp[何桁までみ…

UVa演習 2014/7/14 (月) 問2問題リンク : http://uva.onlinejudge.org/external/115/11500.html問題概要： 2人のプレイヤーでゲームを行う プレイヤー１の体力はEV1,プレイヤー２の体力はEV2である ゲームがはじまるとプレイヤーが交互にサイコロをふってい…

UVa演習 2014/7/14 (月) 問1問題リンク : http://uva.onlinejudge.org/external/111/11181.html問題概要： N人の人がショッピングにいく 人i ( 1 N人中ちょうどr人が何かを購入する時、人iが何かを購入する確率を求めよ制約： 1 0 0.1 解法: Nが２０人しかい…