・ Codeforces 484A : Bits : Problem - A - Codeforces ・ Codeforces 484B : Maximum Value : Problem - B - Codeforces
問題リンク : Problem - A - Codeforces問題概要 : 君はモンスターと戦っている 君の攻撃力はATKy,守備力はDEFy,体力はHPy モンスターの攻撃力はATKm,守備力はDEFm,体力はHPm １ターンに君の体力はmax(0,ATKm-DEFy)減り、モンスターの体力はmax(0,ATKy-DEFm)…
問題リンク : Happy End Problem | Aizu Online Judge問題概要 : 略解法 : DP 答えるものが多角形の頂点番号なので経路復元もしなければならない メモ化再帰でも間に合うと思ったが幻想だった 各点を出力に合わせてソートする 下にあるものほど前にくる 同じ…
問題リンク : Problem - 442A - Codeforces問題概要 : Aliceはn枚のカードを持っている カードは色と値を持っている 色は{'R','G','B','Y','W'} のいずれかで 値は{'1','2,'3','4','5'} のいずれか Aliceはn枚のカードをランダムにシャッフルした後、机の上…
問題リング : [uva.onlinejudge.org/external/127/12729.pdf:title]問題概要 : H * W のグリッドがあり、初期状態では各マスに色はついていない AnaとBobがゲームをする 最初のターンはAnaが行う Anaは色が付いていない2*2のマスを選び赤で塗りつぶす Bobは…
問題リンク : http://uva.onlinejudge.org/external/127/12755.pdf問題概要 : N*Nのマスに０からN*N-1までそれぞれ１つずつかかれている これを0から昇順になるように並び替えたい ２つのマスの値を入れ替えるためには、片方のマスが０でなければならない 昇…
問題リンク : http://uva.onlinejudge.org/external/126/12627.html問題概要 : 赤い風船を１つだけ持っている 次の日になると赤い風船が３つ、青い風船が１つになった 次の日になると赤い風船は前日と同様に分裂し、青い風船は４つの青い風船になった 詳しく…
問題リンク : http://uva.onlinejudge.org/external/126/p12640.pdf問題概要 : 長さNの数列が与えられる この中から連続するいくつかの数字を選び、それらの和をとる この値の最大値を求めよ解法 : 数列を a とし、各要素は a[i] ( 0 a[0]から順番に見ていく…
問題リンク : Problem - 482A - Codeforces問題概要 : n以下の異なる正の整数からなるパーミュテーションpについて考える pの隣接する各要素の差分が異なるk個の数の集まりとなるようなpを出力せよ解法 : n = 7 について考えるk = 1 のとき、 1 2 3 4 5 6 7k…
問題概要 : 貴方はホテルを経営している 今年も既にn人から予約が入っている n人の到着する日と出発する日が与えられる 貴方はn人の中から何人か選んでその人らにプレゼントをあげる プレゼントをもらった人はハッピーになる プレゼントをもらった人と同じ日…
TCが黄色くなったのでメモ 2014/1/13 SRM645 o-- score : 178.35 / place : 84 ようやくこれでTC,CF両方黄色くなった ( CFは薄いほうの黄色だけれども ) これでようやく心にゆとりを持つことができるこれで本当にチームがYYYになれる ( これまでもCFが薄くて…
問題リンク : Problem - 104C - Codeforces問題概要 : 無向グラフがあたえられる このグラフに、ちょうど１つだけ閉路が存在するかどうか判定せよ解法 : まず、グラフが非連結な場合があるので最初にDFSやらなんやらして非連結ならNOと出力して終わる 次に、…
問題リンク : Problem - 496D - Codeforces問題概要 : 2人でテニスをしたときの記録が与えられる このテニスはsセット先取した人が勝利する 1セットはtポイント先取した人のものとなる 与えられた記録から考えられるsとtの組み合わせをすべて求めよ 記録の長…
問題リンク : Problem - A - Codeforces問題概要 : 長さmの文字列がn個与えられる 自分はこの文字列に対して、ある列を決めn個の文字列の決めた列にある文字を全て削除することができる n個の文字列が辞書順になるために必要な列の削除の回数をもとめよ解法 …
問題リンク : Problem - 498B - Codeforces問題概要 : ある人がn曲の歌を決められた順番で歌う 自分はその歌の名前を思い出し次第その人に対して歌の名前を伝える そうするとその人はその歌をやめて次の歌を歌う 自分は１秒単位でその歌の名前を確率pで思い…
問題リンク : 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問題概要 : 複数の数式が与えられる 一番最初の式が正しい答えで、その他の式がそれと同じかどうか判定せよ 細かい制約は略解法 : 各変数に対してランダムに値を割り当て、式の結果が一致するかどうかチ…
