AtCoder Beginner Contest 018

 ゆっくりしっかり解いてみた。

結果

 400/400 112:29 55位相当

 

 開始時刻 2017/07/23 14:57:00 提出履歴

A: 豆まき - AtCoder Beginner Contest 018 | AtCoder

 4:11(AC)

 どうやるのが綺麗に行くんだろう。とりあえず3要素なので、maxと等しいなら1、minと等しいなら3、そうじゃないなら2ってことでAC。

B: 文字列の反転 - AtCoder Beginner Contest 018 | AtCoder

 11:08(AC)

 愚直にシミュレーション。反転部分を普通に実装してしまったけど、ちょっと調べたらstd::reverseなるメソッドが出てきた。これ使うなら多分std::reverse(s.begin()+l-1, s.begin()+r)でいい気がする。

C: 菱形カウント - AtCoder Beginner Contest 018 | AtCoder

 30:33(TLE, 30/100)112:29(AC)

 白い場所愚直に試すよりは黒い場所から届かないところ埋めて行くと早そう!→TLE。黒の方が多かったらなんの意味もないしなぁ。

 なんとなくここら辺の問題に似てる気がしたので、そう言う感じで考えた(実際は多分全然違う)。まず横方向の制限のみを考えて、あるセルが大きさk以下の菱形をおく中心になりえる、って言う情報を格納して行く。ある行に対して、左の制限と右の制限をそれぞれ走査して、その最小値を取るのが良さそう。

 で、そうなると縦方向にチェックするだけで菱形の存在可能性を絞れる。中心はK以上、あとは一つ上下にずれるたびに制限を1緩めていけばいいだけ。全てのチェックを通過したら個数としてカウントする。

D: バレンタインデー - AtCoder Beginner Contest 018 | AtCoder

 57:04(AC)

 二部グラフになるから最大マッチングとかに帰着するのかなぁと思ったけど、そういう感じの問題に見えないので考え直す。

 とりあえず考えつくのは女子のパターンと男子のパターンを全列挙する方法。これやると計算量がO(nCp*mCq)になるので、さすがに間に合わない。

 ただ、女子のパターンが決まれば男子にあげられる最大値が決まるので、男子のパターンは考えなくて良さそうなことに気づく。これだとO(nCp)なので十分間に合いそう。実際に間に合ってAC。

感想

 落ち着いて解けばなんとかなるなぁとは思った。でもこの問題を20分かからずに解くような人たちがまあまあいるのが信じられない。どういう頭の構造してるんだろう。