E - Multiplication 4(AtCoder Beginner Contest 173)

問題リンク

atcoder.jp

問題概要

 \(N\)個の整数\(A_1,A_2,...,A_N\)が与えられる

この中から、ちょうど\(K\)個の要素の積としてありうる値の最大値を求め、

10^9+7で割った余りを答えよ。

制約：

• \(1 \leq K \leq N \leq 2 \times 10^5\)
• \(|A_i| \leq 10^9\)

解法

 基本的な戦略としては、Aの要素を絶対値が大きい順にソートしてK個選んで積を計算した後、

それが正ならばそのまま出力、

負ならば

• 選んだ正の要素のうち絶対値が一番小さいものを除き、選んでいなかった負の要素の中で絶対値が最も大きいものを掛ける
• 選んだ負の要素のうち絶対値が一番小さいものを除き、選んでいなかった正の要素の中で絶対値が最も大きいものを掛ける

のいずれかで、解の絶対値が大きくなる方を選べば良い。

例：

6 3

6 -5 4 -3 2 -1

このとき、まずは\(6 \times (-5) \times 4 = -120\)を解の候補とする。

これは負なので次のどちらかを選択する。

• 選んだ正の要素のなかで絶対値が最小の4を、選んでいなかった負の要素のなかで絶対値が最大の-3に変える。
• (上の正負を逆転して)-5を2に変える。

このとき、前者は解の絶対値が\(3/4\)倍され、後者は\(2/5\)倍される。

\(3/4 > 2/5\)なので前者を選ぶ。

最終的な解は\(6 \times (-5) \times (-3) = 90\)。

以下の点に注意する。

• そもそもK個の積が負にしかなりえない場合(サンプル2)。この時は絶対値が最もちいさいものが答えになる。
• K個の積が負、もしくは0になる場合*1。この時は答えが0になる。
• 上の「負ならば～」の部分で、選んだ要素が正/負のみ、選んでいなかった要素が正/負のみの場合。
• 「負ならば～」の部分の解の変化の比較で、小数を使うと誤差の危険がある。\(A/B > C/D \Leftrightarrow AD > BC\)(ただしすべて正)を利用して整数のまま比較する。
• 負の数の剰余。出力が「0以上10^9+6以下の整数」になるように調整する。

提出

https://atcoder.jp/contests/abc173/submissions/14993932

感想

かなり注意してやったけど、コーナーケースと全然関係ない論理ミスでWA出した。

*1:例えば
4 3
-1 -1 -1 0

F - Intervals on Tree(AtCoder Beginner Contest 173)

問題リンク

atcoder.jp

問題概要

\(N\)頂点の木が与えられる。各頂点には\(1,...,N\)の番号が振られている。

\(1 \leq L \leq R \leq N\)に対し

\(f(L, R)\) を、「番号\(L\)以上\(R\)以下の頂点と、両端の番号が\(L\)以上\(R\)以下の頂点であるような辺からなる部分グラフの連結成分の個数」と定義する。

\(\sum_{L=1}^N \sum_{R=1}^N f(L,R)\)を求めよ。

解法

 各\(L,R\)に対し、できる部分グラフは森(各連結成分が木であるグラフ)となる。

このグラフには次のような性質がある：

• (連結成分の個数) = (頂点の個数) - (辺の本数)

これは各連結成分に対し(頂点の個数)-(辺の本数)=1であることからわかる。

よって、求める値は

\(L\)と\(R\)を動かした時の

(頂点の個数の合計) - (辺の本数の合計)

となる。

頂点の個数の合計は、\(i=1,...,N\)に対し

\(L \leq i \leq R\)となる\((L,R)\)の組の個数の和なので

\(\sum_{i=1}^N i \times (N-i+1)\)である。

辺の本数の合計は、辺\( (u,v)\) (ただし\( u < v\) )に対しそれを含む\((L,R)\)は

\(L \leq u\), \(v \leq R\)を満たすことが必要十分なので

\(\sum_{i=1}^{N-1} u_i \times (N-v_i+1)\)となる。

提出

https://atcoder.jp/contests/abc173/submissions/14996570

感想

 気づきさえすれば楽。

連結成分の個数は頂点・辺の個数で言い換えられるといい感じ。

F - Strivore(AtCoder Beginner Contest 171)

問題リンク

atcoder.jp

問題概要

英小文字からなる文字列\(S\)と自然数\(K\)が与えられる。

\(S\)に「好きな位置に好きな英小文字を1つ挿入する」という操作をちょうど\(K\)回繰り返して得られる文字列の総数は何通りか。

解法

\(S\)の文字数を\(N\)とおく。

求めるものは、「\((N+K)\)文字の文字列で、\(S\)を(連続とは限らない)部分列に持つものの総数」である。

これは次のように言い換えられる。

• a~zの文字が書かれた26面体のサイコロがある。Sの先頭から見て、現在見ている文字と同じ文字が出たらそれを書いて次の文字に進む、という作業を\((N+K)\)回繰り返す(\(S\)が完成してもサイコロは振り続ける)。目の出方\(26^{N+K}\)通りのうち、\(S\)が完成するのは何通りか。

\(N \leqq i \leqq N+K\)とし、ちょうど\(i\)回目で\(S\)が完成する場合を考えると、

\(1...(i-1)\)回目ではちょうど\(N-1\)回当たりの目(見ている文字と一致する目)、\(i-N\)回外れの目が出て、

\(i\)回目では\(S\)の最後の文字が出て、

\((i+1)...(N+K)\)回目では任意の目が出ている。

よってこの場合の総数は \( {}_{i-1} C_{N-1} \times (26-1)^{i-N} \times 26^{N+K-i} \) 通りになる。

これを\(i\)を\(N\)から\((N+K)\)まで動かして足せば答えが出る。

また、「当たりの目がN回以上出る組み合わせの総数」と考えて

\(\sum_{i=N}^{N+K} ({}_{N+K} C_{i} \times (26-1)^{N+K-i} )\)としても答えが得られる。

提出 

https://atcoder.jp/contests/abc171/submissions/14552574

感想

昨日のAGCでも文字列の数え上げが2つ出たけど、どれも違う解法で良かった。