Hota T

Goでの競技プログラミングについての記事を少々 だらだらやってたけどきょうからまじめに…

Hota T

Goでの競技プログラミングについての記事を少々 だらだらやってたけどきょうからまじめにやる

[学習記録]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 ならば相性が悪いです。 太郎君は、相性が良い男女どうしのペアを N 組作ろうとしています。 このとき、各男性

Hota T

    • [学習記録]AtCoder EDP N-Slimes[Go]

      問題N 匹のスライムが横一列に並んでいます。 最初、左から i 番目のスライムの大きさは ai​ です。 太郎君は、すべてのスライムを合体させて 1 匹のスライムにしようとしています。 スライムが 1 匹になるまで、太郎君は次の操作を繰り返し行います。 左右に隣り合う 2 匹のスライムを選び、それらを合体させて新しい 1 匹のスライムにする。 合体前の 2 匹のスライムの大きさを x および y とすると、合体後のスライムの大きさは x+y となる。 このとき、太郎君は

      Hota T

      • [学習記録]AtCoder EDP M-Candies[Go]

        問題N 人の子供たちがいます。 子供たちには 1,2,…,N と番号が振られています。 子供たちは K 個の飴を分け合うことにしました。 このとき、各 i (1≤i≤N) について、子供 i が受け取る飴の個数は 0 以上 ai​ 以下でなければなりません。 また、飴が余ってはいけません。 子供たちが飴を分け合う方法は何通りでしょうか？ 10^9+7 で割った余りを求めてください。 ただし、2 通りの方法が異なるとは、ある子供が存在し、その子供が受け取る飴の個数が異なるこ

        Hota T

        • [学習記録]AtCoder EDP L-Deque[Go]

          問題太郎君と次郎君が次のゲームで勝負します。 最初に、数列 a=(a1​,a2​,…,aN​) が与えられます。 a が空になるまで、二人は次の操作を交互に行います。 先手は太郎君です。 a の先頭要素または末尾要素を取り除く。 取り除いた要素を x とすると、操作を行った人は x 点を得る。 ゲーム終了時の太郎君の総得点を X、次郎君の総得点を Y とします。 太郎君は X−Y を最大化しようとし、次郎君は X−Y を最小化しようとします。 二人が最適に行動すると仮

          Hota T

        [学習記録]AtCoder EDP O-Matching [Go]

        Hota T

          [学習記録]AtCoder EDP K-Stones[Go]

          問題N 個の正整数からなる集合 A={a1​,a2​,…,aN​} があります。 太郎君と次郎君が次のゲームで勝負します。 最初に、K 個の石からなる山を用意します。 二人は次の操作を交互に行います。 先手は太郎君です。 A の元 x をひとつ選び、山からちょうどx 個の石を取り去る。 先に操作を行えなくなった人が負けです。 二人が最適に行動すると仮定したとき、どちらが勝つかを判定してください。 解法 i 個の石で、j 番目まで使って勝負するDPを考える 太郎君がとれ

          Hota T

          [学習記録]AtCoder EDP K-Stones[Go]

          Hota T

          [学習記録]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 に寿司が無い場合、何も行わない。 すべての寿司が無くなるまでの操作回数の期待値を

          Hota T

          [学習記録]AtCoder EDP J-Sushi[Go]

          Hota T

          [学習記録]AtCoder EDP I-Coins[Go]

          問題N を正の奇数とします。 N 枚のコインがあります。 コインには 1,2,…,N と番号が振られています。 各 i (1≤i≤N) について、コイン i を投げると、確率 pi​ で表が出て、確率 1−pi​ で裏が出ます。 太郎君は N 枚のコインをすべて投げました。 このとき、表の個数が裏の個数を上回る確率を求めてください。 解法コインがi 枚目が表の時、裏の時を全て計算していると、 保持する値の数が 2 ^N となり、不可能。 i 枚目までのコインを使って、j

          Hota T

          [学習記録]AtCoder EDP I-Coins[Go]

          Hota T

          [学習記録]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) および (H,W) は空マスであることが保証されています。 太郎君は、マス (1,1)(

          Hota T

          [学習記録]AtCoder EDP H-Grid-1[Go]

          Hota T

          [学習記録]AtCoder EDP G-Longest Path[Go]

          問題問題文 N 頂点 M 辺の有向グラフ G があります。 頂点には 1,2,…,N と番号が振られています。 各 i (1≤i≤M) について、i 番目の有向辺は頂点 xi​ から yi​ へ張られています。G は有向閉路を含みません。 G の有向パスのうち、最長のものの長さを求めてください。 ただし、有向パスの長さとは、有向パスに含まれる辺の本数のことです。 解法誤った解法 与えられた条件から、各頂点を通ったときの最大値を保持し、それの最大を取れば計算できそうに思

          Hota T

          [学習記録]AtCoder EDP G-Longest Path[Go]

          Hota T

          [学習記録]グラフ理論3

          参考資料https://ocw.hokudai.ac.jp/wp-content/uploads/2016/01/GraphTheory-2007-Note-all.pdf 様々なグラフ空グラフ ( null graph ) 辺集合が無い（空の）グラフ Nn で表される 完全グラフ (complete graph) 相異なる点がすべて隣接しているグラフ。（ループや多重辺を含まない） Kn　で表される。 辺の数は n C 2 = n(n-1) / 2 で表される 正則グラ

          Hota T

          [学習記録]グラフ理論3

          Hota T

          [学習記録]グラフ理論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 ：グラフＧの接続関数 接続関数とは、Ｇの各辺にＧの頂点を対応させる関数である。 V

          Hota T

          [学習記録]グラフ理論2

          Hota T

          [学習記録]グラフ理論１

          参考資料https://ocw.hokudai.ac.jp/wp-content/uploads/2016/01/GraphTheory-2007-Note-all.pdf イントロダクショングラフとは何か グラフ　・・・　点（Vertex）および辺（Edge）からなる図形 次数　　・・・　ある点を端点とする辺の数 次数は点を指定することにより定義される量になる deg(P) = 3, deg(Q) = 4 点の数　＝　位数、点数、ｎ、｜G｜（グラフをGとしたとき）

          Hota T

          [学習記録]グラフ理論１

          Hota T

          [学習記録]AtCoder EDP F-LCS

          問題問題文 文字列 s および t が与えられます。 s の部分列かつ t の部分列であるような文字列のうち、最長のものをひとつ求めてください。 制約 s および t は英小文字からなる文字列である。 1≤∣s∣,∣t∣≤3000 解法s, tを１文字ずつ取り出し、処理を行う。dpには最大文字数を記録する。 マッチした　　→　１文字前の最大長　＋　１（マッチした文字） マッチしない　→　１文字前の最大長(s) と　１文字前の最大長(t)の最大 for i :=

          Hota T

          [学習記録]AtCoder EDP F-LCS

          Hota T

          [学習記録]AtCoder EDP E-Knapsack 2[Go]

          問題問題文 N 個の品物があります。 品物には 1,2,…,N と番号が振られています。 各 i (1≤i≤N) について、品物 i の重さは wi​ で、価値は vi​ です。 太郎君は、N 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 ナップサックの容量はW であり、持ち帰る品物の重さの総和は W 以下でなければなりません。 太郎君が持ち帰る品物の価値の総和の最大値を求めてください。 制約 入力はすべて整数である。 1≤N≤100

          Hota T

          [学習記録]AtCoder EDP E-Knapsack 2[Go]

          Hota T

          [学習記録]AtCoder EDP D-Knapsack 1[Go]

          問題問題文 N 個の品物があります。 品物には 1,2,…,N と番号が振られています。 各 i (1≤i≤N) について、品物 i の重さは wi​ で、価値は vi​ です。 太郎君は、N 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 ナップサックの容量は W であり、持ち帰る品物の重さの総和は W 以下でなければなりません。 太郎君が持ち帰る品物の価値の総和の最大値を求めてください。 制約 入力はすべて整数である。 1≤N≤10

          Hota T

          [学習記録]AtCoder EDP D-Knapsack 1[Go]

          Hota T

          [学習記録]AtCoder EDP C-Vacation[Go]

          問題文明日から太郎君の夏休みが始まります。 太郎君は夏休みの計画を立てることにしました。 夏休みは N 日からなります。 各 i (1≤i≤N) について、i 日目には太郎君は次の活動のうちひとつを選んで行います。 A: 海で泳ぐ。 幸福度 ai​ を得る。 B: 山で虫取りをする。 幸福度 bi​ を得る。 C: 家で宿題をする。 幸福度 ci​ を得る。 太郎君は飽き性なので、22 日以上連続で同じ活動を行うことはできません。 太郎君が得る幸福度の総和の最大値

          Hota T

          [学習記録]AtCoder EDP C-Vacation[Go]

          Hota T