AtCoder ABC142

abc, atcoder

ABC142で初めてABCD4完できたので記念にまとめ。
実際には自力で理解できたわけではなく、ぐぐって解決できた感じ。


AtCoder Beginner Contest 142

 

TL;TD

  • Ａ：Nを全探索した奇数の数 / N
  • Ｂ：Nを全探索して、各要素についてK以上か調べる
  • Ｃ：Ai-ANの昇順で、その要素番号を出力。
  • Ｄ：AとBそれぞれの公約数を全列挙して、どちらにも含む値が素数かどうか判定する。
  • Ｅ：直観的にDPっぽいと思った。DP不慣れで実装できず。結局bitDP(DPキーがbit)らしい

 

A – Odds of Oddness

1分46秒でAC

 

普通にfor文で全探索しました。
最後に(double)でキャストするのを忘れずに。

提出 #7735470

 

別解：
解説PDF詳しすぎてびびる。
後から全探索しないやり方を思いつきました。

 

入力が奇数か偶数かによって、その値がいくつ奇数の数を持つか決められます。

偶数の場合
Nをちょうど2で割った数。

奇数の場合
Nを2で割って、1足した数。

 

あとは上記の解法と同じで、doubleに気を付けてNで割ってあげればOK。

提出 #7784544

 

B – Roller Coaster

3分35秒でAC

 

パット見ただ全件探索するシミュレーションなので、そのまま解く。
Nが10^5で、全件みてもそんなに時間がかからない。

 

これくらいの雰囲気だと、入力を一度配列に入れなくてもそのまま判定してしまった方が早いかもしれません。

 

提出 #7737505

 

C – Go to School

9分30秒でAC

 

問題文がたまたまスムーズに理解できた問題。
イメージは以下のような感じ。

 

 

来た人のID（インデックス）を出力にそのまま置き換えていく感じ。
実装時には、来た順とインデックスを紐づけしたデータを定義して、来た順で昇順ソートする。

 

実装は、TreeMap＜来た順、インデックス＞で格納してfor文回しました。
提出 #7743523

 

D – Disjoint Set of Common Divisors

79分12秒でAC

 

AtCoderで初めてのコンテスト中D問題AC！

嬉しすぎて思わず、非エンジニアの嫁に報告しました。

 

最初、問題文を見て数学問題かつ制約の10^12を見てビビりました。
その後、入力例2を見て、場合を頭の中で数え上げられそうになかったので回答を一時保留にしてE問題へ。
なので、実際の着手は50分頃からだったと思います。

 

最大公約（GCD：GreatestCommonDevisor）を素因数分解。
と言われてもピンとこない数学の素養感なので、愚直に実装しました。

 

大きくわけて3つのステップに分けて実装しました。

  1. AとBの公約数を全部列挙したリストを持つ。
  2. AとBのどちらにもある値をもつリストを持つ。
  3. 2のリストの全ての値が素数かどうかを判定して、素数の数を数える。
  4. 数えた素数の値に、1を足して出力※1

2と3が厳密に、”互いに素”を呈しているかは証明力がなく証明できないので、微妙です。
ここで問題となるのが、1番目の公約数列挙の部分の”実行時間”ですが、間に合いそうだったので良かったです。

  • 1. AとBの公約数を全部列挙したリストを持つ。

まず自前で実装するのは諦めて、ググってみる事に。
とりあえず標準ライブラリとか探してググって出た、個人ブログのアルゴリズムを拝借して、今回のケースにあてがいました。
（主に引数型とかローカル変数のintをlongに変更）

  • 2. AとBのどちらにもある値をもつリストを持つ。

出来上がったリストをcontainsで比較して、秒殺できそうなのでforループ。
ただ、仮に10^12のリストだった場合、メモリも時間も怪しいです。

実際に動かしてみて、制約である10^12を入力した公約数が144個だったので、その心配はなさそうでした。

  • 3. 2のリストの全ての値が素数かどうかを判定して、素数の数を数える。

自前だとバグらせそうで怖かったのでググって解決。
入力がでかすぎると問題っぽいですが、前述とおりせいぜい144個なので問題ないと判断。

  • 4. 数えた素数の値に、1を足して出力※1

今までの結果では、素数判定した値なので1をカウントする値として含んでいません。
なので、1加算した値を答えとして出力します。

以上、1~4を実装した提出

提出 #7764163

 

別解。
解説youtube（47分頃～）じっくりみたけど、根本的な解法を自力で思いつくことは難しそうです。

ただ、素因数分解だったり、GCDの実装をかなり丁寧に解説していたので、その辺弱い人は一度見ておくとスッキリすると思います。

 

以下、解説youtubeメモを元に実装し直し。
素因数分解のところで若干躓いたけど、今後はこの辺を参考に実装組めそう。
提出 #7774288

 

E – Get Everything

解説youtube（1時間33分30秒頃～）後AC

 

実はコンテスト中、C問題後に先に実装したのはこちらでした。
最初は鍵を選ぶ、選ばないの2択を選択していくDPっぽいと思いつつ、使える技術手札が貪欲くらいしかないので貪欲で挑戦。

しかし鍵の状態を高速なデータ構造にする方法が思いつかず、コンテスト中は見送ることに。

 

解説youtubeを見て、2時間くらいかけてやっと解けました。

データ構造はMap＜集合番号、鍵コスト＞として、同じ集合番号のものは鍵コストが安い方で上書きしていく感じに。

あとは解説どおり、鍵集合番号の順に、全ての組み合わせをDPしていく。
DPの初期化値を、いつも通りInteger.MAX_VALUEとか0とかやるとWA貰います。

 

シフト演算とかjava使ってて初めて書きました。
あと、bitDPなるものも初めて触れました。集合的な考え方と扱いは今後使えそうなのでいい感じです。

提出 #7781786

 

以下、解説youtubeメモ

 

使用するテクニック

bitDP

DPの添え字にbit演算（今回は2進数）を使う手法。
集合は空集合→1つの集合→2つの集合と計算していくので、集合のIDをbit値にしておくことで計算する順番を簡単に実装できる。

シフト演算

int shift = 1 << n;

で計算可能。
javaの場合、値は0001,0010,1001などにはならず、2,4,512といった2の累乗と同値になるっぽい。

2の累乗が欲しい場合は1<<nで求められる。

GCD

GreatestCommonDivisor
最大公約数

以下、実装を2つ示すが、どちらも等価

static int gcd(int x, int y){
    // y != 0 の場合、再帰的に実行される。
    return y == 0 ? x : gcd(y, x % y);
}

static int gcd(int x, int y) {
    // y != 0 の場合、再帰的に実行される。
    if (y == 0) {
        return x;
    }

    if (x >= y) {
        x = x % y;
    }
    return gcd(y, x);
}

素数

1とその数以外で割り切ることができない数。
以下実行

static boolean isPrime(long n) {
    if (n == 2) {
        return true;
    }
    if (n < 2 || n % 2 == 0) {
        return false;
    }

    double sqrtNum = Math.sqrt(n);
    for (long i = 3; i <= sqrtNum; i += 2) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

 

おまけ（出力のスペース区切りについて）

競技プログラミングではよくある、スペース区切りでの出力ですが、改行区切りでもＯＫみたいです（AtCoderのみ？）

 

そもそも、出力はスペースである必要があって、最後の行に改行が必要。というのは本質ではないということで、緩めになった模様です。

 

解説youtubeで言及されてました。

シェアする

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

フォローする

, , Naoto