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コード

（C++）Submission #42974255 - Codeforces

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++）Submission #42976889 - Codeforces

C. Array Product

Problem - C - Codeforces

問題概要

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

相異なるインデックス $i, j$ を選ぶ。 $a_{j}$ を $a_{i} \times a_{j}$ で置き換え、 $a_{i}$ を消去する。
この操作は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コード

（C++）Submission #42994169 - Codeforces

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

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つの仕切りの組が、そのまま条件を満たす区間に対応します。