読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

独自の言語でflymakeを使うために

flymakeをデフォルトで設定してある言語以外、自分で作った言語等で使う際のflymakeの設定方法のメモ以下のコードは flymake を a_accepter に使った例 a_accepter は flymake 設定練習用に適当に用意したもの ファイルを読み込んで 'a' 以外の文字があれば…

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台 …

UVa 12484 : Cards

問題リンク : https://uva.onlinejudge.org/external/124/p12484.pdf問題概要 : 整数の書かれたN枚のカードが一直線上に並んでいる AさんとBさんは交互にカードを取っていく ただし、カードを取る際は両端のうちどちらかでないといけない 最初にAさんがカー…

AOJ 2464 : Magic Walls

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

ubuntuにNVIDIAのドライバをインストール

先日、突然画面がずれる->画面に縦線が入る->真っ黒になるという症状から、 最終的にubuntuを起動すると画面が真っ黒になった後に電源が落ちるという現象が発生windowsも同様だが、こっちの場合はwindowsの方で再起動するようで、 windows起動->画面真っ黒、…

ICPC 2015 国内予選 参加記

ICPC2015国内予選にXXXとして参加した。(チーム名は大人の事情があるので伏せる) チームメンバーは:自分、後輩S、後輩T 自分以外は今日初めて競技プログラミングをした、という謎のチーム 午前二限に授業があったため13時に会場集合ということに、 授…

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 は交互に相手の…

UVa 11401 : Triangle Counting

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

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とす…

SRM 652 Div1 250 : ThePermutationGame

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

SRM 653 Div1 250 : CountryGroupHard

[備忘録] 問題概要 : 備忘録なので略解法 : 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 情報1 情報2 情報3 情報4 情報5 情報6 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…

AOJ 1025 : Building Water Ways

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

Codeforces 515 A :Drazil and Date

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

Codefoces 525 A : Vitaliy and Pie

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

Ocaml : 備忘録

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 …

ABC #019 B : 高橋くんと文字列圧縮

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

ABC #019 A : 高橋くんと年齢

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

AOJ 2246 : Alice and Bomb

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

RUPC 2015 Day1 参加記

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

SRM 651 Div1 easy : RobotOnMoon

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

SRM 650 Div1 easy : TaroFillingAStringDiv1

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

Codeforces 512 A : Fox And Names

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

覚えておきたい問題集

・ Codeforces 484A : Bits : Problem - A - Codeforces ・ Codeforces 484B : Maximum Value : Problem - B - Codeforces

Codeforces 487A : Fight the Monster

問題リンク : Problem - A - Codeforces問題概要 : 君はモンスターと戦っている 君の攻撃力はATKy,守備力はDEFy,体力はHPy モンスターの攻撃力はATKm,守備力はDEFm,体力はHPm 1ターンに君の体力はmax(0,ATKm-DEFy)減り、モンスターの体力はmax(0,ATKy-DEFm)…

AOJ 0284 : Happy End Problem

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

Codeforces 442A : Borya and Hanabi

問題リンク : Problem - 442A - Codeforces問題概要 : Aliceはn枚のカードを持っている カードは色と値を持っている 色は{'R','G','B','Y','W'} のいずれかで 値は{'1','2,'3','4','5'} のいずれか Aliceはn枚のカードをランダムにシャッフルした後、机の上…

UVa 12729 : Squares Game

問題リング : [uva.onlinejudge.org/external/127/12729.pdf:title]問題概要 : H * W のグリッドがあり、初期状態では各マスに色はついていない AnaとBobがゲームをする 最初のターンはAnaが行う Anaは色が付いていない2*2のマスを選び赤で塗りつぶす Bobは…

UVa 12755 : Easy Puzzle

問題リンク : http://uva.onlinejudge.org/external/127/12755.pdf問題概要 : N*Nのマスに0からN*N-1までそれぞれ1つずつかかれている これを0から昇順になるように並び替えたい 2つのマスの値を入れ替えるためには、片方のマスが0でなければならない 昇…

UVa 12627 : Erratic Expansion

問題リンク : http://uva.onlinejudge.org/external/126/12627.html問題概要 : 赤い風船を1つだけ持っている 次の日になると赤い風船が3つ、青い風船が1つになった 次の日になると赤い風船は前日と同様に分裂し、青い風船は4つの青い風船になった 詳しく…

UVa 12640 : Largest Sum Game

UVa

問題リンク : http://uva.onlinejudge.org/external/126/p12640.pdf問題概要 : 長さNの数列が与えられる この中から連続するいくつかの数字を選び、それらの和をとる この値の最大値を求めよ解法 : 数列を a とし、各要素は a[i] ( 0 a[0]から順番に見ていく…

Codeforces 482A : Diverse Permutation

問題リンク : Problem - 482A - Codeforces問題概要 : n以下の異なる正の整数からなるパーミュテーションpについて考える pの隣接する各要素の差分が異なるk個の数の集まりとなるようなpを出力せよ解法 : n = 7 について考えるk = 1 のとき、 1 2 3 4 5 6 7k…

SRM 645 Div1 easy : JanuszTheBusinessman

問題概要 : 貴方はホテルを経営している 今年も既にn人から予約が入っている n人の到着する日と出発する日が与えられる 貴方はn人の中から何人か選んでその人らにプレゼントをあげる プレゼントをもらった人はハッピーになる プレゼントをもらった人と同じ日…

ただの記録

TCが黄色くなったのでメモ 2014/1/13 SRM645 o-- score : 178.35 / place : 84 ようやくこれでTC,CF両方黄色くなった ( CFは薄いほうの黄色だけれども ) これでようやく心にゆとりを持つことができるこれで本当にチームがYYYになれる ( これまでもCFが薄くて…

Codeforces 104C : Cthulhu

問題リンク : Problem - 104C - Codeforces問題概要 : 無向グラフがあたえられる このグラフに、ちょうど1つだけ閉路が存在するかどうか判定せよ解法 : まず、グラフが非連結な場合があるので最初にDFSやらなんやらして非連結ならNOと出力して終わる 次に、…

Codeforces 496D : Tennis Game

問題リンク : Problem - 496D - Codeforces問題概要 : 2人でテニスをしたときの記録が与えられる このテニスはsセット先取した人が勝利する 1セットはtポイント先取した人のものとなる 与えられた記録から考えられるsとtの組み合わせをすべて求めよ 記録の長…

Codeforces 497A : Removing Columns

問題リンク : Problem - A - Codeforces問題概要 : 長さmの文字列がn個与えられる 自分はこの文字列に対して、ある列を決めn個の文字列の決めた列にある文字を全て削除することができる n個の文字列が辞書順になるために必要な列の削除の回数をもとめよ解法 …

Codeforces 498B : Name That Tune

問題リンク : Problem - 498B - Codeforces問題概要 : ある人がn曲の歌を決められた順番で歌う 自分はその歌の名前を思い出し次第その人に対して歌の名前を伝える そうするとその人はその歌をやめて次の歌を歌う 自分は1秒単位でその歌の名前を確率pで思い…

Codeforces 498A : Crazy Town

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

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秒間…