naoya_t@hatenablog

いわゆるチラシノウラであります

〈AGC埋め〉B問題集中アタック(022-)

AGCも埋めていこう

6月23日

AGC 022 B - GCD Sequence (600)

考察。
素数を並べてみる:2,3,5とかじゃ無理。{2,5,63}はOK。サンプル2の{2,5,20,63}は2,5,63に20を追加したもの。インクリメンタルに増やして行けたりするのか?
gcd(a_i, Σそれ以外) = gcd(a_i, Σ全部) というのは分かるけど
2,5,x のxで条件を満たすものをサーチする、みたいなの事をして行って間に合うのか?(拡張ユークリッドっぽいことをする?)

  • 1〜30000の異なる数で20000件
  • 「なお、与えられた制約の下で解が少なくとも一つ存在することが保証される」そういうNしかテストケースに来ないということ?あるいは任意のNで可能だったりする?
時間切れにつき解説を読む
  • 5個までは決め打ちで行ける(2,5,63をベースに探索して追加していくコードを書いてみた)
  • 6個以上の場合は (1)合計を6の倍数にする (2)2の倍数と3の倍数だけ使う という戦略で。

6で割った余り(0,2,3,5のいずれかになる)に応じて、8か9を抜いて別の数を入れて調整する。
→WA(1): 8か9を抜くの忘れてた(末尾の数を変えてた)
→AC
https://beta.atcoder.jp/contests/agc022/submissions/2715007

余談

std::all_of, std::any_of, std::none_of, を使いこなして行きたい。

    if (all_of(ALL(a), [&](int ai){ return gcd(S, ai) != 1; })) break;

6月24日

AGC 021 B - Holes (600)

  • ボロノイ図?ドロネー図?とか作らないと駄目かなあ...と思いつつ
  • 無限遠から来た光が最初に届くのはどこだろう、と考える
  • 凸包を作って、凸包の各辺の法線方向より右から来たか左から来たかで(その辺の右の頂点か左の頂点に)振り分ければよさそう。
  • 凸包のある頂点に振り分けられる割合は、その頂点から左右に生える2辺の法線どうしのなす角度をatan2で求めて2πで割ったもの。凸包の内側に入っちゃった点については0%で。
  • convex_hullいつも自分で適当に書いて失敗するので今日はSpaghetti Sourceさんを写経した

→AC(時間測ってなかったけど1時間ちょいかかった)
https://beta.atcoder.jp/contests/agc021/submissions/2740398

解説を読む

解説解も同様。

また、凸包の辺上にある場合も、そのような領域の面積は O(R) なので、R を大きく取れば求める確率は 0 に収束します。

その辺りの考察が適当だったけど、まあ0に収束するので今回はセーフ

AGC 020 B - Ice Rink Game (500)

  • 二分探索で行ける?(単調減少するものなのかちょっと自信ないのでパス)
  • 〈線形走査〉最後に範囲[2,2]になるように逆算していく(a[] の後ろから見て行って範囲を更新していく)。

→WA(1)

intだと桁あふれするのか
long longにして
→AC
https://beta.atcoder.jp/contests/agc020/submissions/2740487

解説より

解説では方針として線形走査と二分探索を挙げている。

f には、広義単調増加であるという便利な性質があります。

二分探索の場合は、g(N)≧2になる最小のNと、2≧g(N)になる最大のNを求めることになる。