ARMERIA

放置していたけど更新再開、Rubyと競技プログラミングの話が中心になっていく予定です

Codeforces Round #510 参加記録

Dashboard - Codeforces Round #510 (Div. 2) - Codeforces

結果は4完…ですが、CとDが遅くて誤答ペナルティもかなり付いてるので順位は低めです(配点はA~Dで500-1000-1500-2000です)

f:id:betrue12:20180917214859p:plain

A~Dを振り返ります。

A. Benches

Problem - A - Codeforces

問題概要

 n 個の整数  a_{1}, ..., a_{n} が与えられる。この数列に「いずれかの要素の値を1増やす」操作を  m 回行い、操作後の  a_{i} の最大値を  k とする。

 k の取りうる値の最小値と最大値を求めよ。

制約

  •  1 \le n \le 100
  •  1 \le m \le 10000
  •  1 \le a_{i} \le 100

解法

最大値のほうが簡単です。操作前で最も大きな要素に  m を足すだけです。

最小値のほうは、なるべく平坦になるように要素を足していきたいです。ですが、元々の要素の最大値を下回ることはできません。 \lceil\frac{\sum a_{i} + m}{n}\rceil \max a_{i} のうち大きい方が答えです。

ACコード

B. Vitamins

問題概要

 n 個の要素について、そのコスト  c_{i} と、ABC をそれぞれ0個または1個含む文字列  s_{i} が与えられる。

ABC 全ての文字を1つ以上含むように要素をいくつか選ぶ時、その合計コストの最小値を求めよ。

制約

  •  1 \le n \le 1000
  •  1 \le c_{i} \le 100000
  •  s_{i} は1~3文字であり、 ABC をそれぞれ0個または1個含む

解法

私は要素を順に見ていくDPをしました。dp[i][S] を、「  i 番目の要素まで見て、既に取った文字の集合が  S であるときの最小コスト」とします。

 S は3つの要素を取った/取ってないの8通りであり、ABC それぞれをビットで管理すると0~7までの整数で表現できます。新しく要素を取った時の集合の遷移は、ビットのor演算を使って実装することができます。

他の方法もあります。高々8通りしかないパターンに1000個の要素があるため、無駄な要素が大量にあります。含む文字が同じ要素の中では、コストが最小のもの1つだけを考えれば十分です。そうすると高々8個の要素しか残らないので余裕で全探索できます。こっちのほうがスマートですね…

ACコード

C. Array Product

Problem - C - Codeforces

問題概要

長さ  n の数列  a_{1}, ..., a_{n} が与えられる。この数列に以下の操作を行う。

  1. 相異なるインデックス  i, j を選ぶ。  a_{j} a_{i} \times a_{j} で置き換え、 a_{i} を消去する。
  2. この操作は1度だけ行える。インデックス  i を選び、  a_{i} を消去する。

これらの操作を合計  n-1 回行うと要素が1つだけ残る。この要素を最大化するような操作手順を1つ示せ。

制約

  •  2 \le n \le 2\times 10^{5}
  •  -10^{9} \le a_{i} \le 10^{9}

解法

問題文の操作は、結局「0個以上の要素を消去し、残りの要素を全て掛け合わせる」という操作になります。複数の要素を消去する場合は、1の操作で消去したい要素を全て掛け合わせてから、最後に2の操作で消せばよいからです。

ということで、上記の操作で最終的な要素を最も大きくするにはどうすればよいか考えます。

  • 正の要素:残す。
  • 負の要素:偶数個なら積が正になるので残す。奇数個の場合、絶対値が最も小さいものを1つ消し、他を残す。
  • 0の要素:基本的には消す。

これが原則になりますが、このまま実装すると「全部0」や「負数1個+残り全部0」の時に全部消す扱いになってしまうので注意です。これらの場合は単に全部の要素をかけ合わせれば良くて、最後に残る要素の最大値は0です。

ACコード

本番コードがあまりにも汚かったので書き直しました…

D. Petya and Array

Problem - D - Codeforces

問題概要

長さ  n の数列  a_{1}, ..., a_{n} が与えられる。その連続部分列のうち、和が  t より小さくなるものの個数を求めよ。

制約

  •  1 \le n \le 200000
  •  |t| \le 2\times 10^{14}
  •  |a_{i}| \le 10^{9}

※絶対値表記になっている要素は、正・負・0の値を取り得る

解法

全要素が非負だとしゃくとり法が使えたりするのですが、負の要素がある場合はもう少し複雑な処理をしなくてはいけません。

まず、数列の区間和を累積和の差だと考えることがポイントです。 n 個の要素について、最初の0を含めて順次累積和を取ります。これらの累積和は以下のような要素間の仕切りに対応し、 (右の仕切りの値) - (左の仕切りの値) \lt t を満たす2つの仕切りの組が、そのまま条件を満たす区間に対応します。

f:id:betrue12:20180917212120p:plain

ということで、各仕切りについて「自分より左に存在する仕切りで、さきほどの条件を満たすものはいくつあるか?」という問題を考えます。仕切りを順番に見ていきながら数え上げることを考えると、

  • ある点に値を追加する
  • 範囲内の値の総和を求める

を順不同で行えるようなデータ構造、BITを使えば解けそうです。

ただし、今回の問題では累積和として取り得る値が非常に大きくなる可能性があります。この方法では累積和の値をBITのインデックスとして使います。長大なBITを作れればよいのですが、メモリも計算時間も足りません。ということで、座標圧縮を行います。

座標圧縮を行うと、値の種類は高々仕切りの個数である  n+1 種類しかないので、(0始まりであれば)  0, ..., n の範囲に収まります。これならBITを作って、現実的なメモリや時間で計算できそうです。

圧縮を行ってしまうと、「  (右の仕切りの値) - (左の仕切りの値) \lt t を満たす左の仕切りの値はどこまでか?」というのがすぐには分からなくなってしまいます。ですが、この条件を満たす/満たさないの境界は、圧縮前の座標を二分探索することで求めることができます。

f:id:betrue12:20180917214154p:plain

累積和が単調変化にならないようなケースで、区間和がある値以上/以下である区間の数え上げをBITで行う…というのはよく見る問題ですね。習得しておくとかなり役立つと思います。

ACコード

さいごに

今回はC問題でハマって多くの時間を使ってしまいました…考察が十分に整理できないままコードを書き上げてWAやREを量産してしまったので、反省です。