ABC141の時の考察まとめ。
寝坊して40分遅めのスタート。
目次
TL;TD
- Ａ：対応する文字を紐づけて出力するだけ
- Ｂ：偶数、奇数の場合の文字列と一致するか全探索。途中で一致しなければ抜ける
- Ｃ：K – Q + 正解数 がその人のもつ得点になる。O(N)
- Ｄ：貪欲でチケット回数分、/2していけばいいことだけは分かった。テストケースでTLEしたので未提出
A – Weather Prediction
〇→△→□→〇→△→□→〇……と循環する。
次の値を答えればよいので、僕はMAPで対応表つくってmap.get()した。
解説は単純比較っぽい
B – Tap Dance
奇数の場合、偶数の場合で処理を分けて判定すればOK
奇：RUD
偶：LUD
なので、RとLの違いしかないのに今気づいた。
奇数のSETと偶数のSETを使って、set.contains(値)で一致判定。
一致しなければ即終了して”No”を出力。
全探索できたら”Yes”を出力。
解説ではpythonでの正規表現での解き方がある。
ここまで10分くらいでAC。
C – Attack Survival
最終的に各人が1ポイント以上（ Ai > 0 )であれば”Yes”,それ以外は”No”の問題。
正解者ごとに配列を操作していくと、Q * N = 10^10になってTLEしちゃいそう。
各人が何個正解したかは配列で算出できそうなので、いったん整理する。
入力例1を参考にしてみた。
6 3 4 3 1 3 2
| N1 | N2 | N3 | N4 | N5 | N6 | |
|---|---|---|---|---|---|---|
| 初期値 | 3 | 3 | 3 | 3 | 3 | 3 |
| A1->3 | 0 | 0 | 1 | 0 | 0 | 0 |
| A2->1 | 1 | 0 | 1 | 0 | 0 | 0 |
| A3->3 | 1 | 0 | 2 | 0 | 0 | 0 |
| A4->2 | 1 | 1 | 2 | 0 | 0 | 0 |
| 正解数 | 1 | 1 | 2 | 0 | 0 | 0 |
| 最終値 | 0 | 0 | 1 | -1 | -1 | -1 |
初期値はKなので、最初は全員がKを持っている状態。
正解したらポイントが増えたりはしないので、常に減算されることを意識する。
N4,N5,N6の人たちは正解数が1つもないので、質問の数（Q=4）だけ得点が減らされる。
N1,N2の人たちは1つ正解があるので、質問の数（Q=4）から1回だけ減点を防げる。
N3の人は2つ正解があるので、質問の数（Q=4）から2回だけ原点を防げる。
つまり、それぞれの人について以下が成り立つ。
最終得点 ＝ K – Q + その人の正解数;
N3の人の場合
ｘ=3-4+2
=1
N1,N2の人の場合
ｘ=3-4+1
=0
N4,N5,N6の人の場合
ｘ=3-4+0
=-1
これを実装していけばOK。
実装的には、全員の得点の初期値をKとして配列で保持っておいて、Q-正解数の結果を引き算して実装。
Kが10^9なのでオーバーフローに注意すればOK。
文字列結合は遅いぞ
2019/09/16追記
気になるツイートを見かけたので、kotlinではなくJavaなら通るのか試してみたくなった。
TL;TD：
文字を出力するケースは、とりあえずStringBufferかStringBuilder使っておけば早い。
https://twitter.com/kirimin_chan/status/1173230925435375617
参考にしたコードはこちら（@kiriminさんのコード）
Javaで書き直したコードはこちら。
結果は、ほぼ同じ条件でTLEでした。
StringBufferなら早いぞ
単純文字列結合ではなく、StringBufferなら通るっぽいのでいろいろ比べてみた。
コードお借りして試してみましたが、StringBufferを使えば前者でも通るようですね。(Javaは文字列結合がめっちゃ重いので)
次同じようなケースがあったらぜひ試してみてください！応援してますhttps://t.co/mj5JAOM8W2— da-louis (@vp_o_l) September 15, 2019
結合なしで都度、System.out.println()：AC
結果を一覧でまとめてみた（単位ms）。
TLEしやすいコードの場合は、都度出力するよりStringBuilderやStringBufferで連結したほうが早い模様。
更に言うと、結合する回数が少ないsample_01.txtなどでも、StringBuilderとprintlnに差がない。
| StringBuilder | StringBuffer | sysout | TLEしたケース | |
|---|---|---|---|---|
| sample_01.txt | 91 | 90 | 91 | |
| sample_02.txt | 89 | 90 | 90 | |
| sample_03.txt | 91 | 89 | 88 | |
| sub1_01.txt | 345 | 358 | 893 | 〇 |
| sub1_02.txt | 248 | 259 | 771 | 〇 |
| sub1_03.txt | 372 | 340 | 1040 | 〇 |
| sub1_04.txt | 254 | 251 | 801 | 〇 |
| sub1_05.txt | 154 | 149 | 660 | 〇 |
| sub1_06.txt | 331 | 332 | 977 | 〇 |
| sub1_07.txt | 327 | 328 | 832 | 〇 |
| sub1_08.txt | 252 | 232 | 786 | 〇 |
| sub1_09.txt | 343 | 320 | 868 | 〇 |
| sub1_10.txt | 319 | 320 | 945 | 〇 |
| sub1_11.txt | 357 | 334 | 961 | 〇 |
| sub1_12.txt | 375 | 348 | 1035 | 〇 |
| sub1_13.txt | 117 | 118 | 575 | 〇 |
| sub1_14.txt | 248 | 256 | 766 | 〇 |
| sub1_15.txt | 368 | 356 | 875 | 〇 |
| sub1_16.txt | 387 | 388 | 892 | 〇 |
| sub1_17.txt | 339 | 323 | 413 | |
| sub1_18.txt | 180 | 187 | 703 | 〇 |
| sub1_19.txt | 315 | 371 | 427 | |
| sub1_20.txt | 188 | 191 | 719 | 〇 |
| sub1_21.txt | 329 | 354 | 431 | |
| sub1_22.txt | 312 | 314 | 952 | 〇 |
| sub1_23.txt | 119 | 108 | 152 |
実際の業務でも、ログ出力は回数依存ですごく遅延するので一括で1回だけ出力したほうが効率的っぽい。
D – Powerful Discount Tickets
貪欲して各値を÷2していくと結果になるのは把握。
ただし、貪欲する為には配列がソート済みなことが条件になるので、毎回ソートが必要と考えて実装。
以下のテストケースでJUnit回したら11秒かかったので、提出見送り。
解説見て追記したい。
@Test
public void test_制約の最大値() {
int N = 100000; // 最大値
int K = 100000; // 最大値
Long[] A = new Long[N];
for (int i = 0; i < N; i++) {
A[i] = (long) Math.random() * 10000; // 最大値でもなんでも
}
long actual = D_PowerfulDiscountTickets.solve(N, K, A);
// 11秒後に結果が戻ってくる
}