AtCoder Beginner Contest 112

2018年10月7日

TNP

こんばんえるえる〜〜〜〜ガナリヤです大学の後期がついに始まりましたね今週一週間は毎日しんどくて未だに体の疲れが取れません。コミュニケーション能力を付けないとこのままではまずい気がします。

今回は、AtCoderBeginnerContest112に出ました。結果としては、ABCD4完は出来ましたが、Cで4WAしているのでもうちょっと細かい部分に意識をしないといけませんね･･･早速内容を振り返っていきましょう！

A 「Programming Education」

問題文

AtCoderはクソデカ年商となり、プログラミング教育をするようになった。入力から自分の年齢Nが入力される。 N=1なら"Hello, World"と出力せよ。 N=2ならA+Bの答を計算せよ。

解法

やるだけです。もう20秒ぐらい早くとけるようになりたいです。

B 「Time Limit Exceeded」

問題文

Xさんは、外から家に帰ろうとしています。現在位置から家に帰るルートは、N個存在しますが、それぞれに係る時間tiと、かかるコストciがあります。時間T以内に、帰らなければいけない時、最小のコストを求めてください。

解法

時間T以内なので、時間T以内のルートのみを列挙して、さらにその中でも一番コストの低いものを出力してしまえばいいです。気をつける点としては、ルートが一つもない場合はTLEと出力しないといけないので、最初の変数の初期化で上限いっぱいにしておいて、値が更新されてなければTLEとしないといけません。実装に2分もかかったので半分ほどにするひつようがあります。

コード

[cpp]

int main() { LL N, T; cin >> N >> T; LL cost = LONG_LONG_MAX; for (int i = 0; i < N; i++) { LL c, t; cin >> c >> t; if (t <= T) { S_MIN(cost ,c); } } if(cost == LONG_LONG_MAX){ OUT_L("TLE"); }else{ OUT_L(cost); } return 0; }

[/cpp]

Pyramid

問題文

問題文長すぎるのでここを見て→ https://beta.atcoder.jp/contests/abc112/tasks/abc112_c

解法

内容としては簡単だったのですが、3つ特殊ケースがあり、そのケースに気づくまで時間がかかってしまいました。

制約を見るとCxもCｙも0~100以内なので、全探索しても余裕で間に合うことが分かります。
中心のCx、Cyを仮に全探索してみます。すると、中心の高さHを求めたいわけですが、この高さは他の点1つを選んでしまえば逆算することが出来ます。そうして求めたHと他の点を全て比べて、条件を満たせばそれが答えになります。

しかし、この解法だけだとうまくいかない場合があり、参考にする点が高さ０の場合です。高さ０の場合、もともと高度は(H -|X - Cx| - |Y - Cy|, 0)のため、マンハッタン距離で0だったのか、最初から0だったのか判断することが出来ません。よって、関係ない答を出力してしまう可能性があります。よって、そのケースは省いて計算する必要があります。体感的にBレベルでしたが、特殊ケースだけはDレベルな感じがしました。

コード

[cpp] int main() { int N; cin >> N; VLL x(N), y(N), h(N); REP(i, N) cin >> x[i] >> y[i] >> h[i]; for (LL i = 0; i <= 100; i++) { for (LL j = 0; j <= 100; j++) { LL H = 0; for (LL k = 0; k < N; k++) { if (h[k] != 0) { H = h[k] + ABS(i - y[k]) + ABS(j - x[k]); break; } } if (H <= 0) continue; bool good = true; for (int k = 0; k < N; k++) { LL _h = C_MAX(H - ABS(i - y[k]) - ABS(j - x[k]), 0LL); if (_h != h[k]) good = false; } if (good) { cout << j << " " << i << " " << H << endl; return 0; } } } return 0; }

[/cpp]

D Partition

問題文

整数N, Mが与えられます。 a1 + a2 + ･･･ + aN = Mとなるような長さNの数列aにおいて、a1~aNの最大公約数となる最大値を求めてください。

解法

Mが与えられるので、可能性のあるaの組み合わせを作成し、その最大公約数を求める必要があります。最大の最大公約数であるため、少し工夫しないといけません。なぜなら、制約でNが10万のため、計算量的にNlogNが最大であるためです。

そこで、最大公約数について一度考え直して見ます。最大公約数は、a全てにおいて、共通の約数を持っており、共通の約数ということは同じ倍数を持っているということに等しいです。共通の倍数をKとすると K_b1 + K_b2 + ･･･ + K_bN = Mということになります。つまりM = K * (b1 + b2 + ･･･ + bN)というわけで、Mは因数としてKを持つことが分かります。よって、Mに対して、約数を列挙し、その約数の中で、NをかけてもMを超えないものが答となります。約数をTとして、T_N < Mのとき、数が余らないか？というう話になりますが、Mも因数Kを持つため、うまく配分すれば全ての変数がKを因数に持つことが分かります。

素因数分解はO(√N)でできるので、計算量的にも間に合うことが出来ます。

今回のDは3分で通せたので、成長を感じます。(なお、C)

コード

[cpp]

//nの約数 template vector DIVISOR(T n) { vector v; for (LL i = 1; i * i <= n; ++i) { if (n % i == 0) { v.push_back(i); if (i != n / i) { v.push_back(n / i); } } } sort(v.begin(), v.end()); return v; }

int main() { LL N, M; cin >> N >> M; auto divisors = DIVISOR(M); LL maxV = 1; for (int i = 0; i < SZ(divisors); i++) { if(divisors[i] * N <= M){ maxV = divisors[i]; } } OUT_L(maxV); return 0; }

[/cpp]

###　感想

今回の問題は、Cが一番難しかった感じがあります。 4WAは流石に出しすぎなので、もうちょっとミスを減らさないといけませんね･･･

ガナリヤでした！