ABC089の時の考察まとめ
同じくらいのレート帯の競技プログラミングyoutuberのkiriminちゃんが生放送してたので、せっかくだからよーいドンで解いてみた。
目次
TL;TD
- Ａ：N/3
- Ｂ：Set化して3か4の場合わけ
- Ｃ：MARCHの各合計をci*cj*ck
- Ｄ：未回答。いずれやってみます
A – Grouping 2
3で割った時の商がグループ化できる最大値。
N8
〇〇〇 〇〇〇 〇〇 ＝ 2個〇〇〇がある
N9
〇〇〇 〇〇〇 〇〇〇 ＝ 3個〇〇〇がある
解説も特に変わらず。
提出 #7499667
B – Hina Arare
複数入力される場合、重複を省きたい場合はHashSetが便利。
（入力順をソートしたい場合はTreeSet）
入力をいったん全部Setに格納してから、Setのサイズを取得する事で何種類の要素があるか判定できる。
今回は3or4の2パターンしか入力されないようなので、そのパターンのMAPなり配列なり、判定分で出力処理を書けばOK。
解説では黄色のひなあられの有無で判定している模様。
制約見るとP,W,Gは必ず入力されるので、Yの有無だけ見ればよかったっぽい。
ここまで10分くらいでAC。
C – March
思いのほかてこずった。（2時間くらいかかった）
とりあえず入力から重複はないと考え、頭文字の個数をカウントしてみる。
総当たりだとN^3となりTLEなのでACできなかった。
どういった法則があるのか謎だったので、いったん総当たりで実装してから各文字の個数を増やしていった時の結果を見てパターンを見出そうとした。
ひとまず、入力例の各文字の個数を並べてみる。
| 文字 | M | A | R | C | H | 結果 |
|---|---|---|---|---|---|---|
| 例1 | 1 | 0 | 1 | 0 | 2 | 2 |
| 例2 | 0 | 0 | 0 | 0 | 0 | 0 |
| 例3 | 1 | 1 | 2 | 1 | 0 | 7 |
……流石にこれだけだと厳しい。
解説pdfは正直理解できず、youtubeの動画見たうえで実装を踏まえてやっと理解した。
3種類から3個選択するケースを考える
問題文そのままだと考えるのが難しいので、問題を簡単にしたい。
選択する個数と種類が完全に一致する場合はどうなるだろう？
表にしてみると、なんとなく関係性が分かりやすい。
| 文字 | M | A | R | 結果 |
|---|---|---|---|---|
| 例1 | 1 | 1 | 0 | 0 |
| 例2 | 1 | 1 | 1 | 1 |
| 例3 | 2 | 1 | 1 | 2 |
| 例4 | 3 | 1 | 1 | 3 |
| 例5 | 2 | 2 | 1 | 4 |
| 例6 | 3 | 3 | 1 | 9 |
| 例7 | 2 | 2 | 2 | 8 |
3種（M,A,R）から3個（つまり全部取る）の場合、M,A,Rの個数を掛け合わせた値が結果となる。
4種類から3個選択するケースを考える
続いて、4種から3個選択する場合はどうなるだろうか。
| 文字 | M | A | R | C | 結果 |
|---|---|---|---|---|---|
| 例1 | 1 | 1 | 1 | 0 | 1 |
| 例2 | 2 | 1 | 1 | 0 | 2 |
| 例3 | 1 | 1 | 1 | 1 | 4 |
| 例4 | 2 | 1 | 1 | 1 | 7 |
| 例5 | 3 | 1 | 1 | 1 | 10 |
| 例6 | 2 | 2 | 1 | 1 | 12 |
| 例7 | 3 | 3 | 1 | 1 | 24 |
| 例8 | 2 | 2 | 2 | 2 | 32 |
一見して法則性が見当たらない。
3種の場合は全取得でOK（1通りしかない）が、種類＞個数の場合は組み合わせが存在する。
MARCという4種類の中から3個選択する組み合わせは、
4C3
=4*3*2/3*2*1
=24/6
=4通り。
つまり、
MAR
MAC
MRC
ARC
の4通り。
これらの組み合わせそれぞれに対して、先ほどの3種類から3個選択するときと同様に掛け算する。
その結果を全て合算した値が、4種類から3個選択する場合の合計値となる。
上記テーブルの例6を参考にしてみる。
| 文字 | M | A | R | C | 結果 |
|---|---|---|---|---|---|
| 例6 | 2 | 2 | 1 | 1 | 12 |
各パターンに応じた、掛け算を行うとこうなる。
| 文字 | M | A | R | C | 結果 |
|---|---|---|---|---|---|
| MAR | 2 | 2 | 1 | – | 4 |
| MAC | 2 | 2 | – | 1 | 4 |
| MRC | 2 | – | 1 | 1 | 2 |
| ARC | – | 2 | 1 | 1 | 2 |
各選択の合計を足すと、4 + 4 + 2 + 2 =12となっているので、考え方として問題なさそう。
5種類から3個選択するケースを考える
考え方は4種から3個選択する場合と同じ。
今回は、計算する組み合わせは 5C3で10通り。
4種類の時の4通りに比べて合算する個数は多少増えるが、TLEになる程ではない。
入力例3を元に、実際に確かめてみる。
| 文字 | M | A | R | C | H | 結果 |
|---|---|---|---|---|---|---|
| MAR | 1 | 1 | 2 | 2 | ||
| MAC | 1 | 1 | 1 | 1 | ||
| MAH | 1 | 1 | 0 | 0 | ||
| MRC | 1 | 2 | 1 | 2 | ||
| MRH | 1 | 2 | 0 | 0 | ||
| MCH | 1 | 1 | 0 | 0 | ||
| ARC | 1 | 2 | 1 | 2 | ||
| ARH | 1 | 2 | 0 | 0 | ||
| ACH | 1 | 1 | 0 | 0 | ||
| RCH | 2 | 1 | 0 | 0 |
合計値は 2 + 1 + 0 + 2 + 0 + 0 + 2 + 0 + 0 + 0 = 7
となり想定通りの動きとなる。
実装的には、for文を取得したい回数である3重ループにして、各ループを5種類である上限5回にすればよさそう。
以下、疑似コード
march[] long ans; for i (0 ... 5) for j (i+1 ... 5) for k (j+1 ... 5) ans += march[i] * march[j] * march[k] print(ans)
問題文見て、楽に解けそうだと思ったら大沼だった。
組み合わせとか最適化問題弱いので、もうちょい精進しないとダメですねー。
使用するテクニック
重複組み合わせ
N種類からM個取得する（重複可）場合、Nの各個数を全部かけ合わせればOK。
3種類から3個の場合、全ての要素を掛け合わせる。
4種類から3個の場合、全ての要素の個数パターン（4^3パターン）を掛け合わせた合計値。
5種類から3個の場合、全ての要素の個数パターン（5^3パターン）を掛け合わせた合計値。
for(int i=0; i<N; i++){
// M重ループする
}
といった具合でループして合算すると良さそう。
組み合わせ式
nHr = n+r-1C r
ex)5C3
=5*4*3 / 3*2*1
=60/6
=10通り