ドイツ大学院生日記

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

競技プログラミング

AGC014 B問題 Unplanned Queries

問題 agc014.contest.atcoder.jp 解説 まずこの問題では木を根付き木として考えます。各辺は偶数回 +1 されていれば良い、つまり各辺の値が0, 2, 4, ...となっていれば良いのでmod2で考えることができます。そして根をrとすると, +1する辺を(a, b)ならば(a,r…

AGC013 B問題 Hamiltonish Path

問題 agc013.contest.atcoder.jp 解説 まず適当に頂点uを選択します。頂点uから移動可能な頂点vを探して頂点vから今まで訪れた頂点でない頂点xを選択し頂点xから移動可能な今まで訪れた頂点でない頂点yを選択し、、、 このような操作を繰り返していくと移動…

ARC083 D問題 Restoring Road Network

問題 AtCoder Regular Contest 083 - AtCoder 解説 入力例のケースで考えてみます。 3 0 1 3 1 0 1 3 1 0 この場合三角形の頂点に3つの街があると仮定し、辺の付近に都市間の距離を書いた、図は 3 ①ーー③ 1| / ②/ 1 となります。 しかし都市間の距離を長…

AGC002 C問題 Knot Puzzle

問題 agc002.contest.atcoder.jp 解説 この問題は結び目に注目して考察すれば解くことができます。 最後にほどくのは必ず左右のロープの長さの和がL以上の結び目でなければなりません。したがってそのような結び目が存在しなければほどくことはできません。 …

AGC001 B問題 Mysterious Light

問題 agc001.contest.atcoder.jp 解説 解法の方針はユークリッドの互除法です。 なぜこの問題を見てユークリッドの互除法が思いつくのかをまず解説していきます。 ユークリッドの互除法を幾何的に説明したサイトがあったので紹介します。 math-arithmetic.bl…

AOJ Range Minimum Query (RMQ)

問題 Range Minimum Query (RMQ) | Aizu Online Judge 解説 一般的なRMQの問題です。 セグメント木で実装すれば構いません。 コード #include <iostream> #define ll long long using namespace std; const int INF = (1<<31)-1, MAX_N = 1<<17; int N, dat[2*MAX_N -1</iostream>…

ARC 074 D問題 3N Numbers

解説 この問題はどこで前半と後半の区切りになるのかを考えます。 例えば | が前後半の区切りだとすると a, b, c d, e | f, g, h, i この棒をずらしていくのですがn~2*nの間しか動くことができません。 先頭からN個数字をとる場合 a, b, c, d, e, f | g, h, …

ARC 072 D問題 Alice&Brown

解説 まずこのようなゲーム系の問題は終了時から遡って考えていきます。 そこでゲームが終了する場面を考えてみると (x, y) = (0, 0), (1, 0), (0, 1),(1, 1) この4通りぐらいは自分で見つけることができるかと思います。 次にx, yが0~5の6x6の表を書いてみ…

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』と決めてあげれば与えられた文字列から全体を決定することができます。 そして完成した文字列が与えら…

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を表す)を代入します。 ルートであれば親は持っていないは…