土下座しながら探索中

主に競技プログラミング

Typical DP Contest I : イウィ

問題リンク : I: イウィ - Typical DP Contest | AtCoder問題概要 : 最大iwi数解法 : メモ化再帰 => WA 区間DP => TLE TLEを解消する方法が全く浮かばなかったので諦めてrngさんのコードを参考に解いたdp[L][R] := 閉区間[L,R]までで得られるiwiの最大値 区…

Typical DP Contest H : ナップザック

問題リンク : H: ナップザック - Typical DP Contest | AtCoder問題概要 : 日本語なので略解法 : まずナップザックに入れるものを色の番号が小さい順にソートする (同じ色のものは連続した場所に存在するようにしたいだけ) 通常のナップザックに加えて、今…

Typical DP Contest G : 辞書順

問題リンク : G: 辞書順 - Typical DP Contest | AtCoder 問題概要 : 文字列sと自然数Kが与えられる sから得られる連続でない部分文字列のうち、辞書順でK番目のものを求めよ解法 : 他の人のブログを参考に解いたので、 コードにある通りコード: #include<bits/stdc++.h> #d</bits/stdc++.h>…

UVa 1577 : Low Power

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

UVa 13039 : Fibonacci Triangle

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

UVa 13036 : Birthday Gift to SJ - 2

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

Typical DP Contest F : 準急

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

Typical DP Contest E : 数

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

AOJ 2607 : Invest Master

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

SEERC 2015 A : Equivalence

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

Typical DP Contest D : サイコロ

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

Typical DP Contest C - トーナメント

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

Typical DP Contest B - ゲーム

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

Typical DP Contest A - コンテスト

問題リンク : 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 Tsukuba Regional Contest : つくば大会 参加記

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

LiveArchive 6582 : UVa 1642 : Magical GCD

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

AOJ 1350 : There is No Alternative

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

LiveArchieve 6804 : Group of Strangers

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

SRM 655 Div1 easy : LuckySum

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

UVa 12923 : The Island

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

Live Archive 6889 : City Park

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

AOJ 1229 : Young, Poor and Busy

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

CODE FESTIVAL 2015 予選A

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

AOJ 0616 : JOI Park

AOJ

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

AOJ 1325 : Ginkgo Numbers

AOJ

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

独自の言語で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さんがカー…