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

torus711 のアレ

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

Codeforces

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…

Codeforces 323, Division 1, A ( Division 2, C ) - GCD Table

問題文 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$ 個の整数が与…

Good Bye 2014, A : New Year Transportation

問題文 http://codeforces.com/contest/500/problem/A 問題概要 のグリッド状の盤面でゲームを行う. の各 について,セル からは 個右のセルにのみ移動することができる. セル からスタートして,セル に到達することは可能か?

Good Bye 2014, B : New Year Permutation

問題文 http://codeforces.com/contest/500/problem/B 問題概要 サイズ の順列 及び, 行列 が与えられる.また, 及び が成り立つ. 二つの整数 について, であるときに限り, と を交換することができる.任意回の操作で作ることができる列の内,辞書式順…

Good Bye 2014, C : New Year Book Reading

問題文 http://codeforces.com/contest/500/problem/C 問題概要 今,手元に 冊の本があり, 番の本の重さは である.部屋には本棚が無いので,本は縦に積まれている.ある本を読むときの手順は以下のようになる. 読みたい本の上にある本を全て持ち上げる 読…

Good Bye 2014, D : New Year Santa Network

問題文 http://codeforces.com/contest/500/problem/D 問題概要 頂点からなる重み付きの木が与えられる.辺の情報は 3 つの配列 によって与えられ, 番の辺は 2 頂点 間を結び,その重みは である.また, を,2 頂点 間の単純道のコストとする. 今,以下の…

Codeforces #274, Division 1, A ( Division 2, C ) : Exams

問題文 http://codeforces.com/contest/480/problem/A 問題概要 ある学生は 科目の試験を受ける。 番の科目の試験は、本来ならば試験期間の 日目に実施されるが、教官との交渉により 日目に受験することも認められた。 番の科目の試験を受けたとき、教官は学…

Codeforces #274, Division 1, B ( Division 2, D ) : Long Jumps

問題文 http://codeforces.com/contest/480/problem/B 問題概要 特殊な定規で 2 つの長さ を測りたい。定規の全長は であり、目盛りは 個ある。 番目の目盛りの位置は端から のところであり、 である。この定規である長さ を「測れる」とは、距離が丁度 だけ…

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, A : Keyboard

問題文 http://codeforces.com/contest/474/problem/A 問題概要 QWERTY 配列のキーボードで単語をタイピングする際、両手のポジションが右または左に 1 つずれてしまった。ポジションがずれた方向と結果として入力された単語が与えられるので、入力しようと…

Codeforces #271, B : Worms

問題文 http://codeforces.com/contest/474/problem/B 問題概要 ユニークな通し番号を付けた虫たちを 個の塊に分ける。結果、 番目 ( 1-indexed ) の塊には 匹の虫がいて、その通し番号は( 0 番目の山にいる虫の数を便宜的に とおけば) である。 以下の形…

Codeforces #271, C : Captain Marmot

問題文 http://codeforces.com/contest/474/problem/C 問題概要 直交座標をもつ平面上の点が 個与えられ、 番目の点の座標は である。また、 番目の点は座標 を中心に、反時計回りに [rad] 回転することができる。4 つずつの塊について(すなわち、有効な に…

Codeforces #271, D : Flowers

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

Codeforces #270, A : Design Tutorial: Learn from Math

問題文 http://codeforces.com/contest/472/problem/A 問題概要 整数 が与えられる。 を 2 つの合成数の和で表わせ。

Codeforces #270, B : Design Tutorial: Learn from Life

問題文 http://codeforces.com/contest/472/problem/B 問題概要 人が一階でエレベーターを待っていて、 番の人が行きたいフロアは 階である。 エレベーターには 人が同時に乗ることができ、 階から 階へ移動するのに の時間がかかる。また、人の乗り降りにか…

Codeforces #270, C : Design Tutorial: Make It Nondeterministic

問題文 http://codeforces.com/contest/472/problem/C 問題概要 要素の文字列配列 と、サイズ の順列 が与えられる。 各 について または のいずれかを選んで としたとき、 を辞書式順序に於いて単調増加にすることができるか否か、求めよ。 なお、与えられ…

Codeforces #270, D : Design Tutorial: Inverse the Problem

問題文 http://codeforces.com/contest/472/problem/D 問題概要 の行列 が与えられる。 頂点からなる木であって、頂点 間の距離が となるものは存在するか? なお構成される木は、無向・重み付きであって、辺重みは全て正である。

Codeforces #243, Division 2, A : Sereja and Mugs

