ABC193の感想
キャディプログラミングコンテスト2021(AtCoder Beginner Contest 193)にバーチャル参加（後日参加）しましたのでその感想を書いていきます。
問題はこちらから。
結果はこんな感じでした。
4完（1wa）
時間：69 : 16(+5分を含む)
パフォーマンス（推定）：1150ぐらい
バーチャル参加なので色々と推定です。アルゴリズムというよりかは数学の比重が大きかったかなと思います。今回は、「キャディ」様の企業コンテストでしたので、企業の特色が問題に反映されているんですかね。知りませんが。計算量の見積もり然り、確率の扱い然り、アルゴリズムのライブラリをぺたって貼る問題よりも考慮すべき点が多くて疲れました。でもこういう問題は難しいですが、とても好きです。楽しかったです。
ではいきます。
A問題
値引き率を求める問題です。就職活動のSPI試験でこんな問題よく見ました。落ち着いて考えれば簡単なのですが、時間に追われていると一気に頭がこんがらがりますね。ややこしいといいますか。結構苦手な問題です。
(1 - (b/a)) * 100
です。doubleで計算することと答えは百分率で答えることに注意です。
B問題
人気商品を買いに行く問題です。人気なので時間が経つたびにどんどん売り切れてしまいます。近くて在庫が多くて安いお店があればいいのですが、そうもいきません。近くて在庫が少ない。在庫が多いけど遠い。近くて在庫も多いけど高い。いい感じのお店を探します。
まず、帰るかの判定をしたのち、そのなかで最安値を出力すればACでした。
C問題
a^bで表現できないn以下の数の個数を求めます。
はじめ n 以下の素数を列挙してその組み合わせから数を絞ろうかと考えました。ただ、めんどくさいなーと思っていったんストップ。
制約は10^10と大きいですが、約数とか素数とかって大抵√nまで考えればよいことが多いので、ここで愚直解法がちらつきました。ai = i として 各aiにかかる計算回数を考えると、ai = 2で 2 ^ 34 = 1.7 * 10^10ということで、どんなに多くても17回です。
ここまで考えて愚直解法をスタートさせました。ただし、intで計算して1wa本当に学びません。
D問題
高橋君が勝つ確率を求めます。
この問題は比較的スムーズに答えの解法にたどり着けました。コンテスト中はこんな感じで考えました。
必要なもの
高橋君が i を引く確率
青木君が j を引く確率
スコアの計算関数
高橋君がもってるカードの内訳
青木君がもってるカードの内訳
残りのカード枚数（カード i、j は残っているか）
流れ
それぞれ、i,jを引く（カードが残っていなければ無視、同じカードを引くときに注意）
スコア計算
勝敗判定
確率計算
ansに足す
あとは、これをプログラムに起こしました。ただ、実装でそこそこバグを発生させて焦りました。特に配列をグローバルに宣言するか、ローカルに宣言するか、参照で渡すかなど、今になってもなんだかなーって思っています。
あとは、精度が怖かったので、与式を一部括ってあげて最後に掛けようかなって考えましたが、まあいいか、でそのままかきました。サンプルを見るに精度に余裕がありましたので一安心、、、でした。
E問題
乗り過ごさないかを判定します。
最近のABCのE問題はグラフ問題といいますか、経路問題といいますかアルゴリズム色が強かったので、本問題を見たときちょっとびっくりしましたが、考えていてすごく楽しかったです。
解けなかったし、まだ解答を見ていないのでどうすればよいのかはわかってませんが、愚直にやったらだめですよね。そもそも終了判定（Bで降りられないときの判定）が良くわかりません。
x, y と p, qの数直線を書くと、だいぶ問題がみえてきました。この区間の共通部分を探せばいいんだなと。ということは、pとqのいい感じの値の2x + 2yの剰余を考えてあげて、それがなんかいい感じに[x,y)に入ってくれればよさそうと考えました。ただ、制約を見るに2x+2y<=2*10^9 + 1000です。この範囲の剰余を監視するのも大変そうだなと思い断念。どうすればよいのでしょうか。解説をみて勉強します。
F問題
見てないです。
この記事が気に入ったらサポートをしてみませんか？