問題 提出コード 解法 クエリが時間順で並んでいるので、時刻を進めながらクエリに答えていくことを目指します。 時刻のクエリに答えるには、となるようなの中で最大の時刻まで時を進めて砂の量を調べ、最後にひっくり返す部分だけシミュレートすれば良いで…
問題 提出コード 解法 操作をいろいろ試してみると、一連の操作で消すことができる部分というのは区間になっていることがわかります。 の区間の文字全てを消すことができるかどうか という区間DPを考えます。が3の倍数でない時はもちろんNOです。 を全て消去…
問題 提出コード 解法 が回文になる条件は、a ~ zについて、に含まれる個数が全て偶数になる、もしくはどれか1つのみが奇数になる、のどちらかです。 a, b, ..., zとします。 先頭の文字から番目の文字までを見て、奇数個になる文字について、を計算したもの…
問題 提出コード 解法 頂点との間に辺が張られていない場合、これらを同じ州に含めることができません。 これは全ての張られていない辺について成り立ちます。逆に、同じ州に含めることができない頂点対に辺を張ったグラフを考えると(これは与えられるグラフ…
問題 提出コード 解法 高橋君が動かない、という操作を選択した場合、青木君は動かない、という操作を行ってゲームを終了させればよいので、高橋君が駒を動かさない、という選択肢は存在しません。 よって、高橋君が動けなくなるように青木君がうまく動けば…
問題 提出コード 解法 種類以下で問題の条件を満たすような文字列たちを作成できるか？という問題を考えると、ある境界が存在し、それ以下では作成不可能、それ以上では作成可能になります。よって、あるについて問題の条件を満たすかどうか、を見ながら二分…
問題 提出コード 解法 まず、 文字目の次にという文字が現れるインデックスの最小値 を計算します。 これは、という更新を行えばよいです。 さて、 文字目を先頭で使った際にできる、部分文字列の種類数 というDPを考えます。 文字目を使った際に考えられる…
問題 提出コード 解法 集合を、集合0、集合1とし、をとします。 番目の要素まで見て、番目の要素を集合に入れるような振り分け方のパターン数 を数えます。 という区間が集合に入り、その前後はもう片方の集合に振り分けられるパターンを考えます。このよう…
提出場所見失いそうなので個人用まとめです もう少し解法の中身っぽいところを後で加えたいです(加えてください) HLD オイラーツアー 頂点 辺 HLD Submission #12187038 - 2010年 日本情報オリンピック春合宿OJ Aizu Online Judge Submission #12180953 - At…
問題概要 解法 Med Large 1つめ:01ナップサックに帰着 2つめ:個数制限なしナップサック 3つめ:ダイクストラ法 おまけ(Med解以外の想定TLE,MLE解法) コード 問題概要 種類のはしごがあり、番目のはしごの長さはです。 以上以下の値で、以下の条件を満たさない…
問題 提出コード 解法 縦方向が、横方向がとします(多分問題と逆…？) 移動は必ず全体で回になります。 縦に回、横に回寄り道すると決めた時、上記の移動のうち、縦方向に移動するのが回、横方向が回になるので、先にその方向を決め打つと、 通りになります。…
問題 提出コード 解法 全て含めて、横の長さと箱が1:1に対応します。 なので、横の長さと箱をマッチングさせていくことを考えます。 箱について、 とマッチングさせる とマッチングさせる マッチングさせない という3つの選択肢が存在します。 それぞれの場…
問題 提出コード 解法 いろいろ嘘枝刈りBFSぽいことを考えましたが、全く解けませんでした… AOJ 2443. ReverseSort - うさぎ小屋 ↑こちらを参考にしました。 前から貪欲に揃えていくと、確実に回以内で揃える事ができます。 操作回数が増えると、たどり着け…
問題 提出コード 解法 もちろん、ペアを全探索することは難しいです。 ペアとしてカウントされる条件を詳しく見ていきます。 としたとき、カウントされる条件は、 となります。 これを式変形すると... となります。 より小さくて、とペアになれるの個数は、…
問題 提出コード 解法 木の2乗DPとかなんとか言われてるやつです。 問題文をじっくり読むと、入力が木になっていて、そのなかで順位付けをしていくことがわかります。木全体の根は、入力時点で一番高さが高かった頂点です。 木の高さがすべて異なる場合は簡…
問題 提出コード 解法 ここでは、について下から桁目の数字をと表記します。また、の文字列の長さ、すなわちをとします。 加えて、をで割った余りをと表記します。 まず、について、桁ごとに分解して表現してみると、 となります。 は、次のように書くことも…
自分の大学にあるサークルが主催するコンテストに参加しました。 自分のコードはまとめてここに上げてあります。問題の前から順番にa,b,...と振ってあります。自分のコードを動かすことができるeの入力データも添えました。 長いのでかなり端折る部分があり…
問題 提出コード 解説ACです。マッチング、難しいですね… 解法 元の問題について、体積の最小値ではなく、見えているマトリョーシカの個数を求める問題は、 最小パス被覆問題そのものになっています。これは二部グラフの最大マッチングに帰着させることがで…
問題 提出コード 解法 あらかじめ、番目のサイコロが転がった結果記される数字と座標のペアリストを作成しておきます。 サイコロの集合について、これらを最適な順番で転がした際に得ることができる得点の最大値 とすると、答えはです。 の求め方について考…
問題 提出コード 解法 のみの場合について答えることができればあとはうまく伝播させて全方位木DPにしてしまえばよいので、の場合を考えます。 を根とする部分木についての、数字の配置パターン数 を根とする部分木の頂点数 とします。の計算方法については…
問題 提出コード 問題概要 要素の数列と、要素の数列が与えられます。 行列の行列で、それぞれの行について、全要素のxorをとるとに、それぞれの列について全要素のxorをとるとになるようなものが存在するならば1つ求めてください。 解法 行う操作がxorなの…
構築の思考パターンメモです。主にはまやんさんの構築まとめに載っている問題をを埋めていきます。 www.hamayanhamayan.com 2べきを考える +1および×2の遷移を作成して任意の値を構築 その他 ARC102 D - All Your Paths are Different Lengths 特徴のあるグ…
問題 提出コード 解法 番目までのようかんを切り終えて、ピースの最小値がになるように切り分けたときに取り得る"ピースの最大値"の最小値 とします。こうすることで、答えはで求めることができます。 すると、でピースを作成すると仮定した際に遷移がどうな…
問題 提出コード 解法 添え字は0-indexedとします。 区間の総和は、BITや累積和を用いて高速に取得できるものとします。 とします。 仮に円環でなく直線上に音符を配置しているとした場合、明らかに音符をの昇順に配置するのが最適です。 しかし今回は、音符…
問題文 提出コード 解法 倒すまでに最小回以上かかるなかで最大となるを二分探索で求めます。 ゲームクリアできない場合、になります。二分探索時は、ゲームクリアまでに回以上かかっている、と仮定します(最後に求まったを確認した場合にゲームクリアできな…
問題文 提出コード 解法 解説の通りこちらを参考にして通しました。 再帰でDFSをしながらナップサックを解き、戻り値として、今いる頂点を使用した際の最適解配列と、使用しなかった際の最適解配列を返します。 今いる頂点をとします。子をとします。 1つめ…
問題 提出コード 解法 小さい順に数字を当てはめていくとき、上段の右端に配置するか、下段の右端に配置するかの二択になることを利用します。 番目までの数字を入れ終えて、上段に配置した個数が個かつ、直近手の上下の配置情報がのときの配置の通り数 とし…
問題 提出コード の文字列を一つの年として見た時の、の組み合わせの個数 とします。 の文字列を使用した、と言うことは、次に選ぶがより真に大きい値になる必要があります。 条件は以下の二つで、どちらか片方を満たせばよいです。 これは、桁がそもそも大…
リンク 問題文 解法 1段ずつ下からブロックを積んでいくことを考えます。 ある段のある区間にブロックを積んだら、それ以降はその積んだ区間に対してのみ積んでいくかどうかを考えます。 今区間の幅が残りで、ブロックの残り個数が個の際の、そこからの構築…
リンク 問題文 解法 これの類題です。 文字目までの文字列を完成させるのに最小となる連続部分列の個数 とします。すると、この配列は広義単調増加になっているはずなので、 は、文字目を右端とするようなの部分文字列の中で最長の長さをとしたとき、となり…
