記事一覧
[学習記録]グラフ理論3
参考資料https://ocw.hokudai.ac.jp/wp-content/uploads/2016/01/GraphTheory-2007-Note-all.pdf 様々なグラフ空グラフ ( null graph ) 辺集合が無い（空の）グラフ Nn で…
[学習記録]グラフ理論2
参考資料https://ocw.hokudai.ac.jp/wp-content/uploads/2016/01/GraphTheory-2007-Note-all.pdf 定義と例単純グラフ 単純グラフ・・・グラフにループが含まれず、頂点の…
[学習記録]グラフ理論１
参考資料https://ocw.hokudai.ac.jp/wp-content/uploads/2016/01/GraphTheory-2007-Note-all.pdf イントロダクショングラフとは何か グラフ ・・・ 点（Vertex）および…
[学習記録]AtCoder EDP O-Matching [Go]
問題N 人の男性たちと N 人の女性たちがいます。 男性たちには1,2,…,N と番号が振られています。 同様に、女性たちには 1,2,…,N と番号が振られています。
各 i,j (1≤i,j≤N) について、男性 i と女性 j の相性の良し悪しが整数 ai,j によって与えられます。 ai,j=1 ならば男性 i と女性 j は相性が良く、ai,j=0 ならば相性が悪いです。
太郎
[学習記録]AtCoder EDP N-Slimes[Go]
問題N 匹のスライムが横一列に並んでいます。 最初、左から i 番目のスライムの大きさは ai です。
太郎君は、すべてのスライムを合体させて 1 匹のスライムにしようとしています。 スライムが 1 匹になるまで、太郎君は次の操作を繰り返し行います。
左右に隣り合う 2 匹のスライムを選び、それらを合体させて新しい 1 匹のスライムにする。 合体前の 2 匹のスライムの大きさを x および
[学習記録]AtCoder EDP M-Candies[Go]
問題N 人の子供たちがいます。 子供たちには 1,2,…,N と番号が振られています。
子供たちは K 個の飴を分け合うことにしました。 このとき、各 i (1≤i≤N) について、子供 i が受け取る飴の個数は 0 以上 ai 以下でなければなりません。 また、飴が余ってはいけません。
子供たちが飴を分け合う方法は何通りでしょうか？ 10^9+7 で割った余りを求めてください。 ただし、2
[学習記録]AtCoder EDP L-Deque[Go]
問題太郎君と次郎君が次のゲームで勝負します。
最初に、数列 a=(a1,a2,…,aN) が与えられます。 a が空になるまで、二人は次の操作を交互に行います。 先手は太郎君です。
a の先頭要素または末尾要素を取り除く。 取り除いた要素を x とすると、操作を行った人は x 点を得る。
ゲーム終了時の太郎君の総得点を X、次郎君の総得点を Y とします。 太郎君は X−Y を最大化し
[学習記録]AtCoder EDP K-Stones[Go]
問題N 個の正整数からなる集合 A={a1,a2,…,aN} があります。 太郎君と次郎君が次のゲームで勝負します。
最初に、K 個の石からなる山を用意します。 二人は次の操作を交互に行います。 先手は太郎君です。
A の元 x をひとつ選び、山からちょうどx 個の石を取り去る。
先に操作を行えなくなった人が負けです。 二人が最適に行動すると仮定したとき、どちらが勝つかを判定してくださ
[学習記録]AtCoder EDP J-Sushi[Go]
問題N 枚の皿があります。 皿には 1,2,…,N と番号が振られています。 最初、各 i (1≤i≤N) について、皿 i には ai (1≤ai≤3) 個の寿司が置かれています。
すべての寿司が無くなるまで、太郎君は次の操作を繰り返し行います。
1,2,…,N の目が等確率で出るサイコロを振り、出目を i とする。 皿 �i に寿司がある場合、皿 i の寿司を 1 個食べる。 皿i に
[学習記録]AtCoder EDP I-Coins[Go]
問題N を正の奇数とします。
N 枚のコインがあります。 コインには 1,2,…,N と番号が振られています。 各 i (1≤i≤N) について、コイン i を投げると、確率 pi で表が出て、確率 1−pi で裏が出ます。
太郎君は N 枚のコインをすべて投げました。 このとき、表の個数が裏の個数を上回る確率を求めてください。
解法コインがi 枚目が表の時、裏の時を全て計算していると、
[学習記録]AtCoder EDP H-Grid-1[Go]
問題縦H 行、横 W 列のグリッドがあります。 上から i 行目、左から j 列目のマスを (i,j) で表します。
各 i,j (1≤i≤H, 1≤j≤W) について、マス (i,j) の情報が文字 ai,j によって与えられます。 ai,j が . ならばマス (i,j) は空マスであり、ai,j が # ならばマス (i,j) は壁のマスです。 マス (1,1)(1,1) および (
[学習記録]AtCoder EDP G-Longest Path[Go]
問題問題文
N 頂点 M 辺の有向グラフ G があります。 頂点には 1,2,…,N と番号が振られています。 各 i (1≤i≤M) について、i 番目の有向辺は頂点 xi から yi へ張られています。G は有向閉路を含みません。
G の有向パスのうち、最長のものの長さを求めてください。 ただし、有向パスの長さとは、有向パスに含まれる辺の本数のことです。
解法誤った解法
与えられた
[学習記録]グラフ理論3
参考資料https://ocw.hokudai.ac.jp/wp-content/uploads/2016/01/GraphTheory-2007-Note-all.pdf
様々なグラフ空グラフ ( null graph )
辺集合が無い（空の）グラフ
Nn で表される
完全グラフ (complete graph)
相異なる点がすべて隣接しているグラフ。（ループや多重辺を含まない）
Kn で表
[学習記録]グラフ理論2
参考資料https://ocw.hokudai.ac.jp/wp-content/uploads/2016/01/GraphTheory-2007-Note-all.pdf
定義と例単純グラフ
単純グラフ・・・グラフにループが含まれず、頂点のどの対も高々１つのリンクで結ばれているグラフ
V(G)：グラフＧの点集合 vertex set
E(G)：グラフＧの辺集合 edge set
ψg ：グ
[学習記録]グラフ理論１
参考資料https://ocw.hokudai.ac.jp/wp-content/uploads/2016/01/GraphTheory-2007-Note-all.pdf
イントロダクショングラフとは何か
グラフ ・・・ 点（Vertex）および辺（Edge）からなる図形
次数 ・・・ ある点を端点とする辺の数
次数は点を指定することにより定義される量になる
deg(P) = 3, d
[学習記録]AtCoder EDP F-LCS
問題問題文
文字列 s および t が与えられます。 s の部分列かつ t の部分列であるような文字列のうち、最長のものをひとつ求めてください。
制約
s および t は英小文字からなる文字列である。
1≤∣s∣,∣t∣≤3000
解法s, tを１文字ずつ取り出し、処理を行う。dpには最大文字数を記録する。
マッチした → １文字前の最大長 ＋ １（マッチした文字）
マッチしない
[学習記録]AtCoder EDP E-Knapsack 2[Go]
問題問題文
N 個の品物があります。 品物には 1,2,…,N と番号が振られています。 各 i (1≤i≤N) について、品物 i の重さは wi で、価値は vi です。
太郎君は、N 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 ナップサックの容量はW であり、持ち帰る品物の重さの総和は W 以下でなければなりません。
太郎君が持ち帰る品物の価値の総和
[学習記録]AtCoder EDP D-Knapsack 1[Go]
問題問題文
N 個の品物があります。 品物には 1,2,…,N と番号が振られています。 各 i (1≤i≤N) について、品物 i の重さは wi で、価値は vi です。
太郎君は、N 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 ナップサックの容量は W であり、持ち帰る品物の重さの総和は W 以下でなければなりません。
太郎君が持ち帰る品物の価値の総
[学習記録]AtCoder EDP C-Vacation[Go]
問題文明日から太郎君の夏休みが始まります。 太郎君は夏休みの計画を立てることにしました。
夏休みは N 日からなります。 各 i (1≤i≤N) について、i 日目には太郎君は次の活動のうちひとつを選んで行います。
A: 海で泳ぐ。 幸福度 ai を得る。
B: 山で虫取りをする。 幸福度 bi を得る。
C: 家で宿題をする。 幸福度 ci を得る。
太郎君は飽き性なので、22