問題文 https://community.topcoder.com/stat?c=problem_statement&pm=14000&rd=16624 問題概要 数のリスト $\mathit{ num }$ が与えられる．$| \mathit{ num } | = N$ とする． $N$ 頂点の木であって，$i$ 番目の頂点の次数が $\mathit{ num }_i$ であるよ…

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13951&rd=16551 問題概要 正整数からなる列 $w$ が与えられる．4 要素からなる $w$ の部分列をとって $\{ a, b, c, d \}$ としたとき，$ac = bd$ となっているものの総数を求めよ． $4 \l…

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=14010&rd=16551 問題概要 ';' + 1 つ以上の '_' + ';' という文字列を顔文字であるとする．例えば ";_;" や ";____;" は顔文字であるが，";;" や ";_" は顔文字ではない． ';' と '_' か…

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13990&rd=16550 問題概要 $N$ 頂点の木と 2 種類のトークンを使った 2 人ゲームをする．プレイヤーを A, B として，A は赤いトークンを，B は青いトークンを使う． 木の頂点は $0$ から $…

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=14059&rd=16550 問題概要 '(' と ')' からなる，括弧がバランスした文字列 $S$ が与えられる．4 つの性質， 長さが $S$ と等しい 括弧がバランスしている $S$ と等しくない $S$ との最長…

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13955&rd=16515 問題概要 $N$ 頂点の木があって，各頂点は $0$ から $N - 1$ で番号付けられている．木の情報は配列 $\mathit{ parent }$ で与えられ，有効な $i$ について，頂点 $i + 1$…

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13751&rd=16515 問題概要 文字列に対して，以下の操作を考える 文字列のどこか（先頭，末尾も許容）に，文字列 "ab" を挿入する 空文字列から始めてこの操作を複数回適用することで，文字…

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13744&rd=16515 問題概要 全ての頂点の出次数が高々 1 であるような，$N$ 頂点の有向グラフが与えられる．このグラフにおいて頂点 0 から辺に沿って移動したとき，出次数 0 の頂点に到達…

問題文 http://codeforces.com/contest/583/problem/D 問題概要 $n$ 項の数列を $T$ 回繰り返した，$nT$ 要素の数列 $a$ が与えられる（与えられるのは最初の $n$ 要素のみ）．$a$ の単調非減少な部分列の内，最長のものの長さを求めよ． $1 \leq n \leq 100…

問題文 http://codeforces.com/contest/583/problem/C 問題概要 $n$ 要素の数列 $a$ から生成されるGCD Table を，$$g_{ ij } = \mathrm{ gcd }( a_i, a_j )$$ なる $n \times n$ 行列とする． 今，$g$ の要素を適当に並び替えた $n \times n$ 個の整数が与…

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13987&rd=16547 問題概要 問題設定は Division 2, Level 2 と同一だが制約が異なる． $1 \leq N \leq 50$ $1 \leq M \leq 20$

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13947&rd=16549 問題概要 初めに正整数の多重集合 $a$ がある．$|a| > 1$ である間，以下の操作をする． $a$ から要素を 2 つ取り除き，それらを $x, y$ とする． $a$ に $x + y$ を加え…

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13948&rd=16549 問題概要 $M $ 曲の歌があって，歌 $i$ はアイドル $s_i$ にのみ歌うことができる．コンサートで歌 $i$ を歌うと聴衆の幸福度が $h_i$ 上がる．また，各アイドルはコンサ…

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13946&rd=16549 問題概要 整数 $S$ が与えられる． 最初，$S$ のみを含む多重集合が手元にあり，以下の操作を（それが可能な限りにおいて）好きなだけ行うことができる． 集合の元を一つ…

問題文 http://abc029.contest.atcoder.jp/tasks/abc029_d 問題概要 正整数 $N$ が与えられる．$N$ 以下の正整数全てを 10 進数で表したとき，出現する 1 の個数を求めよ． $N

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13988&rd=16547 問題概要 特殊なコンピュータがあり，コンピュータにはサイズ $M $ のメモリが積まれている． このコンピュータ上で $N$ 個の命令を実行したい．各命令は，コンピュータ上…

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13989&rd=16547 問題概要 平面上の 2 点 $A$, $B$ が与えられる．以下の条件を満たす点 $C$ を 1 つ求めよ． $C \neq A$ かつ $C \neq B$ $C$ のそれぞれの座標は $-100$ 以上 $100$ 以下…

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=14004&rd=16548 問題概要 平面上の点が 4 個与えられる．これらの点が正方形を成すか？ なお，与えられる点は相異なる．

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=14005&rd=16548 問題概要 $N$ 文字からなる文字列 $\mathit{ message }$ に対し，次の操作を考える． 各位置 $i$ について，$\mathit{ message }_i$ の文字が位置 $\mathit{ key }_i$ に…

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13846&rd=16548 問題概要 $R \times C$ のグリッド状の盤面がある．この盤面上で，上下左右に隣接するセルにのみ移動することができる．任意のセルから始めて，任意のセルで終わる移動で…

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13916&rd=16513 問題概要 いくつかの石が 2 つの山に分けられて積まれている．片方の山に積まれている石の数は $A$ 個で，他方の山のそれは $B$ 個である． この 2 つの山に対し，次の操…

問題文 http://yukicoder.me/problems/392 問題概要 整数 $N$, $M $ が与えられる．$N^M $ を求めよ． $0 \leq N, M \leq 10^{100000}$

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13748&rd=16416 問題概要 英小文字の内 1 種類の文字からなる文字列 を送ったが，伝送途中で丁度 文字が異なる文字に変わってしまった． と が与えられるので，元の文字列として考えられ…

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13749&rd=16416 問題概要 枚のパンケーキがあって， 番のパンケーキの大きさは ，美味しさは である． このパンケーキ群を，以下の手順で積み上げる ランダムに 1 枚のパンケーキを選び，…

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13747&rd=16416 問題概要 枚のパンケーキがあって， 番のパンケーキの大きさは ，美味しさは である． このパンケーキ群を，以下の手順で積み上げる ランダムに 1 枚のパンケーキを選び，…

はじめに 動的計画法のパターンの一つで，「Digit DP」とか「桁 DP」と呼ばれているものがあります．問題によって異なってくる部分もありますが，問題によらず共通している部分がかなりあるので，その部分を中心に解説してみたいと思います． Digit DP とは…

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13709&rd=16415 問題概要 グリッド状の盤面に色を塗る．盤面上のセルは最初，全て白に塗られている．可能な操作は，与えられた整数 について， の矩形領域を任意に選択して，その内部全体…

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13719&rd=16415 問題概要 グリッド状の盤面がある．この盤面の各セルを白または黒に塗る．いくつかのセルについては塗る色が決まっているが，色が決まっていないセルもある． 塗り方の情…

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13721&rd=16415 問題概要 大きさが の長方形の紙がある．この紙を辺に平行かつ，操作後の紙の辺の長さが共に整数となるような線で折りたたむ操作ができる． 面積が となるように折りたた…

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13694&rd=16318 問題概要 文字列 について，その文字列の得点を次のように定める インデックスの対 であって，部分文字列 がただ一種類の文字から成るようなものの個数 今，文字列 が与え…