AtCoder ABC141

ABC141の時の考察まとめ。
寝坊して40分遅めのスタート。

AtCoder Beginner Contest 141

1 TL;TD
2 A – Weather Prediction
3 B – Tap Dance
4 C – Attack Survival
- 4.1 文字列結合は遅いぞ
- 4.2 StringBufferなら早いぞ
5 D – Powerful Discount Tickets
6 使用するテクニック
- 6.1 貪欲法
- 6.2 PriorityQueue

TL;TD

Ａ：対応する文字を紐づけて出力するだけ
Ｂ：偶数、奇数の場合の文字列と一致するか全探索。途中で一致しなければ抜ける
Ｃ：K – Q + 正解数がその人のもつ得点になる。O(N)
Ｄ：貪欲でチケット回数分、/2していけばいいことだけは分かった。テストケースでTLEしたので未提出

A – Weather Prediction

〇→△→□→〇→△→□→〇……と循環する。

次の値を答えればよいので、僕はMAPで対応表つくってmap.get()した。

解説は単純比較っぽい

提出 #7532680

B – Tap Dance

奇数の場合、偶数の場合で処理を分けて判定すればOK

奇：RUD

偶：LUD

なので、RとLの違いしかないのに今気づいた。

奇数のSETと偶数のSETを使って、set.contains(値)で一致判定。

一致しなければ即終了して”No”を出力。

全探索できたら”Yes”を出力。

解説ではpythonでの正規表現での解き方がある。

ここまで10分くらいでAC。

提出 #7534936

C – Attack Survival

最終的に各人が1ポイント以上（ Ai > 0 )であれば”Yes”,それ以外は”No”の問題。

正解者ごとに配列を操作していくと、Q * N = 10^10になってTLEしちゃいそう。

各人が何個正解したかは配列で算出できそうなので、いったん整理する。

入力例1を参考にしてみた。

	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。

提出 #7537582

文字列結合は遅いぞ

2019/09/16追記

気になるツイートを見かけたので、kotlinではなくJavaなら通るのか試してみたくなった。

TL;TD：

文字を出力するケースは、とりあえずStringBufferかStringBuilder使っておけば早い。

ABC完でしたが時間ではほぼ最下位です。
理論上問題ない計算量の解法自体は1時間の時点で完成してたのにTLEが解消できなくてほぼ時間使い果たしました。理由は出力のためのString生成が重く、PrintWriterを使って全行個別printlnしないと間に合わないことでした

— きりみんちゃん💮バーチャル男声幼女プログラマー (@kirimin_chan) September 15, 2019

参考にしたコードはこちら（@kiriminさんのコード）

Javaで書き直したコードはこちら。

結果は、ほぼ同じ条件でTLEでした。

StringBufferなら早いぞ

単純文字列結合ではなく、StringBufferなら通るっぽいのでいろいろ比べてみた。

コードお借りして試してみましたが、StringBufferを使えば前者でも通るようですね。(Javaは文字列結合がめっちゃ重いので)
次同じようなケースがあったらぜひ試してみてください！応援してますhttps://t.co/mj5JAOM8W2

— da-louis (@vp_o_l) September 15, 2019

StringBuilder：AC

StringBuffer：AC

結合なしで都度、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秒後に結果が戻ってくる
}