競プロ記録

問題を解いた際に自分の復習用として使ってます

DMM FX DEMO 2日目

競プロに全く関係ありません。 昨日に引き続き今日も上昇傾向で、一時1ドル110円まであがりました。 そのため本日も容易に利益を出すことができたのでよかったです そのうち大損しそうだから気をつけなければ、、、 一体どこまで上がるのだろう?確実に110円…

DMM FX DEMO

※競プロに全く関係ありません。 今日からDMM FX デモでキャンペーンが始まりました。 それは5,000,000円スタートで3ヶ月間でいくらに増やせるかというのを競います。 夏休みからデモで FXを始めました。 でも暇つぶしにやっているだけで現金は投入する予定は…

yukicoder No.129

解説 基本的な解法の方針は動的計画法です。 そしてお金は1000円単位で平等に配るので、n/1000 mod m 円を分配することは容易にわかると思います。 なので k = n/1000 mod m とすると求めるのはm人にk枚を平等に配るので一人あたり1000円になります。よって…

yukicoder No390

解説 基本的な解法の方針は動的計画法です dp[i] := 値iの要素が右端になる時の長さの最大値 とします。そうすると以下のような漸化式を立てることができます。 dp[i] = dp[y]+1 (yはiの約数) 基本的にはこれだけなのであとは値iの約数を列挙しなければいけ…

yukicoder No.458

解説 基本的な解答の方針は動的計画法です。 小さい素数から順番に見ていって、i番目までの素数で構成される数に対してi+1番目の新たな素数を加えれば、その和の数は異なる素数で表すことができることになります。 そこで素数を加えた回数を保持するために、…

yukicoder No.505

解説 基本的な解放の方針は動的計画法です。 最小値と最大値を保持して計算していけば、答えを求めることができます。 また除算もする必要があるので注意です。 例えば-9 3の場合 -9/3が最大の答えになります。 コード #include <iostream> using namespace std; int m</iostream>…

yukicoder No.533

問題文 1段, 2段, 3段登ることができる人がn段の階段を登っていく場合、n段目までの方法の総数を出力する問題です。 しかし、1つ条件があり、連続して同じ段数を登ることはできません。 解説 基本的な解法の方針は動的計画法です。 連続して、同じ段数登る…

Educational Codeforces Round 27

A問題 Chess Tourney 問題文 2*n個の数字が与えられ、それをn個ずつの2組に分割します。そして2組からそれぞれ一つずつ取り出しn個のペアを作ります。 ここで、1つのペアの中で数字が大きい方が勝ちとします。そしてn個のペアで全て勝つような組が作れればY…

Chokudai Speed Run G問題

Chokudai Speed Run001 G問題解説 問題 数列 aが与えられ a を連結させた整数を、 1,000,000,007 で割った余りを求めなさい。 サンプル Input 7 7 6 5 4 3 2 1 Output 7654321 解説 全てを加えて剰余をとるという方針はlong long では所持できないので不可能…

ダイクストラ法(priority_queue)、経路復元

経路復元(ダイクストラ法) #include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; struct edge { int to, cost; }; typedef vector<vector<edge> > AdjList; AdjList graph; typedef pair<int, int> P; const int INF = 10000000; vector<int> dist; vector<int> prever; void dijkst</int></int></int,></vector<edge></algorithm></queue></vector></iostream>…

ベルマンフォード法とダイクストラ法をvectorで実装

ベルマンフォード法 #include <iostream> #include <vector> using namespace std; struct Edge { int to, cost; }; typedef vector<vector<Edge> > AdjList; // 隣接リストの型 AdjList graph; const int INF = 1000000; vector<int> dist; bool bellman_ford(int n, int s){ dist = vector<int>(n,IN</int></int></vector<edge></vector></iostream>…

055ABC D問題D - Menagerie

問題D - Menagerie この問題は1番目と2番目を決めてあげれば3番目がSかWかが決定できます。 そこで1番目、2番目を 『S、S』『S、W』『W、S』『W、W』と決めてあげれば与えられた文字列から全体を決定することができます。 そして完成した文字列が与えら…

TokenMismatchException in compiled.php line3227

【TokenMismatchException in compiled.php line3227】 webシステムをLaravelで開発しているのですが、このフォーム送信時にエラーが出ました。 まずgoogleで検索をしたら以下のサイトを見つけました。 laracasts.com このサイトでの結論は{{ csrf_field() }…

No4 おもりと天秤

No4 おもりと天秤 解説 問題 NとWがN個与えられ、2組に重りを分け、その2組の重さが等しくなるようにできるのかどうかを調べる問題です。 解答 まず2組が等しくなるためには全ての重りの和が偶数でなければいけません。 その場合にその半分の和となる選び…

No.3 ビットすごろく

yukicoder No.3 ビットすごろくの解説 この問題はある数字Nが与えられ。1〜Nの区間での最小の移動回数を求めます。位置の数字を2進数で表し「1」のbit数だけ前、後に移動することができます。 まずqueueとしてQを宣言します。Qにはその位置から移動できる…

No.8 N言っちゃダメゲーム

No.8 N言っちゃダメゲーム 解説 この問題はNとKが与えられ、Kを宣言したら負けとなるゲームです。 自分は必ず先攻で、相手は後攻です。 1〜Kの値までで加算して宣言することができます。 解答 この問題は自分がN−1をいうことができれば勝てます。 相手にN−…

二分探索木:削除

【アルゴリズムとデータ構造】二分探索木:削除(解説) 9.4の解説をします。 ある節点Zを削除する時を考えます。 ・Zが子を持たない場合 ただ単にZを削除すれば良いので、Zの親の子供を削除つまりZを削除すれば良い ・Zが子を一つ持つ場合 Zは親と子供に…

二分探索木:探索

【アルゴリズムとデータ構造】二分探索木:探索(解説) 215ページの解説をしていきます。 まずどこから探索していくかの基準となるxと調べる値kを引数として受け取ります。 そのあとxをどんどん移していくのですがそのxの値が存在しなくなるまたは、keyにた…

二分探索木:挿入

【アルゴリズムとデータ構造】二分探索木:挿入(解説) 9.2の二分探索木の解説をしていこうと思います。 209ページのプログラムの解説 まずルートから挿入する位置を探索するのでyにNIL(rootを表す)を代入します。 ルートであれば親は持っていないは…

競技プログラミング始めました

今年はプログラミング技術向上のために 競技プログラミングを頑張っていくことにした。 まあそんなんで今蟻本を解いているのですが、動的計画法がよくわからん、、、 なので蟻本に載っている練習問題を解いていくことにした。 問題は POJ3176,2229,2385,3616…