問題リンク : https://uva.onlinejudge.org/external/15/1577.pdf問題概要 : n台のマシーンがある 各マシーンは２つの回路を持っていて、 各回路はk個のバッテリーを持っている つまり、全てのマシーンにバッテリーをセットするためには2*n*k個のバッテリー…

問題リンク : https://uva.onlinejudge.org/external/130/13039.pdf問題概要 : 1番目のフィボナッチ数を2, 2番目のフィボナッチ数を３とする i番目のフィボナッチ数と同じ長さの線分がそれぞれa[i]個存在する これらの線分を使って作れる三角形の本数の最大…

問題リンク : https://uva.onlinejudge.org/external/130/13036.pdf問題概要 : フィボナッチ数の積として表されるような数で、a以上b以下のものの最大値を求めよ解法 : laycrsさんの解説を読んで解いた フィボナッチ数のうち2から89までを前半、それ以降を後…

問題リンク：F: 準急 - Typical DP Contest | AtCoder 解法： dp[i] := i番目の駅に停まらない数 = dp[max(0,i-K)] + ... + dp[i-1] 初期値は dp[0] = 1, dp[1] = 0 また、dp[N] = 0 dp[1]=dp[N]=0は、必ずその駅にとまることを意味する dp[i]は max(0,i-K)…

問題リンク : E: 数 - Typical DP Contest | AtCoder解法 : 桁DP dp[桁][余り][現在の桁までがNのこの桁までと一致しているか] := 総数コード : #include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i</bits/stdc++.h>

問題リンク : Invest Master | Aizu Online Judge問題概要： n日間の株価の情報が与えられる 初日にx円所持しているので、株の売買を行い最終日の所持金を最大化せよ 株の売買に手数料はかからないものとする また、最終日の所持金の最大値は高々１０＾５で…

問題リンク : https://icpcarchive.ecs.baylor.edu/external/71/7173.pdf問題概要 ： ２つの論理式が与えられる それらが等価か判定せよ論理式は論理変数、論理和、論理積、否定から構成される 論理演算の優先度は気にしなくても良い（適切に括弧がつけられ…

問題リンク : D: サイコロ - Typical DP Contest | AtCoder解法 : Dを素因数分解したとき、その素因数に２、３、５以外のものが存在するのであれば求める確率は０となる （サイコロの目が１から６までしかないので、例えば７は２、３、５の積ではどうやって…

問題リンク : C: トーナメント - Typical DP Contest | AtCoder解法 : DP全然思い浮かばなかったので愚直に計算した 他の人のコード見て勉強しますコード: #include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i</bits/stdc++.h>

問題リンク : B: ゲーム - Typical DP Contest | AtCoder解法 : dp[i][j] := 左の山の残りがi個、右の山の残りがj個の時の（すぬけのターン）最大or（すめけのターン）最小値両方の山が０を初期状態とし、１手1手戻りながら計算するコード : #include<bits/stdc++.h> #defin</bits/stdc++.h>…

問題リンク : A: コンテスト - Typical DP Contest | AtCoder解法 : bool dp[i] := i が作れるならtrue, otherwise falseコード : #include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i<n;i++) #define rep(i,n) REP(i,0,n) using namespace std; int n; bool dp[10001]; int main() { dp[0] = true; cin >> n; rep(i,n) { int tmp; cin >>…</n;i++)></bits/stdc++.h>

ACM-ICPC 2015 つくば大会に参加したので記録チーム情報 コーチ : 先輩 研究が忙しい中つくばまで来て頂き有難うございました 「あのシャワー水しかでなかったんだけど」 コンテスタント1 : 後輩T 競プロ歴２日 英語マスター バンバン訳してバンバン伝える …

問題リンク:https://icpcarchive.ecs.baylor.edu/external/65/6582.pdf問題概要： 長さn(1 数列の各要素a[i]は1以上10^12以下 数列の連続した部分列を取り出し、(部分列全体のgcd) * (部分列の長さ) を値とする 値の最大値を出力せよ解法： 部分列の最も右と…

問題リンク:There is No Alternative | Aizu Online Judge問題概要: 重み付き無向グラフが与えられる これに対する最小全域木は複数存在しうるが、それら全ての最小全域木に共通して存在する辺の数とそれらの総和を求めよ解法: Kruskal法を用いてMSTを構築す…

問題リンク:https://icpcarchive.ecs.baylor.edu/external/68/6804.pdf問題概要： 無向グラフが与えられる 3点を選んだとき、それらの間に1本も辺が存在しないようなものの数を数えろ解法: 公式解説の通りコード: #include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i</bits/stdc++.h>

問題概要 : 4と7から構成される正の整数をLucky Numberと呼ぶ [0-9]と?から構成される文字列が与えられる ?には何の数字が入っても良いので、2つのLucky Numberの和がその文字列と等しくなるようなもののうち最小の和を求めよ解法 : 動的計画法 dp[桁][値][…

問題リンク : https://uva.onlinejudge.org/external/129/12923.pdf問題概要 : n * n のマトリックスが与えられる マトリックスの(i,j)はi番目の人が武器jを使った時に得られる力を表す n人の人がそれぞれ１つ武器を持った際に得られる力の総和の最大値を求…

問題リンク : https://icpcarchive.ecs.baylor.edu/external/68/6889.pdf問題概要 : 2次元平面上に１つ以上の長方形がそれぞれオーバーラップせずに置いてある 長方形の縦と横はそれぞれy軸とx軸に平行である ２つの長方形が辺または角で接しているとき、そ…

問題リンク : Young, Poor and Busy | Aizu Online Judge問題概要 : けんさんは函館に住んでおり、けいこさんは東京に住んでいる けんさんとけいこさんは電車を使って合う予定を立てている 電車の時刻表の情報を持っており、その情報は電車が出発する駅の名…

CODE FESTIVAL 2015 予選A に参加した ４完してる人が140人もいて予選突破の難易度の上昇を感じた 各問題について、コメントは以下の通りA : やるだけでしょ => ループの範囲１少なくてWA 辛いB : ループのインデックス*２個だけ足せば良い => AC 良いC : 差…

問題リンクJOI Park | Aizu Online Judge問題概要 : 日本語なので略解法 : その通りに計算する 愚直にやると遅いので、全ての辺の重みの総和を求め Xを小さい順に見ていき辺の総和を減らしていく まず、ノード１からdijkstraで各ノードへの最短距離を求める …

問題リンク : Ginkgo Numbers | Aizu Online Judge問題概要 : Ginkgo Number が与えられる 問題文中で定義されている素数の条件を満たすかどうか判定せよ解法 : 一番下に書いてあるヒント的なものの2つめを使った If · = , then (m2 + n2)(x2 + y2) = p2 + q…

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

問題リンク : The Phantom | Aizu Online Judge問題概要 : 2次元平面上に２枚の鏡と幽霊がいる 鏡と幽霊はそれぞれ線分と点として表される 鏡に映る幽霊の数を出力せよ ただし、その数が100を超える場合は"TOO MANY"と出力せよ解法 :よくあるビームと鏡の反…

問題リンク : 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) に…

問題リンク : Reverse a Road II | Aizu Online Judge問題概要 : V個のノードとE本の有向辺からなるグラフがある それぞれのノードには１から順に番号が割り振られており、 S番からT番に車をできるだけ多くの車を送る ただし、１つの辺を通れる車は高々１台 …

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

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

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

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