2021-01-01から1年間の記事一覧
解説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文字目取り除いてを作る ことと、 が等しい ことは必要十分条件です。 必要性は明らかです。 十分性を示します。 の取り除…
コンテスト中AC:A〜E D - Longest X E - Graph Destruction D - Longest X 連続させたい個数をm個に固定すると、S連続する部分列のうち、m個の要素を含むものについて、いずれか1つでも全てXにできれば、連続m個を達成できます。 必要な操作回数は、部分列に…
問題 Baby-step giant-stepによる解法とWeb公式解説の理解メモ 公式解説の理解 をで割って良い理由 の時に解なしになる理由 Baby-step giant-stepによる解法 公式解説の理解 公式解説 をで割って良い理由 とします。 を変形し、 とします。 はの倍数となる必…
コンテスト中AC:A,B A - Smaller XOR B - Range Point Distance A - Smaller XOR 以下、整数は2進数で表現するものとします。 N = 10101としてシミュレートしてみます。 (1) xの4ビット以降に1がある場合 例えば、x = 100000とすると、 100000 XOR 010101 = …
コンテスト中AC:A~D E問題も解いたので記載しておきます。 B - Takahashi's Secret C - Final Day D - Linear Probing E - Integer Sequence Fair B - Takahashi's Secret に有向辺がある有向グラフとみなすと、これは、 ・閉路がただ一つ存在する ・全ての…
コンテスト中AC:A,B コンテスト後に自力AC:C,D,G B - KEYENCE building C - ABC conjecture D - Project Planning G - Divisors of Binomial Coefficient B - KEYENCE building a*bの積の部分を考えると、a,bは1〜1000までの組み合わせとなり、N=20を考慮し…
注:解説は独自のものなので、誤った部分がある可能性があります。 コンテスト中はしっかりと証明はできず、実際に書いてみて法則を探しました。証明ができていないと、考慮できていないケースなどが存在する場合が多々あるので、証明できるようにしたいとこ…
コンテスト中AC:A〜E こちらの解説は独自の見解であり、間違った情報を含む場合があるのでご注意ください。 B - Counting Arrays 公式解説の方法をC++のstringで実装したところTLEしました。色々な処理が必要な場合、stringはかなり遅いようです。 第一選択…
はじめに 離散対数問題についての問題がAtCoder Beginner Contestで出題され、色々と調べてみたので、その内容をメモします。 離散対数問題 を満たす最小の整数kを求める問題です。 これを求めるアルゴリズムにBaby-step giant-stepがあります。 Baby-step G…
解説なしAC はレプユニット数という呼ばれ、その一般項はなので、この問題の一般項はです。 2や9を無視できれば、を求める問題になり、フェルマーの小定理などで解けそうという感じなので、2と9をどうにかします。 とします。 Kに2を含む場合 XがKの倍数であ…
コンテスト中AC:A〜D C - Calendar Validator 以下の3条件を満たす必要があります。 ・最後の行を除くすべての数について、自分の下の数が、自分の数+7 ・最後の列を除くすべての数について、自分の右隣の数が、自分の数+1 ・すべての行について、要素の数を…
コンテスト中AC:A〜D C - Triangles? で全探索可能です。 面積が正でない三角形は、面積が0の三角形です。 言い換えると、直線上に3点が並んでいる時、面積は0になります。 3点が直線上にある時、線分の傾きが同じになるので、 三角形の面積が0でない時、 が…
コンテスト中AC:A〜D C - Doukasen アルゴリズムとしては、 左端と右端の導火線のうち、燃え尽きる時間が早い方を燃え尽きさせ、そのかかった時間分、もう一方の導火線を短くすることを繰り返す。その際、左から進んだ距離を合計しておく。最後に、導火線が…
コンテスト中AC:A,B A - Gold and Silver を折線グラフで考えたとき、下に凸な頂点で金に交換、上に凸な頂点で銀に交換し、それ以外では何もしないのが最適です。 始点と終点は例外なので、のとき、以下のようにします。 1.金を持っているとき なら、まだ上…
コンテスト中AC:A〜E D - Between Two Arrays 以下のDPを考えます。 がである整数列の総数 遷移を考えると、のとき、をにできるので、 となります。 これをについて計算していると、 というワーストケースを例として計算量はは超えてくるので、計算量を改善…
解説なし 問題文の読み違えで、全ての要素が以上の部分列を求めると勘違いしており、解けませんでした。 部分列の問題では各が必ず末尾に付くような部分列を考えていくと、重複を避けて数え上げることができます。今回もその方法で解くことができます。 具体…
与えられた木を、頂点1を根とする根付き木とみなします。 辺で結ばれた頂点を考えます。頂点の方が根に近いものとします。 根からDFSをすると、での探索が終了した後にに戻ります。 を根とする部分木について、の子孫についてのが求まっているとします。 か…
コンテスト中AC:A〜D D - Online Games の制約が小さければ、以下のimos法で解けます。 ・人目について、配列のに+1、に-1する。 ・最後に、を2から最大日数まで順に+=する ・日目のログイン数は人である。 今回制約が大きいので配列保持することはできませ…
コンテスト中AC:A,B,D C - Long Sequence の合計をとすると、は個のとの番目の要素までの和で構成されているはずです。すなわち、 です。 は、を満たす最小の整数で、は順番に足していけば求まります。 コンテスト中にACできなかったのですが、実装に問題が…
解説ありで解きました。 メモ コンテスト中はDFSや全探索など実装方針がたたず、解けませんでした。 コンテスト後にbit全探索で解いてみましたが、入力例1があわず、公式解説とユーザー解説を確認し、多角形は穴があってはいけないことがわかりました。 そこ…
