torus711 のアレ

主に競技プログラミングの問題について書きます

動的計画法

TopCoder SRM 671, Division 1, Level 1 : BearCries

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

Codeforces 323, Division 1, B ( Division 2, D ) : Once Again...

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

TopCoder, Single Round Match 667, Division 1, Level 1 : OrderOfOperations

問題文 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$

AtCoder Biginner Contets 029, D - 1

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

TopCoder, Single Round Match 667, Division 2, Level 2 : OrderOfOperationsDiv2

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

TopCoder, Single Round Match 656, Division 1, Level 1 : RandomPancakeStack

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

TopCoder, Single Round Match 654, Division 1, Level 1 : SquareScores

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

TopCoder, Single Round Match 653, Division 1, Level 1 : CountryGroupHard

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13688&rd=16317 問題概要 何人かの人が一列に並んでいる.人々は,出身が同じ人同士は連続した位置に座っていることが分かっている.それぞれの人に対し,「同じ出身の人は何人いるか」と…

TopCoder, Single Round Match 653, Divisino 2, Level 3 : SingingEasy

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13685&rd=16317 問題概要 Alice と Bob はある歌を歌おうとしている.今,歌に表れる音階を の整数で表す(値が音の高さを表す).また,歌おうとしている曲は配列 で表される. Alice と…

TopCoder, Single Round Match 650, Division 2, Level 2 : TaroFillingAStringDiv2

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13668&rd=16314 問題概要 'A', 'B', '?' からなる文字列 が与えられる.この文字列中の '?' を 'A' まては 'B' に(独立に)置き換えることを考える. 文字列の "ugliness"(醜さ)を,文…

TopCoder, Single Round Match 649, Division 2, Level 2 : CartInSupermarketEasy

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13659&rd=16313 問題概要 一列に連結された 個のショッピングカートがある.次の 2 種類の操作を繰り返し適用して,全てのカートをできるだけ早く消し去りたい. それぞれの列を,より短…

TopCoder, Single Round Match 649, Division 1, Level 1 : Decipherability

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13656&rd=16313 問題概要 文字列 と正整数 が与えられる. から 文字を削除して得られる文字列が与えられたとき,削除された文字の位置を一意に特定できるか否か,求めよ.

TopCoder, Single Round Match 648, Division 2, Level 3 : ABC

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13645&rd=16312 問題概要 二つの正整数 が与えられる.次の条件を満たす文字列 を 1 つ求めよ.存在しない場合は空文字列で示せ. は 文字からなり, である. 整数の順序対 であって, …

TopCoder, Single Round Match 648, Division 1, Level 1 : AB

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13642&rd=16312 問題概要 二つの正整数 が与えられる.次の条件を満たす文字列 を 1 つ求めよ.存在しない場合は空文字列で示せ. は 文字からなり, を構成する各文字は 'A' または 'B' …

TopCoder, Single Round Match 647, Division 1, Level 2 : CtuRobots

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13595&rd=16279 問題概要 何体かのロボットが売られていて, 番のロボットの価格は ,燃料タンクの容量は である.購入時に燃料タンクは満タンの状態になっている.これらのロボットの内…

TopCoder, Single Round Match 642, Division 1, Level 1 : WaitingForBus

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13540&rd=16085 問題概要 Joseph の住む町のバスターミナルは確率的に営業される. バスターミナルの開業前,バスターミナルには 台のバスが待機していて,各バスは で番号付けられる.ま…

Codeforces #274, Division 1, C ( Division 2, E ) : Riding in a Lift

問題文 http://codeforces.com/contest/480/problem/C 問題概要 階ある建物のエレベーターで遊ぶ。プレイヤーは最初 階にいて、 階に行くことはできない。また、 階から 階に移動するとき、 かつ でなければならない。このルールを守って 回移動するとき、移…

Codeforces #272, Division 1, C ( Division 2, E ) : Dreamoon and Strings

問題文 http://codeforces.com/contest/477/problem/C 問題概要 二つの文字列 が与えられる。 から 文字を消去したとき、 が に重複しない部分文字列として表れる個数の最大値を全ての について求めよ。

Codeforces #271, D : Flowers

問題文 http://codeforces.com/contest/474/problem/D 問題概要 'W', 'R' からなる文字列であって、出現する全ての 'W' を互いに交差しない、連続した長さ の区間に分割できるものについて考える。 以下の形式のクエリを 件処理せよ。 二つの整数 が与えられ…

Codeformula 2014 本選, D : 映画の連続視聴

問題文 http://code-formula-2014-final.contest.atcoder.jp/tasks/code_formula_2014_final_d 問題概要 種類の映画がある。 番の映画の種類は で、時刻 に始まって に終わる。 高橋くんは同じ種類の映画を連続して観ることで、より多くの幸福度を得る。同じ…

TopCoder, SRM 627, Division 2, Level 3 : BubbleSortWithReversals

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13256&rd=16008 問題概要 整数列 が与えられる。高々 個のオーバーラップしない の連続する部分列を反転させる操作をした後、 をバブルソートで昇順ソートする。発生する交換操作の回数を…

TopCoder, SRM 626, Division 1, Level 1 : FixedDiceGameDiv1

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13239&rd=15859 問題概要 複数のサイコロを使った二人ゲームを考える。Alice は 個の 面サイコロを、Bob は 個の 面サイコロを使用する。二人は同時に全てのサイコロを振り、出目の和が大…

TopCoder, SRM 623, Division 1, Level 2 : CatchTheBeat

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12807&rd=15856 問題概要 次のようなゲームをする。 2D ゲームである プレイヤーキャラクターの初期位置は原点 ( 0, 0 ) プレイヤーキャラクターは X 軸上のみを移動することができ、その…

TopCoder, SRM 621, Division 2, Level 2 : NumbersChallenge

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13166&rd=15854 問題概要 整数の(多重)集合 S が与えられる。S の部分和として現れない最小の非負整数を求めよ。

AtCoder Beginner Contest #008, D : 金塊ゲーム

問題文 http://abc008.contest.atcoder.jp/tasks/abc008_4 問題概要 説明しづらいので本家問題文参照で><

Google Code Jam 2014, Round 1B, B : New Lottery Game

問題文 http://code.google.com/codejam/contest/2994486/dashboard#s=p1 問題概要 正整数 A, B, K が与えられる。a *1 *1:& は bitwise and を表す

AtCoder Beginner Contest #007 D : 禁止された数字

問題文 http://abc007.contest.atcoder.jp/tasks/abc007_4 問題概要 整数 A, B が与えられる。区間 [ A, B ] 内の値であって、10 進数表記したときに 4 または 9 を含む値(禁止された値)の個数を求めよ。

TopCoder, SRM 615, Division 2, Level 3 : MergeStrings

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13095&rd=15848 問題概要 文字列 S, A, B が与えられる。S は英大文字及び '?' からなり、A, B は英大文字からなる。二つの文字列について、'?' を(独立に)任意の文字に置き換えること…

TopCoder SRM 614, Division 2, Level 3 : TorusSailingEasy

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13085&rd=15847 問題概要 幅が N 、高さが M であって、上端と下端・左端と右端がそれぞれ繋がっている二次元のグリッド状の盤面を考える。最初、きつねのしえるが位置 ( 0, 0 ) にいる。…

TopCoder, SRM 613, Division 2, Level 3 : TaroCards

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13015&rd=15846 問題概要 2 つの正整数が書かれたカードが N 枚ある。i 番のカードに書かれた一つ目の値は first[ i ] であり、二つ目のそれは second[ i ] である。ここで、配列 first, …