コンテスト中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があわず、公式解説とユーザー解説を確認し、多角形は穴があってはいけないことがわかりました。 そこ…
コンテスト中AC:A 難しかったです。辛うじてAだけ解けました。 A - Make 10 本番でも自身の解法に確証がなかったので、公式解説を参照したほうがよいかもしれません。 使う数字をできるだけ少なくするようにする貪欲法を考えます。使う数字が少なければ、そ…
コンテスト中AC:A〜C 戦績が良くなかったので、コンテスト後に解けたDだけ書きます。 D - Strange Lunchbox 購入したお弁当の個数の情報と、その時のたこ焼き及びたい焼きの個数の情報が欲しいので、以下のDPを考えます。 種類目までのお弁当のうち個のお弁…
解説なし 辺の距離が全て1なので、最短距離、最短パスはBFSで求まります。 BFSはなので、すべての辺が通れないときを計算すると、で間に合いません。 元のグラフの最短距離が変化するのは、最短パス上の辺が通れなくなった場合だけです。したがって、このと…
2022/03/25 Eに追記 コンテスト中AC:A〜E C - Shapes D - Rectangles E - Destruction C - Shapes 難しかったです。 以下の2点を解決する必要があります。 90°回転の実装 平行移動の方法 90°回転は回転行列で解決しました。なお、全てのマスはxy座標上の点と…
前に解説読んでよくわからなかったので寝かしていましたが、今回やってみたら解けました。 まず、以下に頻出の考え方について説明します。 ある整数列のを末尾とする連続した部分列の要素の和がの倍数となるような、全てのを求めることを考えます。 とすると…
コンテスト中AC:A〜E D - Cutting Woods 結合している座標情報を管理する場合、操作列を逆順にしてUnion-Findで結合していくなどが考えられます。しかし、なので、全ての座標を保持することはできません。 そこで、切られた座標を管理することを考えます。 …
解説を見て解きました。 問題文の条件は、同じ色を連続して全て取ってから次の色を取るということを示します。 入力例1なら、32123の順で並んでいるボールを12233の順で取ります。同じ数字内での取り方に指定はありません。 ある色のボールを全て取ることを…
コンテスト中AC：A, B, C, D C - Many Balls 操作を逆順に考えるのは典型です。Nから始めて0にすることを考えると、魔法Aは-1、魔法Bは÷2することになります。 すると、奇数なら魔法Aしかできず、偶数なら魔法Bを使用する方が0に近づけます。 奇数ならA、偶…
コンテスト中AC:A A - Dial Up に1しかないのにに1がある場合、-1です。0の場合も同様です。以下、そうでない時を考えます。 を円環とみなしたとき、と異なる数のうち最も近い位置と、との距離をとします。 への追加操作は明らかに回必要であるため、以下で…
B - log2(N) GCCの組み込み関数__builtin_clzllを使うと、 __builtin_clzll(1LL) - __builtin_clzll(N) で求められます。 提出コード：https://atcoder.jp/contests/abc215/submissions/25200114 C - One More aab aba baa 文字列の並び替えの総数は最大でも…
