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

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

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

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

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

問題リンク : http://uva.onlinejudge.org/external/114/11401.pdf問題概要 : 3以上の整数 n が与えられたとき、 長さが1からnまでの棒がそれぞれ1本ずつあるものとして それらのうち3本を選んで作れる三角形の個数を出力せよ n が3未満ならばプログラムを終…

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

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

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

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

問題概要: これまた備忘録なので略解法： １からNまでの周期が存在するので（＜＝ノートに書いてたらそんな感じ、直感的に） １からNまでの最小公倍数を求めれば良い（＜＝さっきのことがわかればそうなるでしょうね） １からNまでで存在する素数を列挙し…

[備忘録] 問題概要 : 備忘録なので略解法 : DP { 0, 0, 3, 3, 0, 0 } という数列が与えられたとする 0..1...2...3...4...5...6 0 0 3 3 0 0 みたいな感じで間に板を置き、左から昇順に番号を割り振る dp[i] := 0番の板からi番の板までで条件を満たす組み合わ…

Daily Quests 情報１ 情報２ 情報３ 情報４ 情報５ 情報６ the twenty-seventh of April (27/4/2015) SRM 655 Div1 250 BichromePainting 類題を解いたことがあるのでは 上からパネル取ってくアレ the twenty-ninth of April (29/4/2015) SRM 654 Div1 250 S…

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

問題リンク : Problem - 515A - Codeforces問題概要 : (x,y)にいる人は(x-1,y) (x,y-1) (x+1,y) (x,y+1) のいずれかに移動できる 初期位置は(0,0)で目的地(a,b)にs回の移動で到達できるか解法 : 最短で移動してもs回で目的地に到達すらできないならダメ 目…

問題リンク : Problem - 525A - Codeforces問題概要 : 2*n-2桁の文字列が与えられる 英小文字は鍵を表し、英大文字はドアを表す 鍵は同じ英文字のドアを開けることができる ドアを開けたあとその鍵は消える 自分は文字列の一番左にいて、1マスずつ右へ進んで…

Ocamlについて、忘れないようにメモ・List.sortについて List.sort 比較関数 リスト;; 例 : let list = [5;2;5;1;6;8;0];; List.sort compare list;; (* 昇順 *) 自分で比較関数を定義すると次のようになる let my_compare x y = if x = y then 0 else if x …

問題リンク : B: 高橋くんと文字列圧縮 - AtCoder Beginner Contest 019 | AtCoder問題概要 : 英小文字からなる文字列が与えられる それらを問題文中に書かれている方法で圧縮しその結果を出力せよ解法 : 圧縮して出力するコード : let rec solve s i = if (…

問題リンク : A: 高橋くんと年齢 - AtCoder Beginner Contest 019 | AtCoder問題概要 : ３つの整数が与えられるのでそれらを昇順に並びかえたときの真ん中の値を出力せよ解法 : ソートして真ん中を出すコード : Printf.printf "%d\n" ( let list = Scanf.sca…

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

立命館大学競技プログラミング合宿2015の初日、立命館大学セット 同じ大学の後輩と２人でチームを組んだ ( 折角の合宿なのだから他大学の人と組めという話だが、積極的にチーム編成に参加していかなかった結果 ) コンテスト中の流れは以下の通り開始 自分がA…

問題概要: H * W マスからなるフィールドがあり、各マスは次のいずれかである '.' : 空マス 移動可能 '#' : 障害物 移動不可能 'S' : ロボットが最初にいる場所 移動可能 ロボットは命令に従って移動する 命令は 'U','D','L','R' で表されるコマンドがいくつ…

問題概要 : 長さNの文字列がある 初期状態ではそのうちのいくつかに'A'か'B'が書かれていて、 その他は何も書かれていない これから何も書かれていない場所に'A'か'B'を書いていく ただし何も書かれていない場所全てに'A'か'B'を書い後、隣接する２つの場所…

問題リンク : Problem - A - Codeforces問題概要 : n個の文字列が与えられる n個の文字列が辞書順となるような文字の順番が存在するか あればそれのうちどれか１つを出力せよ なければ "Impossible" と出力せよ解法 : aaab aaa のように文字の順番を変えたと…

・ 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から昇順になるように並び替えたい ２つのマスの値を入れ替えるためには、片方のマスが０でなければならない 昇…