AOJ2200: Mr. Rito Post Office

数日悩んだ結果問題文誤読と気付いたのでキレそうです。

続きを読む

AtCoder Regular Contest 075 E - Meaningful Mean

ARCのEは解けるようにならないと不味い。

問題概要

N個数列のN*(N+1)/2個の空でない部分列のうち、算術平均がK以上のものはいくつあるか。

http://arc075.contest.atcoder.jp/tasks/arc075_c

解説

仮平均をすると楽なので、各a[i]からKを引いておくと、「算術平均がK以上」→「総和が非負」に言い換えられます。

累積和を使うと各区間が定数時間で求まるので、O(N2)で解くことが出来ますが、今回はO(NlogN)まで速くしないといけません。自分はここまででした。

b[i]=(a[0]+a[1]+…+a[i-1])-K*(i-1)とすると、b[i](0≦i≦N+1)がバラバラの値として存在していて、b[r]-b[l]≧0となるl,r(l<r)の数を求めるのが問題でした。rを左から順に見ていくとして、b[0],b[1],…,b[r-1]の中にb[r]以下の数がいくつあるかが分かれば問題が解けます。BITを使えばこれがO(logN)で求まるのですが、数が大きすぎるので、座標圧縮の要領でb[i]が何番目に大きいのかを求めたc[i]でBITをすればOKです。c[i]は0~N+1であることが保証されており、後はc[i]以下の数の個数をBITで求めて加え、BITにc[i]を追加する、ということを繰り返します。

BITはyukicoderのこの問題が似ている気がしたので載せておきます。練習用にどうぞ。

http://yukicoder.me/problems/no/59

以下解答プログラムです。結局O(NlogN)まで縮められました。

http://arc075.contest.atcoder.jp/submissions/1330330

感想

この問題の解説には「データ構造を使って計算量を落とす」としか書いていませんでしたし、自分もBIT位しか思いつかなかったのですが、O(N)まで落とせた人はいらっしゃるのですかね…

正直600点問題が解けなかったのは痛いです。実力も最近かなり酷いので、競プロに専念出来る環境が欲しい…

Codeforces Round #416 (Div. 2)

実力不足が出てきているので、ちゃんとブログ活用して精進しなくては…

続きを読む

AtCoder Regular Contest 073 E - Ball Coloring

長らく解けなかったので掲載。

問題概要

N組の2個のボールの組が与えられる。各組の片方を赤、もう片方を青に着色していったとき、赤のボールの範囲*青のボールの範囲の最小値を求めよ。

E: Ball Coloring - AtCoder Regular Contest 073 | AtCoder

 解説

AtCoder Beginner Contest 060 / AtCoder Regular Contest 073 解説 - はまやんはまやんはまやんを参考にしています。AtCoderの解説準拠です。

ボールを2色に分けるのですが、全体の最小値と最大値は必ずRmax、Rmin、Bmax、Bminのいずれかに属します。よって最大値と最小値がどちらに属するかで場合分けします。

  • 最大値と最小値が異なる色のとき 最大値を赤、最小値を青とします。ここで、赤は小さいほう、青は大きい方を求める必要があります。赤の最小値を大きく、青の最大値を小さくすればいいのですが、これは色を塗るときに組の大きいほうを赤、小さいほうを青に塗ればよいです。
    ということで、各組の大きいほう、小さいほうからのみなる配列を作って、その最大値-最小値をかければOKです。

  • 同じ色のとき 赤が最大値、最小値両方占めたとしましょう。すると、残りのN-2組から任意に片方だけ抜いていった時の最大値-最小値が小さくなればよさそうです。取り敢えず全部の組で小さいほうを選んだとして、その後値の小さい組から入れ替えていって、入れ替え後に最小値が大きくなる間更新し続けます。(逆に大きいほうだけを抜き出し、最大値を減らしても求める)。参考にしたurlでは一気にセグメント木で殴っていたので、自分もそうさせていただきました。

Submission #1259798 - AtCoder Regular Contest 073 | AtCoder

感想

最初、x,yが出ていて、「(x,y)か(y,x)に点を置いていくときに、点すべてを中に含む長方形の面積の最小値を求めよ」という風に解釈して苦労したのですが、こっちの考え方で解いた強者いらっしゃいますかね…

yukicoder No.497 入れ子の箱

解説見たら別解(ただし誰でも思いつきそう)だったので一応掲載。

続きを読む

AtCoder Beginner Contest 057

競プロが絶不調の中、「下手すると全完出来ないかも」と思いながらやってました。 (コンテスト中は寝ていたので、終了後から解き始め、無事に1時間で全完出来ましたが) 今回はA〜CをPython2、DをC++で解いてます。

続きを読む

みんなのプロコン D - 工場

segment treeがこういう使い方も出来る、という勉強になりました。

続きを読む