実行時間制限: 2 sec / メモリ制限: 256 MB
問題文
ニコニコ動画には、プレミアム会員という制度があります。このプレミアム会員制度には月額一定の額を支払うことで加入できます。
ニワンゴくんは、この n ヶ月間連続してプレミアム会員です。 また、x ヶ月前に月の一定支払い額が 525 円から 540 円に変わったことを知っています。 つまり、この n ヶ月のうち最近の x ヶ月間は月額 540 円支払っていて、それ以外の月では 525 円払っていたことが分かっています。
n と x が与えられるので、この n ヶ月間でニワンゴくんがプレミアム会員制度に支払った合計額を出力してください。
入力
入力は以下の形式で標準入力から与えられる。
n x
- 1 行目には、プレミアム会員への加入月数を表す整数 n (1≦n≦100) が与えられる。
- 2 行目には、月の一定支払い額が変更された後のプレミアム会員への加入月数を表す整数 x (1≦x≦n) が与えられる。
出力
1 行目には、ニワンゴくんがプレミアム会員制度に支払った合計額を出力せよ。
行末の改行を忘れると不正解と判定されるので注意すること。
入力例1
5 2
出力例1
2655
5 ヶ月のうち 2 ヶ月間 540 円を払っていたことが分かっています。残りの 3 ヶ月間は 525 円を払っていたため、支払った合計額は 540×2+525×3=2655 です。
入力例2
25 25
出力例2
13500
入力例3
100 1
出力例3
52515
入力例4
1 1
出力例4
540
実行時間制限: 2 sec / メモリ制限: 256 MB
問題文
0 から 9 の数字から成る文字列 S が与えられます。
ある文字列 X について、X="25" または X="2525" または X="252525" …… というふうに "25" を何回か繰り返した文字列になっているとき、X はニコニコ文字列であるといいます。 たとえば "25" や "25252525" はニコニコ文字列ですが、"123" や "225" はニコニコ文字列ではありません。
あなたの仕事は、文字列 S について、ニコニコ文字列となるような連続した部分文字列の取り出し方が何通りあるかを答えることです。 文字列として同じであっても、取り出し位置が異なっていれば別々に数えます。
入力
入力は以下の形式で標準入力から与えられる。
S
- 1 行目には、文字列 S が与えられる。Sの長さは 1 以上 100,000 以下である。また、S の各文字は 0 から 9 の数字のみから成る。
部分点
この問題には部分点が設定されています。
N≦2000 を満たすデータセット 1 にすべて正解すると、30 点が得られます。 追加制約のないデータセット 2 にすべて正解すると、上記のデータセットに加えてさらに 70 点が得られ、全体で 100 点が得られます。
出力
1 行目には、文字列 S からニコニコ文字列となるような連続した部分文字列を取り出す方法が何通りあるかを出力せよ。
行末の改行を忘れると不正解と判定されるので注意すること。
入力例1
2525
出力例1
3
S="2525"のケースです。部分文字列が "25" となる取り出し方が 2 通り、"2525" となる取り出し方が 1 通りあるので合計 3 通りを出力します。
入力例2
1251251252525
出力例2
8
入力例3
25225
出力例3
2
入力例4
252252252252252252
出力例4
6
入力例5
20061212
出力例5
0
実行時間制限: 2 sec / メモリ制限: 256 MB
問題文
ドワンゴ社内には、ポーカー部、軽音同好会、料理研究会といった様々な同好会があり、ニコニコ動画を支える社員たちは仕事の合間に部活動を楽しんでいます。
ボードゲーム部も、社内に数多くある同好会の一つです。ボードゲーム部で遊ばれる多くのゲームはターン制のものですが、よくある悩みは、最初のプレイヤーをどうやって決めるかというものです。典型的にはじゃんけんで最後まで勝ち残った人を決めますが、この方法では参加者が多くなるとあいこになりやすく、効率的ではありません。
こんなときボードゲーム部では、ボードゲーム好きの間で古くから伝わる「ゲーマーじゃんけん」と呼ばれる変種のじゃんけんを行います。そのルールは以下のようなものです。
ルール
「ラウンド」と呼ばれる勝負を繰り返し、 1 人の勝者を決めます。
最初のラウンドには、全てのプレイヤーが参加します。ラウンドの勝者が複数人いた場合、勝者のみでラウンドを行うことを繰り返します。ラウンドの勝者が 1 人だけだった場合、そのラウンドの勝者がこのじゃんけんの勝者になります。
ラウンド
ラウンドに参加するプレイヤーは、グー・チョキ・パーの手を選んで出す。
- 出された手が 1 種類の場合
- あいこである。全てのプレイヤーは勝者となる。
- 出された手が 2 種類以上の場合
- 出したプレイヤーの数が最も少ない手に注目する。
- そのような手が 1 種類あった場合
- その手を出したプレイヤーのみ勝者となる。
- そのような手が 2 種類あった場合
- その 2 種類の手の強弱 (*1) を判定し、強い手を出したプレイヤーのみが勝者となる。残る 1 種類の手を出したプレイヤーも敗退する。
- そのような手が 3 種類あった場合
- あいこである。全てのプレイヤーは勝者となる。
- そのような手が 1 種類あった場合
- 出したプレイヤーの数が最も少ない手に注目する。
補足
- (*1) グーはチョキに勝ち、チョキはパーに勝ち、パーはグーに勝ちます。
ラウンドの具体例
- 全員がパーを出した場合
- 全員がこのラウンドの勝者となります。
- 5 人の参加者がそれぞれグー、チョキ、チョキ、パー、パーを出した場合
- 出した人数が最も少ない手であるグーを出したプレイヤーが勝者となります。
- 7 人の参加者がそれぞれグー、グー、チョキ、チョキ、チョキ、パー、パーを出した場合
- 出した人数が最も少ないのはグーとパーです。グーとパーではパーの方が強いので、パーを出した 2 人のみが勝者となります。
- 3 人の参加者がそれぞれグー、チョキ、パーを出した場合
- 全員がこのラウンドの勝者となります。
このゲーマーじゃんけんでは、人数が多くても効率的に 1 人の勝者を決めることができます。N 人のプレイヤーがゲーマーじゃんけんを行ったとき、最後に 1 人の勝者が決まるまでに行われるラウンドの回数の期待値を計算してください。ただし、全てのプレイヤーはグー・チョキ・パーを同じ確率で出すものとします。
入力
入力は以下の形式で標準入力から与えられる。
N
- 1 行目には、プレイヤーの数を表す整数 N (2 ≦ N ≦ 100) が与えられる。
出力
1 行目には、ラウンドの回数の期待値を表す実数を出力せよ。小数点以下何桁でも出力してよいが、10-6 を超える絶対誤差を含んではならない。
入力例1
3
出力例1
1.5
実行時間制限: 2 sec / メモリ制限: 256 MB
問題文
ある星で、プログラミングコンテスト「ドワンゴからの挑戦状」の予選が行われ、予選通過者を本選会場へと招待することになりました。
この星には長さ L の環状線 1 本があり、環状線上に N 個の都市があります。都市には 1 から N までの番号が、都市 1 を基準として時計回りに昇順に付けられています。
本選は 1 つ以上の都市で行われ、各会場ごとに生放送をすることになりました。
各都市と各会場ごとに、その都市に住んでいる本選出場者数と会場に入る本選出場者数は決まっています。
会場に入る本選出場者数の合計は本選出場者数の合計とぴったり一致しています。
都市によっては、その都市に住んでいる本選出場者数と会場に入る本選出場者数が一致していないこともあり、その場合は都市間で本選出場者をタクシーで移動させる必要があります。
タクシーは環状線上を移動し、本選出場者 1 人ごとに移動距離に等しいコストが掛かります。
移動にかかるコストの合計値として考えられる最小値を求めるプログラムを作成してください。
入力
入力は以下の形式で標準入力から与えられる。
N L a_1 b_1 c_1 a_2 b_2 c_2 : a_N b_N c_N
- 1 行目には、都市の個数 N (2 ≦ N ≦ 100,000) と環状線の長さ L (N ≦ L ≦ 10,000,000) が空白区切りで与えられる。
- 2 行目から N 行には、各都市に関する情報が与えられる。このうち i (1 ≦ i ≦ N) 行目には 3 つの整数 a_i (0 ≦ a_i ≦ L - 1), b_i (0 ≦ b_i ≦ 100,000), c_i (0 ≦ c_i ≦ 100,000) が空白区切りで与えられる。これは、都市 i が環状線上を都市 1 を基準として時計回りに a_i だけ進んだところにあり、都市 i から出る本選出場者数が b_i 人で、c_i = 0 なら都市 i には会場はなく、c_i ＞ 0 なら都市 i には本選出場者を c_i 人招待することを表す。
- a_1 = 0 であり、すべての整数 i (2 ≦ i ≦ N) に対して a_i ＞ a_{i-1} が成り立つ。
- b_1 + ... + b_N = c_1 + ... + c_N である。
- b_1 + ... + b_N ≧ 1 である。
部分点
この問題には部分点が設定されています。
- N ≦ 5,000 および b_1 + ... + b_N ≦ 5,000 を満たすデータセット 1 にすべて正解すると、15 点が得られます。
- N ≦ 5,000 を満たすデータセット 2 にすべて正解すると、上記に加えてさらに 30 点が得られます。
- 追加制約のないデータセット 3 にすべて正解すると、上記に 2 つに加えてさらに 55 点が得られ、全体で 100 点が得られます。
出力
移動コストの合計値として考えられる最小値を 1 行に出力せよ。出力の末尾にも改行を入れること。
入力例1
7 30 0 3 6 1 2 2 4 5 4 19 0 1 20 4 4 21 1 0 27 3 1
出力例1
12
以下のような移動を考えます。
- 都市 3 の本選出場者 1 人が都市 1 にタクシーで反時計回りに移動する。移動コストは 4 × 1 = 4 である。
- 都市 6 の本選出場者 1 人が都市 4 にタクシーで反時計回りに移動する。移動コストは 2 × 1 = 2 である。
- 都市 7 の本選出場者 2 人が都市 1 にタクシーで時計回りに移動する。移動コストは 2 人あわせて 3 × 2 = 6 である。
この移動の結果、移動後のどの都市についても、会場があるならその会場に入る人数とその都市にいる本選出場者数が等しく、かつどの本選出場者も会場に入れます。
移動コストの合計値は 4 + 2 + 6 = 12 で、この値が最小値となります。
入力例2
6 25 0 10 1 3 0 1 9 0 2 12 0 3 13 0 2 21 0 1
出力例2
85
実行時間制限: 2 sec / メモリ制限: 256 MB
問題文
ある星には正三角形の形状をした街があり、この街は N × (N + 1) / 2 個の家が正三角形状に並んでいます。この正三角形は、ある辺が東西方向に平行で、その辺を構成しない頂点が最も北にある家となるような形状をしています。
各家は 2 つの整数を用いて番号が付けられています。最も北にある家を (1,1) とし、北の端から i 行目の西から j (1 ≦ j ≦ i ≦ N) 番目の家には (i,j) という番号が付けられています。
以下に N = 5 の例を示します。
| (1, | 1) | ||||||||
| (2, | 1) | (2, | 2) | ||||||
| (3, | 1) | (3, | 2) | (3, | 3) | ||||
| (4, | 1) | (4, | 2) | (4, | 3) | (4, | 4) | ||
| (5, | 1) | (5, | 2) | (5, | 3) | (5, | 4) | (5, | 5) |
dwango 社は M 個の電波局 (1 から M まで番号が付けられているとします) を持っており、それぞれの電波局はある正三角形状の範囲 (各辺は街の外周部の辺と平行である) にデジタルコンテンツを配信しています。
電波局 i (1 ≦ i ≦ M) には 3 つの整数 a_i,b_i,c_i が定められており、1 ≦ k ≦ j ≦ c_i を満たすすべての整数 j,k に対して、家 (a_i+j-1,b_i+k-1) に配信しています。
dwango 社は新たに 1 つ電波局を設置して、新たな顧客を呼び込もうと考えています。
電波局の設置の方法は Q 通り発案されています。各設置方法に対して新たに獲得できる顧客の人数を求めるプログラムを作成してください。
入力
入力は以下の形式で標準入力から与えられる。
N M a_1 b_1 c_1 a_2 b_2 c_2 : a_M b_M c_M Q d_1 e_1 f_1 d_2 e_2 f_2 : d_Q e_Q f_Q
- 1 行目には、2 つの整数 N (1 ≦ N ≦ 1,000,000,000),M (1 ≦ M ≦ 1,000) が空白区切りで与えられる。
- 2 行目から M 行には、既に設置されている電波局に関する情報が与えられる。M 行のうち i (1 ≦ i ≦ M) 行目には電波局 i が配信する範囲を表す 3 つの整数 a_i,b_i (1 ≦ b_i ≦ a_i ≦ N),c_i (1 ≦ c_i ≦ N-a_i+1) が与えられる。これは電波局 i が、1 ≦ k ≦ j ≦ c_i を満たすすべての整数 j,k に対して、家 (a_i+j-1,b_i+k-1) に配信していることを表す。
- M + 2 行目には、整数 Q (1 ≦ Q ≦ 1,000) が与えられる。
- M + 3 行目から Q 行には、新たな設置方法に関する情報が与えられる。Q 行のうち i (1 ≦ i ≦ Q) 行目には、i 番目の設置方法において新たに設置する電波局が配信する範囲を表す 3 つの整数 d_i,e_i (1 ≦ e_i ≦ d_i ≦ N),f_i (1 ≦ f_i ≦ N-d_i+1) が与えられる。これは新たに設置する電波局が、1 ≦ k ≦ j ≦ f_i を満たすすべての整数 j,k に対して、家 (d_i+j-1,e_i+k-1) に配信予定であることを表す。
部分点
この問題には部分点が設定されています。
- N ≦ 200 および M ≦ 200 および Q ≦ 200 を満たすデータセット 1 にすべて正解すると、10 点が得られます。
- M ≦ 200 および Q ≦ 200 を満たすデータセット 2 にすべて正解すると、上記に加えてさらに 30 点が得られます。
- 追加制約のないデータセット 3 にすべて正解すると、上記に 2 つに加えてさらに 60 点が得られ、全体で 100 点が得られます。
出力
出力は Q 行からなる。Q 行のうち i (1 ≦ i ≦ Q) 行目には、i 番目の設置方法において新たに配信される家の個数を出力せよ。
入力例1
8 3 2 2 4 5 4 3 6 1 3 2 4 1 4 7 6 2
出力例1
5 2
既に設置されている 3 つの電波局によって配信されている家の範囲は、下図のようになっています (○は配信されていることを、×は配信されいないことを表します)。
| × | ||||||||||||||
| × | ○ | |||||||||||||
| × | ○ | ○ | ||||||||||||
| × | ○ | ○ | ○ | |||||||||||
| × | ○ | ○ | ○ | ○ | ||||||||||
| ○ | × | × | ○ | ○ | × | |||||||||
| ○ | ○ | × | ○ | ○ | ○ | × | ||||||||
| ○ | ○ | ○ | × | × | × | × | × |
1 つ目の設置方法の場合、新たに配信される家は下図の+で示す 5 個です。
| × | ||||||||||||||
| × | ○ | |||||||||||||
| × | ○ | ○ | ||||||||||||
| + | ○ | ○ | ○ | |||||||||||
| + | ○ | ○ | ○ | ○ | ||||||||||
| ○ | + | + | ○ | ○ | × | |||||||||
| ○ | ○ | + | ○ | ○ | ○ | × | ||||||||
| ○ | ○ | ○ | × | × | × | × | × |
2 つ目の設置方法の場合、新たに配信される家は下図の+で示す 2 個です。
| × | ||||||||||||||
| × | ○ | |||||||||||||
| × | ○ | ○ | ||||||||||||
| × | ○ | ○ | ○ | |||||||||||
| × | ○ | ○ | ○ | ○ | ||||||||||
| ○ | × | × | ○ | ○ | × | |||||||||
| ○ | ○ | × | ○ | ○ | ○ | × | ||||||||
| ○ | ○ | ○ | × | × | + | + | × |
入力例2
3 2 1 1 2 3 2 1 3 2 1 2 2 2 1 1 1 3
出力例2
1 0 2