AtCoder ABC141

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

AtCoder Beginner Contest 141

TL;TD

  • A:対応する文字を紐づけて出力するだけ
  • B:偶数、奇数の場合の文字列と一致するか全探索。途中で一致しなければ抜ける
  • C:K – Q + 正解数 がその人のもつ得点になる。O(N)
  • D:貪欲でチケット回数分、/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を参考にしてみた。

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の人の場合
x=3-4+2
=1
N1,N2の人の場合
x=3-4+1
=0
N4,N5,N6の人の場合
x=3-4+0
=-1

これを実装していけばOK。

実装的には、全員の得点の初期値をKとして配列で保持っておいて、Q-正解数の結果を引き算して実装。

Kが10^9なのでオーバーフローに注意すればOK。

提出 #7537582

文字列結合は遅いぞ

2019/09/16追記

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

TL;TD:

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

https://twitter.com/kirimin_chan/status/1173230925435375617

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

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

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

StringBufferなら早いぞ

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

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秒後に結果が戻ってくる
}

使用するテクニック

貪欲法

PriorityQueue

シェアする

  • このエントリーをはてなブックマークに追加

フォローする