Codeforces Beta Round #87 (Div. 1 Only)

Codeforces 参加記録

Result

運良すぎた回。
つってもD,E解けてないんでもっと練習の必要性を感じはする。


490 / 924 / 1140 / (2WA) / -
35位 1873 -> 2013


なんとレッドコーダーに！！嬉しい！！！

A. Party

問題

会社にはn人の人がいて、それぞれ直属の上司が一人あるいは０人居る。それらが与えられる。

今、aがbの上司であるとは、

  • aがbの直属の上司である。
  • あるbの直属の上司cがいて、cの直属の上司がaである。

のいずれかを満たすことを言う。
上司の関係がループすることはない。


会社の人間全員が、いくつかのグループに分かれて参加するパーティを開きたいが、
一つのグループなかに、aがbの上司であるという関係にあるa,bを含まないようにしたい。

そのようなグループの必要な最小の個数を求めよ。

試行錯誤

問題が長くて読むのに少し時間がかかる。
あ、でも今回の英語は読みやすい。


えーと、木の高さ分だけグループが必要で、逆に木の高さあるとき
条件を満たすようなグループ分けはできるよね。


ＯＫ．書いた。送信。pretest passed.

B. Lawnmower

問題

h*wのグリッドが与えられる。各マスは芝生のGまたは雑草のWのいずれかである。
芝刈り機が(0,0)を、右の向きで出発する。
芝刈り機ができる操作は以下の通り。

  • 向いている向きに移動する
  • 一マス下のマスに移動し、（必ず）向きを反転する

芝刈り機はグリッドの外に出ることは出来ない。
全ての芝を刈るのに必要な、芝刈り機の移動回数の最小値を求めよ。

試行錯誤

なんか気合の入った図がｗ
DP？

サイズ的にはDPでいけそうだけど、なんかもう少し単純じゃないか。
えーと、

  • 今の行について、一番端にある芝のとこまでは行かなくちゃいけない
  • 今の行の、一つ下の行についても一番端の芝を刈らなくちゃいけないのでそこまでは行く必要がある
  • 二行下はまた同じ方向に進めるので考える必要はない

あー2行ずつ見てくgreedyでいいっぽい。
途中から芝が全くなくなるケースがコーナーケースかな。
一番下で、あらかじめ芝のない行は取り除いておこう。


書く。サンプル合う。送信。pretest passed.快調。

C. Plumber

問題

四種類のパイプがある。これをh*wのグリッドに条件を満たすように敷き詰める。

  • 四種類のパイプは、┌型、┐型、└型、┘型のいずれか
  • パイプは、グリッドの端を除いて、パイプの両端が別のパイプつながっていなければならない
  • あらかじめ配置するパイプが決まっているマスもあり、それらが与えられる

このとき、条件を満たすパイプの敷き詰め方をmod 10^6+3で求めよ。

試行錯誤

DP？
あ、いやでも制約が相当デカい。n×mが2*10^5以下。
うーんじゃあbitDPとかムリだなあ。なんか上手く状態が減るんだろうか。


前の一行が決まると？
うーんと、一意には定まらない。あ、左端を決めると一意に定まるな。
前の行がどんなふうでも、対応するパイプのつなぎ方はある？あるな。


あ、前の行のパイプが下に接続されるとき、この行のパイプは下にはつながらない。
下へのつながり方は一行ごとに反転する！
左右のつながり方も同じ。


ってことは行ごとに縦のつながり方と横のつながり方をみて、
最後に自由度の累乗だけ2をかけてやればいい！


書けた。なんかサンプルあわない。出力してデバッグ。
サンプル合った。デバッグ出力も正しそう。
送信。pretest passed.

D. Unambiguous Arithmetic Expression

問題

Unambiguous Arithmetic Expression(UAE)とは以下の条件を満たす式である。

  • 数字。leading zeroはOK
  • X,YをUAEとして、(X)+(Y), (X)-(Y), (X)*(Y),(X)/(Y)
  • XをUAEとして+(X), -(X)

括弧を含まない式が与えられるので、
UAEとして括弧を付ける付け方は何通りあるか、mod 10^6+3で求めよ。

試行錯誤

長さは……2000以下。
え、普通に構文解析するとO(n^3)かかって間に合わない。


何かいい方法あるんだろうか。
単項演算子の+と-がなかったら多分凄く簡単な式になる。
なので単項演算子を上手くちょいちょいやればDPとかに……なんのか？


ならなそうなのでEを読む。
Eから戻ってきて、とりあえずO(n^3)を書いて出してみる。


サンプル合った。
あれ、TLEどころかWAった。

E. Linear Kingdom Races

問題

n本の、一直線に並んだ道路がある。それぞれの道路は初期状態では全て壊れている。
それぞれの道路を補修するのには、道路ごとに定められたコストがかかる。

m個のレースがある。
それぞれのレースは、区間l[i]からr[i]の全ての道路を使用する。利益はp[i]である。


どのレースを開催するか自由に選ぶことができるとき、利益（レースの利益引く道路の補修費用）の最大値を求めよ。
レースを全く開催しなくともよい。

試行錯誤

うーん……特殊なデータ構造を使うDP？
あるいはなんか費用流みたいなフローっぽい感じなんだろうか。


少し考えたけどよくわからないのでDへ戻る。

System Test

提出したAからCは全部通った。