読者です 読者をやめる 読者になる 読者になる

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, …

Codeforces #237, D : Minesweeper 1D

問題文 http://codeforces.com/contest/404/problem/D 問題概要 一次元でのマインスイーパーを考える。盤面は文字列で表され、各文字は "*012" のいずれかである。'*' は爆弾を表し、数字は隣接するセルに存在する爆弾の数の合計を表す。 今、"*012" に '?' …

TopCoder SRM 612, Division 2, Level 2 : EmoticonsDiv2

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13041&rd=15845 問題概要 丁度一つの顔文字を含むテキストファイルを、次の二種類の操作によって編集する。 バッファにある全ての文字列をクリップボードにコピーする クリップボードの文…

Codeforces #235, D : Roman and Numbers

問題文 http://codeforces.com/contest/401/problem/D 問題概要 18 桁以下の整数 n と、100 以下の整数 m が与えられる。次の condition をすべて満たすような整数の数を求めよ。 n の各桁の並び替えによって得られる Leading Zero をもたない modulo m の値…

TopCoder SRM 610, Division 1, Level 2 : AlbertoTheAviator

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13024&rd=15843 問題概要 量 F の燃料を積載した航空機があり、これを用いていくつかの「任務」をこなしたい。任務は複数個あり、i 番の任務を遂行するためには duration[ i ] の燃料が必…

Codeforces #232, Division 1, A ( Division 2, B ) : On Number of Decompositions into Multipliers

問題文 http://codeforces.com/contest/397/problem/C 概要 n 項からなる数列 a が与えられる。 とする。n 項からなる整数の列であって、総乗が m と等しくなるものの数を mod で求めよ。

TopCoder SRM 609, Division 2, Level 3 : VocaloidsAndSongs

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12989&rd=15842 問題概要 三人の歌手がいて、S 曲からなるアルバムを作ろうとしている。全ての曲は、1 〜 3 人で歌われなければならない。更に、それぞれの歌手がアルバム中で歌う曲の総…

TopCoder SRM 605, Division 1, Level 1 : AlienAndHamburgers

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12948&rd=15838 問題概要 N 個のハンバーガーがある。各ハンバーガーは二つの属性 type と taste をもち、それぞれ整数値で表される。 これらのハンバーガーのうち、いくつかを選んで食べ…

TopCoder SRM 602, Division 2, Level 3 : BlackBoxDiv2

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12929&rd=15820 概要 正方形のグリッドからなる長方形の盤面がある。各グリッドには、高々一つのブロックを置くことができるが、配置完了後の盤面を正面及び横から見たときの見え方が指定…

TopCoder SRM 602, Division 2, Level 2 : PilingRectsDiv2

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12928&rd=15820 概要 N 個の長方形があり、i 番の長方形の高さは Y[ i ] 、幅は X[ i ] である。この内いくつかを選んで机の上に置く。このとき、長方形の辺はいずれかの座標軸に並行でな…

TopCoder SRM 602, Division 1, Level 1 : TypoCoderDiv1

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12924&rd=15820 概要 あるコンテストでのレーティングシステムでは、2200 以上を brown coder 、2200 未満を ciel coder と呼ぶ。ねこの Lower は現状 ciel coder であり、今年の終わりで…

TopCoder SRM 599, Divisin 2, Level 3 : SimilarNames2

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12871&rd=15711 概要 相異なる複数の文字列と整数 L が与えられる。この文字列群の並び替えであって、L - 2 以下の各 i について i 番目の文字列が i + 1 番目の文字列のプレフィックスと…

AtCoder Beginner Contest #003, D : AtCoder社の冬

問題文 http://abc003.contest.atcoder.jp/tasks/abc003_4 概要 の盤面上に 'D', 'L', '-' が配置されている。このとき、全ての '-' 以外の文字を内部に含む最小の矩形領域の大きさは となった。盤面上には 'D' が D 個、'L' が L 個ある。盤面の配置として …

Codeforces #214, C : Dima and Salad

問題文 http://codeforces.com/contest/366/problem/C 概要 N 種類の野菜があり、i 番の野菜は甘さが でカロリーが である。 この中からいくつかの野菜を選び、できるだけ甘いサラダを作りたい。 ただし、選んだ野菜の集合を S としたとき、 となるようにし…

TopCoder SRM 596, Division 2, Level 2 : ColorfulRoad

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12837&rd=15708 概要 一直線上の道があり、道は N 個の部分に分かれている。 各部分は左端から 0, 1, 2, ... と番号付けられる。 各部分には色がついていて、色は 'R', 'G', 'B' の三種類…

TopCoder SRM 595, Division 2, Level 3 : LittleElephantAndXor

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12623&rd=15707 概要 整数 A, B, C が与えられる。 次の cond を満たすタプル ( x, y ) の数を求めよ x y x XOR y

TopCoder SRM 594, Division 1, Level 1 : AstronomicalRecords

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12804&rd=15706 概要 ある惑星系にあるいくつかの惑星の大きさの比を、恒星に近いものから順に並べたものが二つ与えられる。 惑星系にある惑星の数の最小数を求めよ。

Codeforces #205, C : Find Maximum

問題文 http://codeforces.com/contest/353/problem/C 概要 N 項からなる数列 a がある。 関数 f を次のように定める。 ただし bit(i) は x の i bit 目が立っているときに 1 になる関数 x が m 以下のとき、f(x) の最大値を求めよ。

TopCoder SRM 593, Division 2, Level 2 : WolfDelaymaster

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12778&rd=15705 概要 次のような文字列を valid であるとする。 ある正整数 k があって、k 個の 'w' の連続 + k 個の 'o' の連続 + k 個の 'l' の連続 + k 個の 'f' の連続 である文字列 …

TopCoder SRM 590, Division 2, Level 3 : FoxAndShogi

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12745&rd=15702 概要 '.', 'U', 'D' からなるグリッド状の盤面が与えられる。 一回の操作は次の二つの操作の内いずれかを行うことができる。 その上のセルが '.' である 'U' を一つ選び、…

TopCoder SRM 588, Division 2, Level 2 : GUMIAndSongsDiv2

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12707&rd=15700 概要 N 個の曲があって、それぞれについて長さとトーンの情報が与えられる。 曲 x の次に曲 y を歌うとき、そのトーンの差の絶対値だけ時間を開けなければ歌えない。 時間…