AtCoder Grand Contest 016

参加しました


A問題 Shrinking

長さNの文字列tを長さN-1の文字列t'に変える操作を考える。

t'[i]はt[i]かt[i+1]を選ぶ。

このとき、全部が同じ文字に成るようにする最低回数を求めよ。

 

最初の文字列のi番目の文字のみになるような時の最低回数は貪欲的にできるので、全部の文字についてやりました。

 

B問題 Colorful Hats

1~N匹の猫が色のついた帽子をかぶっている。

i匹目の猫から見ると他のN-1匹はa_i種類の色の帽子をかぶっているとする。

{a_i}が与えられた時そういうパターンは存在するかという問題。

 

とりあえず考察。

(1) a_iで出てきていい数字は2種類まで(3種類以上あると無理)

(2) 2匹が同じ帽子をかぶっていると必ずその色はすべての猫から見える

(3)a_iで出てくる数字がk,k+1のときkの方の猫は全て別の色の帽子をかぶっている

 

以上で無理な場合を弾いていけば解けました。

 

C問題 +/- Recrangle

H*Wの行列が以下を満たすようなものを構成しろ(無理ならNo)

・行列の全要素の和は正

・h*wの部分長方形を取り出しても要素の総和は負

 

貪欲にh行w列ごとに-hwを配置していけばいいんじゃね?というノリでやったら無事死にました。

H=1,W=3,h=1,w=2で落ちるようです。( 2, -3 ,2 とすれば良い)

全然気づかなかったのでもうダメ。

 

D問題 XOR Replace

問題文は結構面倒なので省略。

a1,a2,....,x の値のセットは常に一定なので、末尾とのスワップのみでb1,b2....bnを作ることを考えました。

多分方針はあってるような気がするけど、時間も足りず終了(後半が本質らしいのでやっぱ無理)。

 

順位 275位 パフォーマンス 1996 レート1975(+2)

 

精進あるのみ。