解説AC お釣りの問題は過去出題例があります。 過去問では、 maspypy.com を参考にしました。 この解説と公式解説を踏まえ、まずは解法を書きます。 例として、 X = 35 A = {1,4,12} を考えます。 を円払うために必要な最小の硬貨の枚数 と定義します。 は、…

コンテスト中AC:A,B A - Permutation Grid B - Shift and Reverse A - Permutation Grid nの制約上、実際に構築することはできません。 このことから、の組みによって一意に定まるような法則性がありそうだと予測します。 白黒がどのように決定するか試して…

コンテスト中AC:A〜E C - Product D - Count Interval E - Σ[k=0..10^100]floor(X／10^k) C - Product ボールの数の総積がを超えないので、各袋からボールを1つ選んだ時の全組み合わせもを超えません。よって、得られる全ての積を配列に保存できます。 部分…

コンテスト中AC:A〜E C - Graph Isomorphism D - Weak Takahashi E - Rook Path C - Graph Isomorphism 順列全探索の問題です。 Pのあり得る組み合わせは最大で8!通りで、順列全探索で十分間に合います。 逆にNが8くらいまでなら順列全探索を疑うと良いかも…

コンテスト中AC:A〜D コンテスト後にFを自力ACしました。 D - Neighbors F - Jealous Two 自分の解法 公式解法 ユーザ解説(Wavelet Matrix) D - Neighbors 問題文の条件は簡単ですが、判定法に抜けなどがあり、WAをたくさん出しました。 問題文の条件を満た…

解説AC ABCのこの問題のように類題は出題されています。しかし、このように逆に構成できることは思いつきませんでした。 右からi桁目までを10進数の整数としたとき、なる区間(j,i]を10進数としたものが7の倍数となる条件は、 を満たすことです。なお、10と7…

解説を見てAC 公式解説に詳しく書かれていますが、自分用にメモしておきます。 勝敗の決定 ・Nが奇数なら先手必勝 ・Nが偶数なら、1個取って0にできれば先手必勝、そうでなければ後手必勝 1個取って0になることの判定法 公式解説と少し違いますが、この方が…

コンテスト中AC:A,B A - Two Lucky Numbers B - Grid Repainting 4 A - Two Lucky Numbers 整数xの文字列表現をstr(x)とします。また、str(x)+str(y)は文字列の連結を表すこととします。 基本的にはstr(B/2)とstr(A)を連結させる方針となります。 しかし、B…

コンテスト中AC:A〜DEを解説ありで解きました。 A - AtCoder Quiz 3 B - Triple Metre C - X drawing D - Destroyer Takahashi E - Fraction Floor Sum A - AtCoder Quiz 3 公式解説より、setfillとsetwでleading zerosを実現できるらしいです。 B - Triple …

自力AC 全ての積をとるのは巨大過ぎて不可能です。 であり、また、約数の個数は素因数分解して、 となった時、 として求められます。 以上から、1つの方法として、 ・分母分子の個々の整数を素因数分解して、素因数の個数をカウントする ・分子の素因数の個…

コンテスト中AC:A,B A - Remove One Charcter B - Colorful Lines A - Remove One Charcter 同一文字が連続する領域から、i文字目とj文字目取り除いてを作る ことと、 が等しい ことは必要十分条件です。 必要性は明らかです。 十分性を示します。 の取り除…