問題文 http://codeforces.com/contest/426/problem/A 問題概要 容積が s である空のカップと、n 個のマグカップを使ったゲームをする。n 個のマグカップには最初水が入っていて、i 番のマグカップの内容量は である。各プレイヤーは一回ずつ、空でないマグ…

Codeforces #243, Division 2, B : Sereja and Mirroring

問題文 http://codeforces.com/contest/426/problem/B 問題概要 の行列に対する mirror 操作を、次のように定義する。 結果の行列のサイズは 結果の行列の上半分は、元になった行列と等しい 結果の行列の下半分は、元になった行列の行の順序を反転したもの …

Codeforces #243, Division 1, A ( Division 2, C ) : Sereja and Swaps

問題文 http://codeforces.com/contest/426/problem/C 問題概要 項数 n の数列 a と整数 k が与えられる。m( a ) を a の連続する部分列の和の最大値とし、a の二つの要素を交換する操作を最大 k 回できるとき、m( a ) の最大値はいくらか。 なお、 である。

Codeforces #237, A : Valera and X

問題文 http://codeforces.com/contest/404/problem/A 問題概要 文字の行列が与えられる。この行列が、対角要素が全て同じ文字であり、それ以外の要素が対角要素とは違う文字であるような行列かどうかを判定せよ。

Codeforces #237, C : Restore Graph

問題文 http://codeforces.com/contest/404/problem/C 問題概要 整数 n, k と数列 d が与えられる。以下の condition を満たすグラフを一つ示せ。存在しない場合は -1 で示せ。 頂点数が n 全ての頂点について、次数は k 以下 ある頂点 v を選んだとき、v か…

Codeforces #237, D : Minesweeper 1D

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

Codeforces #235, A : Vanya and Cards

問題文 http://codeforces.com/contest/401/problem/A 問題概要 それぞれ絶対値が x 以下の整数が一つ書かれたカードが n 枚ある。同様の(絶対値が x 以下の整数が一つ書かれたカード)を複数枚加えて、全てのカードに書かれた値の和を 0 にしたい。最小で…

Codeforces #235, B : Sereja and Contests

問題文 http://codeforces.com/contest/401/problem/B 問題概要 あるプログラミングコンテストは、参加者のレベル帯によって二つの Division 、{ Div1, Div2 } に分かれて開催されている。コンテストは、Div1, Div2 が同時に開催されるか、Div2 のみが開催さ…

Codeforces #235, C : Team

問題文 http://codeforces.com/contest/401/problem/C 問題概要 n 個の '0' と m 個の '1' を、以下の二つの condition を共に満たすような並べ方で並べよ。そのような並べ方が存在しないとき、-1 で示せ。 '0' 同士は隣接しない 連続する 3 個の文字が '1' …

Codeforces #235, D : Roman and Numbers

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

Codeforces #232, Division 2, A : On Segment's Own Points

問題文 http://codeforces.com/contest/397/problem/A 概要 数直線上の区間が n 個与えられ、i ( 1-based ) 番の区間は である。1 番の区間に含まれ、他の区間に含まれないような部分の長さを求めよ。

Codeforces #232, Division 2, B : On Corruption and Numbers

問題文 http://codeforces.com/contest/397/problem/B 概要 次のようなクエリ ( n, l, r ) を t ( ≦ 1,000 ) 個処理せよ クエリ ( n, l, r ) := n を [ l, r ] に含まれる整数の和として表現できるかどうか判定し、"Yes" / "No" で示せ

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 で求めよ。

Codeforces #231, A : Counting Sticks

問題文 http://codeforces.com/contest/394/problem/A 概要 [ A ] + [ B ] = [ C ] という形式で数式が与えられる。A, B, C はそこに含まれるバーティカルバー( '|' )の本数に対応する値を表す。 A, B, C 間で棒を動かす操作が一回まで許される。等式を成…

Codeforces #231, C : Dominoes

問題文 http://codeforces.com/contest/394/problem/C 問題概要 のフィールドに文字列 = { "00","01, "10, "11" } が並んでいる。この文字列に対し、以下の二つの操作を任意回できる。 場所を並び替える 文字列を反転する 列の総和の最大値を最小化するよう…

Codeforces #226, A : Bear and Raspberry

問題文 http://codeforces.com/contest/385/problem/A 概要 ある品物があり、i 日目には A 一つが金額 で売れる。 くまは始め、一つの品物も持っていないが、金額 c を上乗せして返すことを条件に品物を一つ友人から借りる。くまがとる戦略は、有効な d につ…

Codeforces #226, B : Bear and Strings

問題文 http://codeforces.com/contest/385/problem/B 概要 文字列 s が与えられる。 が文字列 "bear" を含むような ( i, j ) の総数を求めよ。

