ABC
解説AC 問題へのリンク 公式解説 単純に部分列を得るだけなら部分列DPなどが考えられますが、今回はすべての並び替えを得る必要があるので適用できません。 重複を含む並び替えの計算方法から考えてみます。 の選んだ個数をそれぞれとします。この時の並び替…
解説AC 問題へのリンク 公式解説 公式解説のメモ程度です。 の累積和をとおくと、与えられる情報は、 という風になり、 との一方が分かれば、もう一方がわかる という関係になる。 この関係をグラフ化し、とが連結ならYes。 ここまでが公式解説の内容です。 …
コンテスト中AC: A〜D A - Exponential or Quadratic D - AND and SUM 公式解説メモ 連立方程式の解き方 A - Exponential or Quadratic から、が64bit整数型に収まらなければ、直ちにYesです。 よって、64bit型を超えるまでは、実際に2を掛けていきます。そ…
コンテスト中にACしたものの、after_contestでTLEで、嘘解法でした。 この記事は公式解説を自分用にまとめたもので、新たな情報などは無いです。 ここでは、標高が低いところから高いところに行く坂を下り坂、逆を上り坂と言うことにします。 2個目の条件を…
コンテスト中AC:A〜E Eは嘘解法(Cも若干そうでしたが)だったので、ここでは省略します。 C - kasaka D - LR insertion C - kasaka 先頭から連続しているaの個数をhead、末尾から連続しているaの個数をtailとします。 先頭に付け加えるのに必要な個数は、tail…
コンテスト中AC:A〜C D - Dance 状態遷移を伴うDFS 考慮すべき事項 状態の管理に必要な情報 情報の受け渡し方法 値渡し グローバル変数等で共有 終了条件 D - Dance 解けなかったので、反省点含めて記録します。 まず、Nが小さいことから全探索が可能と予想…
自力AC(一度TLEになったので、解法を見て、合っているか確認した) 条件を満たす桁に関する問題 以下の整数全てに関する問題 という条件から、桁DPが有力候補となります。 桁DPに関する情報はネット上に多くあるため、ここでは割愛しますが、大雑把に説明しま…
コンテスト中AC:A〜E C - The Kth Time Query D - Multiply and Rotate E - MST + 1 C - The Kth Time Query 二次元配列を用意し、には、が出現したインデックスを順に記録します。 クエリが与えられた時、まず、のサイズがより小さい場合(出現数が)は、-1を…
問題へのリンク 解説AC 牛ゲーとのことで、解法は公式解説を見るのが良いかと思います。 ここでは、自分なりの理解をつけ足したいと思います。 牛ゲーについては、別記事にまとめました。 geam1113.hatenablog.com また、ネットで調べると色々出てきます。 …
C - Happy New Year! D - Prefix K-th Max E - Arithmetic Number C - Happy New Year! 非負整数の2進数表記の1を2に変換する操作を考えます。操作後の値をとします。すると、以下が言えます。 とは一対一対応する。 非負整数の変換によって、0,2のみからな…
解説AC。大体の解法は自分が想定したものと合っていました。 ここでは、を、頂点iに書かれた整数と表現します。 「i番目とj番目が交換可能」という条件を「頂点iと頂点jに無向辺がある」と言い換えます。 昇順に並び替えるとは、 すべての頂点について、とが…
解説AC お釣りの問題は過去出題例があります。 過去問では、 maspypy.com を参考にしました。 この解説と公式解説を踏まえ、まずは解法を書きます。 例として、 X = 35 A = {1,4,12} を考えます。 を円払うために必要な最小の硬貨の枚数 と定義します。 は、…
コンテスト中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〜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〜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~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〜E D - Between Two Arrays 以下のDPを考えます。 がである整数列の総数 遷移を考えると、のとき、をにできるので、 となります。 これをについて計算していると、 というワーストケースを例として計算量はは超えてくるので、計算量を改善…
解説なし 問題文の読み違えで、全ての要素が以上の部分列を求めると勘違いしており、解けませんでした。 部分列の問題では各が必ず末尾に付くような部分列を考えていくと、重複を避けて数え上げることができます。今回もその方法で解くことができます。 具体…
与えられた木を、頂点1を根とする根付き木とみなします。 辺で結ばれた頂点を考えます。頂点の方が根に近いものとします。 根からDFSをすると、での探索が終了した後にに戻ります。 を根とする部分木について、の子孫についてのが求まっているとします。 か…
