Ulm Local 2007

練習会 PKU

いい感じの難易度だった

3633 - Annoying painting tool

問題

n*mの矩形領域に0か1が割り当てられている。
r*cの矩形領域内の0,1が反転する操作が出来る。
このときr*cがn*mからはみ出してはいけない。
目標の盤面が与えられるので、そこに辿り着く最小操作回数を求めよ。
初期盤面は全て0である。
また、無理なら-1を出力せよ。

制約

1 ≤ r ≤ n ≤ 100, 1 ≤ c ≤ m ≤ 100

解法

目標状態から全て0にするための最小操作回数を考えればよい。
n*m領域を左上から順に見ていき、そこが1なら、そこを左上とするr*c領域を反転させる。
最後まで行って全部0になってなかったら無理。
全部0になってたらそのときの反転回数が答え。

3364 - Black and white painting

問題

n*mのチェス盤のように白黒で塗り分けられたボードを考える。
右下はcが0なら黒、cが1なら白である。
このとき、8*8のチェス盤となっている所は何箇所あるか。
チェス盤は右下が白である。

制約

8 ≤ n, m ≤ 40000

解法

8*8領域を取ってくる取り方は(n-7)*(m-7)である。
この中で右下が白になっているものは1/2っぽい。
ただし、(n-7)*(m-7)が奇数のときは右下が白なら+1する必要がある。
答えは
((n-7)*(m-7)+c)/2
で出る。

3365 - Cylinder

問題

w*hの紙から円柱を作る。
紙を２つの部分に切り、１つ目から出来るだけ大きな円を切り、２つ目を（１つ目の円に合うように）輪にして円柱の側面とする。
このように作るときの最大の体積を求めよ。

制約

1 ≤ w ≤ h ≤ 100

解法

２つ目の部分を縦に丸めるか横に丸めるかで２つ試して最大の方を選ぶ。
円柱の半径をrとすると、この問題では体積は単調増加になる。
rに関する制約があるので、その中での最大を用いて体積を計算する。

3366 - Deli Deli

問題

N個の文字列が与えられるので、複数形にせよ。
ただし、文字列とその複数形が別にL個与えられる。
そこで与えられているものに関しては、それに沿って出力する。

制約

0 ≤ L ≤ 20, 1 ≤ N ≤ 100

解法

与えられている対応はmapでやればよい。
あとの複数形の作り方は問題分で与えられているのそのとおりにやる。

3367 - Expressions

問題

逆ポーランド記法で与えられている式を、それと同じ結果になる別の式にする。
逆ポーランド記法ではスタックに入れて計算するが、この問題で求めれられる式の表現方法は、キューに入れて計算する。
すなわち、式を左から見て、数字ならエンキューし、演算子ならキューから２つデキューし演算子を作用させた結果をエンキューする。
最後にキューに残ったのが式の値。
数字は小文字、演算子は大文字のアルファベット１文字で表現される。

制約

テストケース ≤ 200
式は最大10000文字

解法

与えられた式を木構造に直し、その木を幅優先で処理して逆順で出力すれば良い。
入出力が多いのでcin,coutを使うと死ぬ。

3368 - Frequent values

問題

要素n個の広義単調増加の数列aが与えられる。
その後q個のクエリを処理する。
各クエリでは区間を指定されるので、その区間で最も多く現れている数字の個数を出力する。

制約

1 ≤ n, q ≤ 100000

  • 100000 ≤ ai ≤ 100000
解法

数列aで同じ数が連続する長さを入れた数列bを考える。
例えばサンプルなら
b = {2,4,1,3}
になる。
以下の２つのテーブルを作る。

  1. aの各要素がbのどの要素に対応しているかを表すテーブル
  2. aの各要素でその要素の値が始まった場所を格納したテーブル

基本的にはテーブル１とSegTreeを使って、与えられた区間に完全に含まれる部分のbの最大値を求める。
これだけだと区間の端がまずいので、テーブル２を用いて端も考慮に入れる。

3369 - Grocery store

問題
  • a+b+c+d = a*b*c*d
  • a,b,c,dは0.01の整数倍。
  • a+b+c+d <= 20.00

を満たすa,b,c,dを全て出力せよ。
a,b,c,dは昇順で出力する。
出力の順番は任意でよいが、重複があってはいけない。

解法

小数は面倒なので、全部100倍したものを考える。すると条件は、
(a+b+c+d)/100 = a*b*c*d/100^4
(a+b+c+d)*100^3 = a*b*c*d
となる。
a,b,cを決めればdは決まるので、全部ループを回せばO(2000^3)。
そんなに長くかからず終わるので埋め込みでもいい。


埋め込みをしない場合、工夫したループをすることになるが、自分のアイディアを以下に示す。

  • a*b*c*dは100^3(=2^6*5^6)の倍数
  • 因数2を6個、因数5を6個a,b,c,dに分配する方法を全部試す
  • a,b,c,dはそれぞれ、分配された因数を掛け合わしたものの倍数にしかならないのでループがかなり制限されて間にあう

しかしもっと簡単な方法ありそう…

3370 - Halloween treats

問題

長さnの数列aの部分集合で、和がcの倍数になるものを１つ求めよ。

制約

1 ≤ c ≤ n ≤ 100000
1 ≤ ai ≤ 100000

解法

cの倍数になるものを探すのは、和がmod cで0になるものを探せば良い。
mod cでのa0+..+aiをsum[i]とすれば、
nがc以上なので鳩の巣原理より、必ずsum[i]=sum[j](i!=j)となるi,jがある。
このとき、ai+..+aj=0(mod c)なので、
i ... j と出力すれば良い。
ちなみにsum[i]=sum[j](i!=j)を見つけるのはテーブルを使えばO(n)で出来る。
時間制限がきついのでかなり神経質にならないとＴＬＥになる。