競プロ記録

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

機会学習:メモ

前提インポート import numpy as np import matplotlib.pyplot as plt import pandas as pd import mglearn from Ipython.display import display 前提コマンド %matplotlib notebook k-Nearest Neighbors 新しいデータポイントに対して予測する際に、新しい…

Pythonによるデータ分析入門:メモ

内容 ちらほらエラーがでるところがあったので修正した箇所一覧をまとめました。 p28 修正前 users = pd.read_table('pydata-book/datasets/movielens/users.dat', sep='::', header=None, names=unames) 修正後 users = pd.read_table('pydata-book/dataset…

AGC018 A問題

問題 agc018.contest.atcoder.jp 解説 この問題はユークリッドの互除法を用います。ではなぜユークリッドの互除法と言う考え方が出てくるのか解説します。 まずユークリッドの互除法に関して以下のページを読んでください。 math.nakaken88.com a(modG)が0, …

ABC051 D問題 Candidates of No Shortest Paths

問題 abc051.contest.atcoder.jp 解説 まずNが少ないのでワーシャルフロイドを使いそうだなと考えられ、実際に使用します。 まず頂点間の最小距離を求めておきます。 そしてある辺が最小距離のパスに使われているかどうかは以下の式を満たしているs, tが存在…

CODE FESTIVAL 2017 qual B C問題 3 Steps

問題 code-festival-2017-qualb.contest.atcoder.jp 解説 辺を3本巡って到達できる頂点と辺を新たに結ぶので、2頂点間に奇数長のパスが存在すれば辺を結ぶことができます。 では奇数長のパスが存在するとはどのような時なのでしょうか。それは2分グラフであ…

ABC075 A~D問題

A問題 A - One out of Three 解説 これは解説省略します。 コード #include <iostream> #include <algorithm> #include <string> #include <set> #include <map> #include <queue> #include <vector> using namespace std; const int inf = 1e9; const int mod = 1e9+7; int main(void){ int a, b, c; string s; cin</vector></queue></map></set></string></algorithm></iostream>…

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の表を書いてみ…

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−…