ブログ名

競技プログラミングやお歌のお話をする高菜です。

トップ > ABC 151 解法

ABC 151 解法

コンテストページ

AtCoder Beginner Contest 151 - AtCoder

解法

✔A - Next Alphabet（100 点）

C++ ならば、char 型で受け取ってインクリメントすればよいです。

✔B - Achieve the Goal（200 点）

最低限必要な合計点は n * m 点です。それと今までの差を計算しましょう。 それが 0 以下であれば既に足りているので答えは 0 です。 また K を超えていたら、時既に遅しですから、−1 を出力です。

✔C - Welcome to AtCoder（300 点）

どの問題が AC 済みであるかと、どの問題で何回 WA をしたかを管理です。

AC をしたら AC 配列を編集しましょう。 WA をしたら、まずその問題が AC 済みであるかどうかをチェックです。AC 済みであればスルーで、まだ AC をしていなければ WA の数に加算です。

最後に集計です。AC の数はそのままフラグの数を数えればよいです。 WA は注意です。各問題について、AC 済みであるかどうかをチェックしましょう。AC 済みならおとなしくペナルティに加算、残念ながら AC が出来なかった問題については、ペナルティも免除されます。いいですか？ 免罪処理を忘れてはいけませんよ？

✔D - Maze Master（400 点）

最も遠い 2 点の間の距離が答えです。

全点から BFS をしましょう。いいですか？ 壁に埋まった状態からスタートしてはいけませんよ？

✔E - Max-Min Sums（500 点）

min と max をそれぞれ独立に計算しましょう。

max です。同じ値のものが複数あって厄介に見えるのですが、例えば添字との辞書順で順番がついているものとみなせばよくて、記にする必要がないことがわかります。さて、順番がついていると思って、各項について、それが最大になるような部分集合の数を数えればよいです。これは、それよりも小さいものから K - 1 個選べば良いので、この項が小さい方から i 番目のときは binom( i, k - 1 ) 通りあります。

min は同じことを逆から行ったものと同じです。 最後に max - min を出力しておしまいです。

✔F - Enclose All（600 点）

中心としてありえるのは、同一直線上にない 3 点の作る三角形の外心、もしくは 2 点の中点なので、全探索です。 外心は、頂点の位置ベクトルを、sin 2A, sin 2B, sin 2C で重み付き平均を取ったものですから、私はそれで計算しました。

ちなみに解説 PDF では二分探索を用いていました。半径 Rを決め打ちすると、中心になるのはどれか 2 点からの距離が R な場所だとしてよいです。こちらのほうが実行速度は速いです。天才ですね。負けませんよ？

結果

f:id:ngtkana:20200113001131p:plain

229 位 1992 青パフォです。コンテスト中の predictor はもう少し酷かったのですが、終わってみるとそうでもなくて、なんといいますかという気持ちです。

F が遅かったのは、地味に書く量も多かったですし、許容範囲なのですが、ペナルティがひどいです。

許容範囲とは言ったものの、ペナルティがなくて 55:57 で全完できていたとしても、黄色パフォです。この F は青ならば解けて当然、黄色ならば速解きということでしょうか。なかなか厳しい戦いでした。ABC の全完速解きの回は負けがちです。悲しいですね。

ツイッターの様子

A について

あるあるです。

ちなみにこれは integral promotion と呼ばれていて、char 型には operator + がありませんから、int に昇格して計算され、int が返ってきます。（これであっているでしょうか）cppreference のリンクも貼っておきます。

Implicit conversions - cppreference.com

被害者の会です。

C について

無限人発生したようです。

E について

そういえば入力に負数がありました。mod は注意です。

F について

三分探索でできるようです。これならば実行時間も速いです。天才ですね。

興味深いお話です。

たしかに、言われてみればそうかもしれません。ここにさらに乱択も混ぜると無敵です。（悪い顔）

その他

素晴らしい機能です。かがくの ちからって すげー！です。

AC ひとつの裏には、ドラマがあるものです。