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" で示せ