Codeforces #223, Division 2, A : Sereja and Dima

問題文 http://codeforces.com/contest/381/problem/A 概要 相異なる数が書かれた N 枚のカードを使った、以下のようなゲームをする。 プレイヤーは二人で、交互に動く プレイヤーは各ターン、列のどちらかの端にあるカードを一枚取得できる カードが無くな…

Codeforces #223, Division 2, B : Sereja and Stairs

問題文 http://codeforces.com/contest/381/problem/B 概要 m 個の正整数がある。この正整数から幾つかを選んで並び替え、以下の制約を満たす数列 a を作りたい。 を満たす が存在する そのような列を一つ求め、その長さと内容を出力せよ。

Codeforces #219, Division 1, A ( Division 2, C ) : Counting Kangaroos is Fun

問題文 http://codeforces.com/contest/372/problem/A 概要 n 匹のカンガルーがいて、i 番のカンガルーの大きさは である。二匹のカンガルー i, j について、 であれば、i は j のポケットに入ることができる。ポケットに入ったカンガルーは他のカンガルーを…

Codeforces #215, Division 2, A : Sereja and Coat Rack

問題文 http://codeforces.com/contest/368/problem/A 概要 n 個の洋服掛けがあり、i 番の洋服掛けは金額 で客人に貸し出す。 この日、m 人の客人がくる。 客人は、到着順にその時点で空いている洋服掛けの内で最も安いものを利用する。 洋服掛けに空きが無…

Codeforces #215, Division 2, B : Sereja and Suffixes

問題文 http://codeforces.com/contest/368/problem/B 概要 n 項からなる数列 a がある。 以下の様なクエリ ( l ) を m 個処理せよ。 位置 l 以降に何種類の値があるかを出力する

Codeforces #215, Division 1, A ( Division 2, C ) : Sereja and Algorithm

問題文 http://codeforces.com/contest/367/problem/A 概要 文字列を入力として受け取る、次のようなアルゴリズムがある。 入力文字列の長さ 3 の部分文字列であって、"zyx", "xzy", "yxz" のいずれにも一致しないものを探す。存在しない場合は終了する 1. …

Codeforces #214, C : Dima and Salad

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

Codeforces #213, Division 2, A : Good Number

問題文 http://codeforces.com/contest/365/problem/A 概要 N 個の整数が与えられる。 k 以下の数字を全て含むものの数を求めよ。

Codeforces #213, Division 2, B : The Fibonacci Segment

問題文 http://codeforces.com/contest/365/problem/B 概要 数列 a が与えられる。 この列の連続する部分列であって、次の制約を満たすものの内で最長のものの長さを求めよ 有効な i, i - 1, i - 2 について、

Codeforces #213, Division 1, A ( Division 2, C ) : Matrix

問題文 http://codeforces.com/contest/365/problem/C 概要 数字からなる文字列 s が与えられる。 行列 b の ( i, j ) 要素を とする。 行列 b 内部の長方形領域であって、要素の和が a となるものの数を求めよ。

Codeforces #210, Division 2, A : Levko and Table

問題文 http://codeforces.com/contest/361/problem/A 概要 整数 n, k が与えられる。 n × n の正方行列であって、各行と列の総和が k であるようなものを一つ出力せよ。

Codeforces #210, Division 2, B : Levko and Permutation

問題文 http://codeforces.com/contest/361/problem/B 概要 整数 n, k が与えられる。 1 〜 n の順列であって、 を満たす i の数が k 個であるようなものを一つ出力せよ。 存在しない場合は -1 で示せ。

Codeforces #206, Division 2, A : Vasya and Digital Root

問題文 http://codeforces.com/contest/355/problem/A 概要 関数 S を次のように定める S( n ) = n の各桁の和 整数 n に対し、関数 dr を次のように定める。 dr( n ) = S( n ) ( S( n ) dr( n ) = dr( S( n ) ) ( otherwise )二つの整数 k, d が与えられる…

Codeforces #206, Division 2, B : Vasya and Public Transport

問題文 http://codeforces.com/contest/355/problem/B 概要 二種類の交通機関 A, B があり、それぞれいくつかの車両が走っている。 これらの交通機関で使えるチケットが四種類あり、i 番のチケットの価格は である。 チケットの詳細は次のようになる。 A ま…

Codeforces #206, Division 1, A ( Division 2, C ) : Vasya and Robot

問題文 http://codeforces.com/contest/355/problem/C 概要 横一列に N 個のアイテムが並んでいて、これらをロボットを使って全て集めたい。 ロボットは次の行動ができる。 残っている内で左端のアイテムをコスト l * w で取得する。直前と同じ動作である場…