Codeforces Round 106 (Div2 only)

Codeforces 参加記録

Result

494 / 750(1 Hacked) / 1230 / 2130(1 Resubmit) / -
0 hack
4594点 20位（レート変動なし）

A. Business trip

とりあえずAから見て行って、ゆっくり4完くらいを目標にする。
最近Div2Eが難しいことが結構多いので。

問題

12ヶ月の間花に水をやる。
それぞれの月で水をやった場合、花はa[i]cmだけ成長する。
水をやらなかった月は成長しない。


全体でkcm以上成長させたい。
最低でいくつの月水をやらなければならないか、求めよ。
kcm成長させるのが不可能な場合は-1を出力せよ。

制約条件

a[i]≦100
k≦100

試行錯誤

ソートして貪欲に使えばいい。
できた。送信。Pretest passed.

B. Martian Clock

問題

時刻がa:bの形で与えられる。
aは0以上23以下の整数で、bは0以上59以下の整数であるが、
何進数で書かれているかはわからない。


何進数で書かれているか、ありえる基数を全て出力せよ。
無限に多くの基数で可能な場合は-1を出力、
可能な基数が無い場合は0を出力せよ。

制約条件

a,bは5文字以下
a,bは0-9またはA-Zからなる文字列

試行錯誤

たぶん60進法とみても59進法と見ても変わらなかったら、61進法以上でも変わらないので、
一つでも有効な基数があれば-1になる？


基数を1から順に試していけばいいのでは。
最後のサンプルが合わない。
a,bが2文字ずつとは限らなかった。


直した。
合ってる気がする。送信。

C. Division into Teams

問題

n人の人がいて、それぞれのスキルはa[i]である。
全員をちょうど二つのチームに振り分けたい。


チーム分けは、

  • 人数の差が1以下
  • チームの全員のスキルの和の差が、最も高いスキルを持つ人のスキル以下

という条件を満たすように行う。


正しいチームわけをどれか一通り出力せよ。
必ずそのようなチームわけがあることは保証されている。

制約条件

n≦10^5
1≦a[i]≦10^5

試行錯誤

解を構成しろ系。
いつも苦手な（時間かかる）ので先にDを読んでみるかな。

D. Coloring Brackets

問題

対応の取れた括弧からなる文字列が与えられる。
この文字列のそれぞれの文字について、

  • 色を塗らない
  • 赤色に塗る
  • 青色に塗る

のどれかをする。


対応する括弧は、どちらか一方のみが色を塗られていて、、
かつ、隣り合うどの文字も同じ色に塗られていないような色の塗り方は何通りあるか、
mod 10^9+7で求めよ。

制約条件

文字列の長さ≦700

試行錯誤

なんかDPっぽい？
とりあえずサンプルを見る。なるほど。


部分文字列と、その両端で禁止される色が決まれば、
その部分文字列に対する場合の数が求まる。
なので、
dp[l][r][左側で禁止される色][右側で禁止される色]
みたいなDPをすればいい気がする。


えーと、括弧の対応がどこかを前計算しとく必要があるかな？
これはstackを適当に使ってやればいい気がする。


書けた。
サンプル合わない。
あ、どちらか一方のみに色が塗られるという条件を忘れてた。
つけたす。サンプル通った。
合ってる気がするので送信。Pretest passed.


ああああああああmod取り忘れてる。
再送信orz

C（再）

Bがハックされたといかいうお知らせが。
とりあえずCを解いてからにする。


2チーム適当につくった後、
Aチームの強さ＞Bチームの強さだったら、
Aチームの一番強い人とBチームの一番弱い人を入れ替えたら？


入れ替えたら、A-Bの変動は2*max以下。2*max以下なので、
入れ替えた後で両チームの強さが入れ替わって、BがA+maxより強くなることはない。
なおかつA-Bは必ず減る。


なので、一番強い人を適当に入れ替え続ければいい。
えーと、setを使って強い人と弱い人をO(log n)で取り出せるようにすれば、
全体の計算量もO(nlog n)で間に合う。


おｋ,書いた。
サンプル合った。送信。Pretest passed.

B（再）

基数は2以上とすると書いてある。
これ見落としてたかも。
2以上にする。送信。Failed.


あれー。
あ、オーバーフローしてる？
送信。Failed
あれー。


あ、60進法まで見ないとダメかなこれ。
10とかは59進法までおｋじゃん。
35進法までしか見てなかった。
直して送信。Pretest passed.


komakiに点数抜かれた。ちくしょー。

E. Martian Strings

問題

文字列sが与えられる。
m個の文字列が与えられる。
この中で、sに「分かれて出現する」ものはいくつあるか、求めよ。


ただし「分かれて出現する」とは、
4つの整数a≦b＜c≦dについて、
sのa番目からb番目までを抜き出した文字列と、c番目からd番目までを抜き出した文字列を結合させた文字列が、その文字列になっているという意味である。

制約条件

sの長さ≦10^5
m≦100
m個の文字列の長さはそれぞれ1000以下

試行錯誤

suffix arrayを作って出現位置をO(log n)で探索して、
segtreeを適当に作ってうんぬん……とか？
いやでもnが10^5あって、mが100個あって、mのそれぞれが1000文字だと時間間に合わないよなあ。


どうするんだろ。
よくわからんし眠いので寝る。

System Test

全部通ってたらしい。