hogecoder

つたじろう(Tsuta_J) 競技プログラミングの記録

動的計画法

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に入って提出は何回かしてたのだけど、まだ不慣れで最初の方はコンパイルエラー出しまくった。 今度はすんなり…