Codeforces Round#12(Div2 only)

参加。今回は夜中じゃない!うれしい!

結果

+00:04/+00:07/+00:18/-4/-1
28位 1414->1573

最初の3問でWA出さなかったのは及第点。だけど難しい問題を解く力がないよorz
高速データ構造苦手だなあ。

A. Super Agent

問題

9x9のマスで表され、いくつかのマスがXで残りが.のであるような図形がある。この図形が真ん中を中心として対称かどうかを判定せよ。

試行錯誤

上の列の三つと下の列の三つが逆順に対応していて、真ん中の列の左と右が対応してればおk.

書く。送信。AC.(4分)

B. Correct Solution?

問題

ある数nの各桁を並べ替えてできるような数のうち最小のものがmであるかを判定せよ。ただし数の先頭に0がきてはならない。

試行錯誤

nをStringで入力してソート。先頭が0なら次に出てくる0じゃないものと交換すれば、並び替えて最小になるような整数になる。それをmと比較すればおk.


あ、n=m=0のケースもあるのか。場合わけしておこう。


送信。AC.(7分)

C. Fruits

順調なんじゃないかこれ。

問題

n個の商品とn枚の値札がある。これを好きに商品に貼って、m個の商品を買うときの価格を最小および最大にせよ。

試行錯誤

ん?高い順にm個と安い順にm個値札を取るってことか?
書いてみる。サンプルとあわない。


えーと、同じ名前の商品には同じ値札をつけるらしい。1枚の値札が(同じ名前の)複数の商品につく場合があるようだ。
ここまでWAなしなので慎重にやろう。


商品の名前の出現回数をmapで数えて、値札を貼っていく。と。
あれーサンプルあわない。商品の個数逆順にしないとダメだ。おk修正。


送信。AC.(18分)

D. Ball

Standingsをみる。あ、wrongさんがうえーーのほうにいる。凄い。

問題

ある王国の女性は自分より「美しく」「知的で」「お金持ち」な女性の存在を知ると嫉妬で身投げしてしまう。王国の女性N人(N≦500000)の美しさ、知性、お金がそれぞれ与えられたとき、身投げする可能性のある女性の人数を求めよ。


i番目の女性の美しさをBi,知性をIi,お金をRiとするとBi<Bj,Ii<Ij,Ri<Rjとなるうような女性jがいるときにi番目の女性は身投げする可能性がある。

試行錯誤

問題文ひでえなw
Nが50万てことはO(N^2)だと間に合わなさげ……またデータ構造の問題っぽい。。。
とりあえず美しさでソートして線形に比較してってみよう。。。


書く。送信。WA.(case 3)


え。どこが間違ってるんだろ。ソースと問題文を必死こいて見直す。
どうもi+1行目にi番目の女性の美しさ、知性、お金が書いてあるのではなく、1行目に1番からN番の女性の美しさ2行目に……となっているらしい。
サンプル3x3だし答えも同じになってたから気づかなかった。


訂正。送信。TLE(case 34)


う、うん。ですよね。しばらく図を描いたりして考える。
解法思い浮かばない。問題Eを読もう。

E. Start of the season

問題

与えられた偶数n(n≦1000)に対して次の性質を満たすnxn行列を出力せよ。答えが複数ある場合はどれを出力してもよい。

  • 各成分は0以上n未満である
  • 対角線上の成分は0である
  • 各行のn個の整数は全て互いに異なる
試行錯誤

n≦1000ってことは探索むりぽいwPKUだったら入出力だけでTLEになりそうなサイズだ。
図を描く。n=5でよくわからん。


えーと、もう一度Standingsを確認。解いてる人一人しかいないからやっぱDにもどろう。

D(再)

しょうがないので適当に枝刈りを入れてみることにした。
Bの最大値をもつような女性、Iの最大値をもつような女性、Rの最大値をもつような女性をもっておき、それと比較して身投げする場合は即座に身投げさせる。(なんのこっちゃ)


送信。TLE.(case 34)


だめだ変わらない。
B,I,Rの最大値と一致する場合は身投げ失敗でループを抜ける。
→TLE.(case 34)


適当に数字が大きい人を保存しておいてその人と比較。
→TLE.(case 33)


あれ全然枝刈れてないどころか遅くなってるw


しばらく考えても全然解法が浮かばないので休憩して風呂。
風呂の中で、「結局身投げしない場合残りの人数全員を調べなくちゃいけないんだから、どう枝刈っても最悪ケースでTLEになりそう。だから四分木+座標圧縮書かないとダメだなあ」と悟るがそんなの書けるわけない。諦めて試合終了。