2012-02-01から1ヶ月間の記事一覧
問題 アルファベットがm種類ある言語の上で、 n文字からなり、その連続する部分文字列の長さがkのものはどれも回文になっているような文字列はいくつあるか、mod 10^9+7で求めよ。 制約条件 n,m,k≦2000
問題 ある整数に対して、二人が次のようなゲームを行う。 一人が、その数の自明でない約数を言う。(1とその数自身以外の約数) もう一人が、前の人が言った数の自明でない約数を言う。 これを、約数が言えなくなるまで続ける。 約数を言えなくなった人の勝…
問題 n人の人の電話帳のデータが与えられる。 電話番号のうち、 全ての桁が同じ数字のものはタクシーの番号であり、 全ての桁が降順に並んでいるものは、ピザ屋の番号であり、 その他の番号は全てガールフレンドの番号である。 タクシーの番号、ピザ屋の番号…
問題 k本のボトルがあり、それぞれlリットルの飲料が入っている。 c個のライムがあり、それぞれをd枚にスライスする。 pグラムの塩がある。 トースト一枚につき、nlリットルの飲料、 1枚のライムのスライス、npグラムの塩が必要である。 n人が、平等にトース…
ソースコード #include<iostream> #include<sstream> #include<algorithm> #include<map> #include<set> #include<queue> #include<complex> #include<cstdio> #include<cstdlib> #include<cstring> using namespace std; #define rep(i,n) for(int i=0;i<(int)n;i++) #define all(c) (c).begin(),(c).end() #define pb emplace_b…</cstring></cstdlib></cstdio></complex></queue></set></map></algorithm></sstream></iostream>
C++0xの新機能タプル型ですが、 operator tupleの要素数は可変長で、なおかつその長さを調べる方法がないため、 (調べたところ見つからなかっただけです。ご存知の方いらっしゃったら教えてください) デバッグなどで中身を全て確認したいときにいちいち、 …
問題 (xa,ya),(xb,yb)を角とするような、 座標軸に平行なテーブルがある。 このテーブルの辺のうち、座標が整数の点には人がいる。 ストーブがn個あり、それぞれの座標は(x[i],y[i])であり、 ストーブの有効範囲はr[i]である。 どのストーブの有効範囲にもい…
問題 与えられた数字を $をつけて、3桁ごとにカンマで区切り、小数点2桁未満を切り捨てて表示せよ。 数字が負の場合は、さらにその文字列を()でかこって表示せよ。 制約条件 与えられる数字の桁数≦50
問題 4つの□に、1〜9の相違なる整数を入れる。 □□ □□ 入れた後の数字の、各列の和、各行の和、対角線の和が与えられる。 このとき、数字の入れ方として正しいものをどれか1通り出力せよ。 正しい入れ方が存在しないときは-1を出力せよ。 制約条件 c1,c2,r1,r…
問題 ある数のLucky maskとは、その数から4または7の数字だけを取り出して、 元の順のまま並べて一つの数字にしたものである。 72174994のmaskは7744で、7のmaskは7, 9999047のmaskは47である。 与えられた数4または7のみからなる数bに対して、 aより大きい…
問題 n桁の数字が書かれたチケットがある。 このチケットがLuckyであるとは、 各桁の数字が4または7 前半のn/2文字と後半のn/2文字の数字の和が等しい ことを言う。与えられたチケットがLukcyであるかそうでないかを判定せよ。 制約条件 n≦50
問題 対応の取れた括弧からなる文字列が与えられる。 この文字列のそれぞれの文字について、 色を塗らない 赤色に塗る 青色に塗る のどれかをする。 対応する括弧は、どちらか一方のみが色を塗られていて、、 かつ、隣り合うどの文字も同じ色に塗られていな…
問題 n人の人がいて、それぞれのスキルはa[i]である。 全員をちょうど二つのチームに振り分けたい。 チーム分けは、 人数の差が1以下 チームの全員のスキルの和の差が、最も高いスキルを持つ人のスキル以下 という条件を満たすように行う。 正しいチームわけ…
問題 時刻がa:bの形で与えられる。 aは0以上23以下の整数で、bは0以上59以下の整数であるが、 何進数で書かれているかはわからない。 何進数で書かれているか、ありえる基数(2以上の整数)を全て、小さい順に出力せよ。 無限に多くの基数で可能な場合は-1を…
問題 12ヶ月の間花に水をやる。 それぞれの月で水をやった場合、花はa[i]cmだけ成長する。 水をやらなかった月は成長しない。 全体でkcm以上成長させたい。 最低でいくつの月水をやらなければならないか、求めよ。 kcm成長させるのが不可能な場合は-1を出力…
Result 494 / 750(1 Hacked) / 1230 / 2130(1 Resubmit) / - 0 hack 4594点 20位(レート変動なし)
問題 NxMのグリッドがある。 それぞれのマスについて、色を塗るか塗らないか選ぶ。 色を全て塗り終えた後で、 色が塗られているマスに(上下左右に)隣接する色の塗られているマスの数はすべて偶数である ような色の塗り方は何通りあるか、求めよ。 制約条件…
問題 N個の町があり、1番からN番の番号がついている。 そこに双方向に通行可能な道路M本を引く。 道路は、異なる町A,Bについて|A-B|≦Kのときに引くことができる。 また、全ての道路を引き終えた後で、全ての町から出ている道路の数は偶数でなくてはならない…
問題 3つの輪がつながったものがいくつかある。 それぞれの輪は、綺麗であるか、汚れているかであり、 綺麗な輪には美しさが定められている。 輪がつながったものを好きな順に一列につなげる。 そこから「綺麗な輪が連続する部分」を切り出す。 切り出したも…
Result 252.86 / Opened / Unopened 0チャレンジ 147位 1960 -> 1995 前回大敗北したので酷い順位なのにレート上昇した…… Easy DengklekMakingChains 問題 3つの輪がつながったものがいくつかある。 それぞれの輪は、綺麗であるか、汚れているかであり、 綺…
問題 n個の棚がある。棚から合計m個の品を取りたい。 それぞれの棚は、先頭または末尾からしか品物を取り出すことは出来ない。 それぞれの棚の品物の価値が与えられたとき、 取り出せる価値の合計の最大値はいくつか、求めよ。 制約条件 n≦100, m≦10000 それ…
問題 n人がいて、それぞれの人は1以上50000以下の整数のお金を持っている。 n人を先頭から見ていったとき、 「直前の人よりもお金を多く持っている人」がa人 「今までの人の持っているお金の合計よりも多くお金を持っている人」がb人いた。 (ただし、後者に…
問題 hxwのグリッドで表される迷路がある。 '.'および'^'のマスは何もないマスで、'#'のマスは壁である。 この迷路の'^'のマスのどこかにモンスターを置く。 モンスターは迷路を上下左右の何もないマスに動くことができる。 迷路の外へモンスターが脱出でき…
問題 n個の都市からなる国があり、それぞれの都市はいくつかの双方向に通行可能な道路で結ばれている。 kingdom[i][j]が'1'のときiとjは道路で結ばれている。 いま道路を好きなだけつなぐまたは壊して、 任意の二つの都市間にパスが一つだけ存在するようにし…
問題 1〜n番までのn種類のモンスターがいる。 最初は1番のモンスターが1匹いる。 一日たつと、i番目のモンスターは、それぞれ与えられたモンスター(一匹以上)へと変化する。 最終的にモンスターは何匹になるか、 モンスターが無限に増える場合は-1を、そう…
問題 N曲の曲からP曲を重複を許して、以下の条件を満たすよう選ぶ。 選び方は何通りあるか、mod 10^9 + 7で求めよ。 条件: 全ての曲が少なくとも一度以上選ばれる。 同じ曲は間に少なくともM曲のほかの曲を挟む。 制約条件 N,M,P≦100
大敗北。 Result Challenged / Opened / Unopened 398位 2097 -> 1960
問題 n個のステージがあるゲームをする。 最初ステージ0からスタートして、n-1にたどり着いたらクリアである。 ステージiをクリアした後ステージjに移動できるかどうかの関係がグラフにより与えられる。 ゲームクリアを、「今までのクリアで一回も使われてい…
問題 nxmのグリッドであらわされるケーキがある。 このケーキを、hxlのグリッドであらわされるカッターで切る。 カッターはケーキのグリッドに合うように使い、カッターはケーキの外にはみ出てはならない。 更に、カッターの'.'のマスにはケーキがなくてはな…
問題 n個のビンがあり、それぞれにS[i]個のボールが入っている。 ボールを別のビンに移す操作を繰り返して、 それぞれのビンに入っているボールの個数T[i]が、 T[i]はS[i]を並べ替えたものであり、T[i]がソート済みの列になるようにする。 T[i]が与えられた…