hogecoder

tsutaj 競技プログラミングの記録

動的計画法

FaceBook Hacker Cup 2021 Qualification Round C: Gold Mine

問題概要 問題原文 → Problem C2: Gold Mine - Chapter 2 | Facebook Hacker Cup - 2021 - Qualification Round 頂点の木があり、それぞれの頂点 には重み がついている。木から高々 個の辺素パスを取るとき、パスに含まれる重みの和の最大値を求めよ (ただ…

AtCoder Grand Contest 030 F: Permutation and Minimum

問題概要 日本語があるので原文参照 → F - Permutation and Minimum 解説 と の順序は答えにあまり関係ないので、数列を 2 個のブロックに区切って考えていき、ブロックの中は (左の値) < (右の値) という関係が常に成り立つものとする。ブロックの状態とし…

Codeforces Round #576 Div.1 D: Rectangle Painting 1

本番は嘘解法で通してしまったのでちゃんと書きます。 問題概要 原文 → Problem - D - Codeforces のグリッド状のマスが与えられ、それぞれは白または黒に塗られている。 このマスの任意の 長方形領域に対して、その領域内にあるマスを全て白にするという操…

TCO19 Round3A Med: WaitingForBusAgain

問題概要 原文 → TopCoder Statistics - Problem Statement 種類のバスがあり、 番目のバスは 分おきに停留所に到着することがわかっている。 それぞれのバスについて、来る間隔だけはわかっているがどのタイミングからその間隔で来るかは一様にランダムであ…

AOJ 2436: Card

同じ方針でやっている人があまりいなさそうなので一応書きます。 問題概要 日本語なので原文を参照してください → Card | Aizu Online Judge 解説 整数を組み合わせて最終的に という数を作ったとします。与えられるそれぞれの整数について、その整数の 1 の…

TopCoder SRM 718 Div1 Easy (Div2 Med): InterleavingParenthesis

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 括弧列 と が与えられる。 に の各文字を、 の文字間の相対位置関係を変えずに挿入することを考える。このとき、 valid な括弧列になるパターンは何通りあるか?…

蟻本練習問題解説 Part3 (2-3)

蟻本練習問題の解説をします。今回のトピックは動的計画法です! 今回は難易度が割と混在しているため、水色 〜 青 の方でも解きごたえがある (ありそう、完全に主観) な問題に★をつけました。競技プログラミングにある程度慣れている方も、★がついている問…

TopCoder SRM 720 Div1 Easy: SumProduct

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement digit1 桁の数 と、digit2 桁の数 を、以下の条件のもとで作ることを考える。 leading zero を許す の各桁において、登場する の個数の合計は最大で 個 このよう…

TopCoder SRM 724 Div2 Hard: UnfinishedTournamentEasy

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 人のリーグ戦の表が与えられる (引き分けなし)。試合は全て終わっているわけではなく、勝敗がまだ決していない箇所は '?' で表される。 '?' を埋めたとき、勝率…

TopCoder SRM 725 Div1 Med: HiddenTree

するめうめ tsutaj.hatenablog.com 問題概要 原文 → 掲載されてないぽい (unrated だから?) 頂点が 個あり、それぞれの頂点について値 が与えられる。各頂点に という値を適切に決めたとき、以下の条件を満たす DAG がいくつできるか求めよ。なお、 の値が…

TopCoder SRM 725 Div2 Hard: HiddenTreeDiv2

するめうめ tsutaj.hatenablog.com 問題概要 原文 → 掲載されてないぽい (unrated だから?) 頂点が 個あり、それぞれの頂点について値 が与えられる。以下の条件を満たす DAG が構成できるか判定せよ。 それぞれの頂点について、入次数は高々 頂点 から到達…

TopCoder SRM 726 Div1 Easy: Unpacking

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 個の袋がある。 番目の袋には 個の赤いキャンデーと の青いキャンデーが入っていて、コストは とのことである。 それぞれの袋について、この情報は微妙に間違っ…

TopCoder SRM 726 Div2 Hard: HeroicScheduled2

するめうめ tsutaj.hatenablog.com 問題 原文 → TopCoder Statistics - Problem Statement 個の仕事があり、それぞれについてこなすために の時間がかかり、その仕事を実行できる時間が区間として決まっている。 個の仕事の部分集合であって、適切にこなすこ…

分割数 DP について

昨日の 第4回ドワンゴからの挑戦状 予選 C 問題 で、分割数 DP を必要とする問題が出されました。 蟻本をよく読んでいる人ならご存知のとおり、この DP は dp[i][j] := j を i 分割する時の場合の数 とするとき、 dp[i][j] = dp[i][j-i] + dp[i-1][j] となり…

Codeforces Round #416 (Div. 2) C: Vladik and Memorable Trip

本番出てた回。ようやく復習できました。 問題概要 原文 → Problem - C - Codeforces 長さ の数列があり、 番目の要素を と書く。 次のルールに従って区間を選ぶ (複数でも良い、数列全体を被覆するような選び方でなくても良い) とき、選んだ区間の重みの合…

TopCoder SRM 712 Div1 Easy: LR

オーバーフローで死ぬつらい問題。 問題概要 原文 → TopCoder Statistics - Problem Statement 環状になっているサイズ の数列 がある (0-indexed)。 番目の要素に対して左隣は要素 であり、右隣は要素 である。 (ただし、 番目の要素の右隣は要素 である。)…

AtCoder Regular Contest 043 B: 難易度

ARC043 B問題、データ構造で殴ってしまったけど、明らかに想定解法より楽な方法だと思うのでいちおう紹介。 問題概要 問題原文 → B: 難易度 - AtCoder Regular Contest 043 | AtCoder 長さ の数列が与えられる。この数列から、( 番目に取った数 ) ( 番目に取…

AtCoder Regular Contest 027 C: 最高のトッピングにしような

またまた DP 自力で解けた記念。 問題概要 原文 → C: 最高のトッピングにしような - AtCoder Regular Contest 027 | AtCoder 種類のトッピングがある。トッピング は 枚のチケットを交換することで入手でき、その価値は である。 チケットにはスペシャルチケ…

AOJ DPL_1_G: Knapsack Problem with Limitations

個数制限付きナップザック問題です。 問題概要 原文 → Knapsack Problem with Limitations | Aizu Online Judge 価値 で重さ であるような 種類の品物と、容量が のナップザックがある。 番目の品物は 個まで使用できる。 ナップザックの容量を超えないよう…

AOJ 1335: Equal Sum Sets

たとえ簡単な DP でも一発で通ると嬉しいよね。 問題概要 原文 → Equal Sum Sets | Aizu Online Judge 以下の相異なる自然数 個の合計が となる組み合わせの総数を求めよ。 解説 以下の各数字 について、 を使うときと使わないときを考えてみます。 を使うと…

AOJ 0097: Sum of Integers II

やっぱり俺の敵はDPだ・・・— つたじろう (@_TTJR_) 2016年8月10日 DPは難しい、はっきりわかんだね。 問題概要 原文 → 整数の和 | Aizu Online Judge 0 から 100 の数字から異なる n 個の数を取り出して合計が s となる組み合わせの数を出力せよ。 解説 私…

TopCoder SRM 694 Div 2

SRMの結果、白コーダーから灰色コーダーになった(残念だが当然)— つたじろう (@_TTJR_) July 10, 2016 今日初めてTopCoderに出てみた。 以前Arenaに入って提出は何回かしてたのだけど、まだ不慣れで最初の方はコンパイルエラー出しまくった。 今度はすんなり…