キャディプログラミングコンテスト2021(AtCoder Beginner Contest 193)

悔しい。本当に悔しいです。コンテスト終了した2分後にD問題提出してACでした。今回のD問題は計算量大したことなさそうだから愚直に全パターン列挙すれば絶対に解ける!という確信があったので、絶対取りきるべき問題でした。もっと強くなりたいです。精神面技術面ともに。あまりにも悔しいのでこの記事を書いています。

以下、A~D問題の感想です。

A - Discount

特に何も言うことはないですね…print((A-B)*100/A)で通しました。

B - Play Snuke

この問題はちょっと実装ミスってて少し時間食いました。方針としては、各お店に対して(x-1)//aで高橋くんがお店に到着した際の在庫の有無判定して、在庫有りなら値段が最安かどうかの判定をして結果一番安かった値段が答え、というもので解きました。

C - Unexpressed

今回のでっかい反省点がこいつですね。まず純粋な実装の方針に関しては、以下ステップでやりました。

ステップ1：$x^2$がN以上となる最小の$x$を求める。
ステップ2：$i$ in range(2,$x$)でforループを回し、その中で各$i$に対してwhileループで$i^2$、$i^3$、…とべき乗数を増やしていき、各値がN以下だったらカウントする。Nを越えた時点でbreak。
ステップ3：Nから、ステップ2でカウントした数を引いたものが答え。

なのですが…何故かサンプルケース2だと、答えより微妙に小さい値が出力される。なんで？うーんうーんと唸りながら各$i^p$を出力しつつ考えること15分…

ステップ2で重複してカウントしとるやんけ!!!!(例：$2^4=16$と$4^2=16$を別々でカウント)

慌ててステップ2を修正し、setを使ってN以下の$a^b$と表せる数をリストアップしてようやく正しい答えに。よっしゃ提出や!!

デバッグ用の出力消し忘れてた…

くそがああああああああ よっしゃこれでどうや!!

デバッグ用の出力(その2)消し忘れてた…　あぁぁぁぁぁああぁぁぁぁあぁあぁ


正しい出力形式になっているかチェックしてからでないとコード提出してはいけない(戒め)

D - Poker

問題文を読んで正しく解釈するのに時間使いましたが、やるべきことは大体見えてきたので実装を進めながら、都度修正を繰り返しました。結果的にはちょっと問題を読み替えて以下ステップで解きました。

ステップ1：S、Tそれぞれで表になってる4枚のカードの合計点を求めておく。また、4枚のカードが高橋くん、青木くんにそれぞれ配られた後に1~9のカードがそれぞれ何枚残っているかを求めておく(S、Tの5枚目のカードとして考えられるパターンの計算用)。
ステップ2：ステップ1で算出したS、Tの5枚目のカード候補のうち、考えられるペアをlist(itertools.permutations(「S、Tの5枚目カード候補のリスト」,2))で算出する(5枚目カード候補のリストは、[1,1,3,3,4,4,5,6,6,7,8,8,9,9]のようなイメージ。※このリストでは、1~9の各数字が仮に2枚以上残っている場合でも2枚だけ残っているものと見做した。2枚以上リストに加えても順列の総パターン数には影響しないため。)。
ステップ3：ステップ2で求めた各カードのペア(高橋くんの5枚目=数字a,青木くんの5枚目=数字b)それぞれについて、ステップ1で求めた二人の得点を修正した後に高橋くんが勝っているケースが何通りあるかを求める。何通りあるかは各カードペアについて、5枚目のカードを配る際に「数字aが何枚残ってたか」×「数字bが何枚残ってたか」で計算できるので、それらを合計していく。
ステップ4：「ステップ3で数え上げた合計」を分子に、「ステップ1で求めた5枚目候補のカード枚数」×「5枚目候補のカード枚数-1」を分母にして確率計算したらそれが答え。

うぅ…もっと落ち着いて解き進められれば…精進します。3月末まで仕事忙しそうで時間取れるか微妙だけど…

以上です。