2015-12-01から1ヶ月間の記事一覧
問題リンク : https://uva.onlinejudge.org/external/15/1577.pdf問題概要 : n台のマシーンがある 各マシーンは2つの回路を持っていて、 各回路はk個のバッテリーを持っている つまり、全てのマシーンにバッテリーをセットするためには2*n*k個のバッテリー…
問題リンク : https://uva.onlinejudge.org/external/130/13039.pdf問題概要 : 1番目のフィボナッチ数を2, 2番目のフィボナッチ数を3とする 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円所持しているので、株の売買を行い最終日の所持金を最大化せよ 株の売買に手数料はかからないものとする また、最終日の所持金の最大値は高々10^5で…
問題リンク : https://icpcarchive.ecs.baylor.edu/external/71/7173.pdf問題概要 : 2つの論理式が与えられる それらが等価か判定せよ論理式は論理変数、論理和、論理積、否定から構成される 論理演算の優先度は気にしなくても良い(適切に括弧がつけられ…
問題リンク : D: サイコロ - Typical DP Contest | AtCoder解法 : Dを素因数分解したとき、その素因数に2、3、5以外のものが存在するのであれば求める確率は0となる (サイコロの目が1から6までしかないので、例えば7は2、3、5の積ではどうやって…
問題リンク : 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(すめけのターン)最小値両方の山が0を初期状態とし、1手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 競プロ歴2日 英語マスター バンバン訳してバンバン伝える …