ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

AGC032 D - Rotation Sort

問題 提出コード 解法 シフトという操作が少しわかりづらいのですが、結局は 任意の要素を取り出し、別の任意の位置に挿入する(現時点より左に挿入するならコストは、右であれば) という操作ができることになります。 ので、それぞれの要素を、 右側に移動し…

AGC043 D - Merge Triplets

問題 提出コード 解法 いろいろな数列を試していると、4つ以上の連続する区間が単調減少することはありません。 この原因を考えてみると、長さ3の数列を作成しているため、4つ単調減少させようとすると、1つの長さ3の数列 + どこか1か所別の値が選ばれる必要…

ARC082 F - Sandglass

問題 提出コード 解法 クエリが時間順で並んでいるので、時刻を進めながらクエリに答えていくことを目指します。 時刻のクエリに答えるには、となるようなの中で最大の時刻まで時を進めて砂の量を調べ、最後にひっくり返す部分だけシミュレートすれば良いで…

Typical DP Contest I - イウィ

問題 提出コード 解法 操作をいろいろ試してみると、一連の操作で消すことができる部分というのは区間になっていることがわかります。 の区間の文字全てを消すことができるかどうか という区間DPを考えます。が3の倍数でない時はもちろんNOです。 を全て消去…

CODE FESTIVAL 2017 qual C D - Yet Another Palindrome Partitioning

問題 提出コード 解法 が回文になる条件は、a ~ zについて、に含まれる個数が全て偶数になる、もしくはどれか1つのみが奇数になる、のどちらかです。 a, b, ..., zとします。 先頭の文字から番目の文字までを見て、奇数個になる文字について、を計算したもの…

ARC099 E - Independence

問題 提出コード 解法 頂点との間に辺が張られていない場合、これらを同じ州に含めることができません。 これは全ての張られていない辺について成り立ちます。逆に、同じ州に含めることができない頂点対に辺を張ったグラフを考えると(これは与えられるグラフ…

AGC029 D - Grid game

問題 提出コード 解法 高橋君が動かない、という操作を選択した場合、青木君は動かない、という操作を行ってゲームを終了させればよいので、高橋君が駒を動かさない、という選択肢は存在しません。 よって、高橋君が動けなくなるように青木君がうまく動けば…

AGC029 C - Lexicographic constraints

問題 提出コード 解法 種類以下で問題の条件を満たすような文字列たちを作成できるか?という問題を考えると、ある境界が存在し、それ以下では作成不可能、それ以上では作成可能になります。よって、あるについて問題の条件を満たすかどうか、を見ながら二分…

Typical DP Contest G - 辞書順

問題 提出コード 解法 まず、 文字目の次にという文字が現れるインデックスの最小値 を計算します。 これは、という更新を行えばよいです。 さて、 文字目を先頭で使った際にできる、部分文字列の種類数 というDPを考えます。 文字目を使った際に考えられる…

AGC009 C - Division into Two

問題 提出コード 解法 集合を、集合0、集合1とし、をとします。 番目の要素まで見て、番目の要素を集合に入れるような振り分け方のパターン数 を数えます。 という区間が集合に入り、その前後はもう片方の集合に振り分けられるパターンを考えます。このよう…

オイラーツアー、HLD解いた問題まとめ

提出場所見失いそうなので個人用まとめです もう少し解法の中身っぽいところを後で加えたいです(加えてください) HLD オイラーツアー 頂点 辺 HLD Submission #12187038 - 2010年 日本情報オリンピック春合宿OJ Aizu Online Judge Submission #12180953 - At…

Waseda Orientation Programming Contest 2020 J - トレジャーハンター

問題概要 解法 Med Large 1つめ:01ナップサックに帰着 2つめ:個数制限なしナップサック 3つめ:ダイクストラ法 おまけ(Med解以外の想定TLE,MLE解法) コード 問題概要 種類のはしごがあり、番目のはしごの長さはです。 以上以下の値で、以下の条件を満たさない…

AOJ 2335 - 10歳の動的計画

問題 提出コード 解法 縦方向が、横方向がとします(多分問題と逆…?) 移動は必ず全体で回になります。 縦に回、横に回寄り道すると決めた時、上記の移動のうち、縦方向に移動するのが回、横方向が回になるので、先にその方向を決め打つと、 通りになります。…

AOJ 2293 - Dangerous Tower

問題 提出コード 解法 全て含めて、横の長さと箱が1:1に対応します。 なので、横の長さと箱をマッチングさせていくことを考えます。 箱について、 とマッチングさせる とマッチングさせる マッチングさせない という3つの選択肢が存在します。 それぞれの場…

AOJ 2443 Reverse Sort

問題 提出コード 解法 いろいろ嘘枝刈りBFSぽいことを考えましたが、全く解けませんでした… AOJ 2443. ReverseSort - うさぎ小屋 ↑こちらを参考にしました。 前から貪欲に揃えていくと、確実に回以内で揃える事ができます。 操作回数が増えると、たどり着け…

ABC166 E - This Message Will Self-Destruct in 5s

問題 提出コード 解法 もちろん、ペアを全探索することは難しいです。 ペアとしてカウントされる条件を詳しく見ていきます。 としたとき、カウントされる条件は、 となります。 これを式変形すると... となります。 より小さくて、とペアになれるの個数は、…

AOJ 2611 - 順位付け

問題 提出コード 解法 木の2乗DPとかなんとか言われてるやつです。 問題文をじっくり読むと、入力が木になっていて、そのなかで順位付けをしていくことがわかります。木全体の根は、入力時点で一番高さが高かった頂点です。 木の高さがすべて異なる場合は簡…

ABC164 D - Multiple of 2019

問題 提出コード 解法 ここでは、について下から桁目の数字をと表記します。また、の文字列の長さ、すなわちをとします。 加えて、をで割った余りをと表記します。 まず、について、桁ごとに分解して表現してみると、 となります。 は、次のように書くことも…

MIS.W新歓コンテスト2020

自分の大学にあるサークルが主催するコンテストに参加しました。 自分のコードはまとめてここに上げてあります。問題の前から順番にa,b,...と振ってあります。自分のコードを動かすことができるeの入力データも添えました。 長いのでかなり端折る部分があり…

AOJ 2828 - マトリョーシカ

問題 提出コード 解説ACです。マッチング、難しいですね… 解法 元の問題について、体積の最小値ではなく、見えているマトリョーシカの個数を求める問題は、 最小パス被覆問題そのものになっています。これは二部グラフの最大マッチングに帰着させることがで…

AOJ 2703 - サイコロスタンプ

問題 提出コード 解法 あらかじめ、番目のサイコロが転がった結果記される数字と座標のペアリストを作成しておきます。 サイコロの集合について、これらを最適な順番で転がした際に得ることができる得点の最大値 とすると、答えはです。 の求め方について考…

ABC160 F - Distributing Integers

問題 提出コード 解法 のみの場合について答えることができればあとはうまく伝播させて全方位木DPにしてしまえばよいので、の場合を考えます。 を根とする部分木についての、数字の配置パターン数 を根とする部分木の頂点数 とします。の計算方法については…

Educational Codeforces Round 48 (Rated for Div. 2) D. Vasya And The Matrix

問題 提出コード 問題概要 要素の数列と、要素の数列が与えられます。 行列の行列で、それぞれの行について、全要素のxorをとるとに、それぞれの列について全要素のxorをとるとになるようなものが存在するならば1つ求めてください。 解法 行う操作がxorなの…

構築問題 メモ

構築の思考パターンメモです。主にはまやんさんの構築まとめに載っている問題をを埋めていきます。 www.hamayanhamayan.com 2べきを考える +1および×2の遷移を作成して任意の値を構築 その他 ARC102 D - All Your Paths are Different Lengths 特徴のあるグ…

JOI2017/2018 予選 D - 水ようかん (Mizuyokan)

問題 提出コード 解法 番目までのようかんを切り終えて、ピースの最小値がになるように切り分けたときに取り得る"ピースの最大値"の最小値 とします。こうすることで、答えはで求めることができます。 すると、でピースを作成すると仮定した際に遷移がどうな…

AOJ 2312 - 魔法少女さやかちゃん

問題 提出コード 解法 添え字は0-indexedとします。 区間の総和は、BITや累積和を用いて高速に取得できるものとします。 とします。 仮に円環でなく直線上に音符を配置しているとした場合、明らかに音符をの昇順に配置するのが最適です。 しかし今回は、音符…

AOJ 2826 - ゲームバランス

問題文 提出コード 解法 倒すまでに最小回以上かかるなかで最大となるを二分探索で求めます。 ゲームクリアできない場合、になります。二分探索時は、ゲームクリアまでに回以上かかっている、と仮定します(最後に求まったを確認した場合にゲームクリアできな…

AOJ 2966 - G トレジャーハンター (Treasure Hunter)

問題文 提出コード 解法 解説の通りこちらを参考にして通しました。 再帰でDFSをしながらナップサックを解き、戻り値として、今いる頂点を使用した際の最適解配列と、使用しなかった際の最適解配列を返します。 今いる頂点をとします。子をとします。 1つめ…

AOJ 2965 - F グリッドの番号

問題 提出コード 解法 小さい順に数字を当てはめていくとき、上段の右端に配置するか、下段の右端に配置するかの二択になることを利用します。 番目までの数字を入れ終えて、上段に配置した個数が個かつ、直近手の上下の配置情報がのときの配置の通り数 とし…

Good Bye 2015 D. New Year and Ancient Prophecy

問題 提出コード の文字列を一つの年として見た時の、の組み合わせの個数 とします。 の文字列を使用した、と言うことは、次に選ぶがより真に大きい値になる必要があります。 条件は以下の二つで、どちらか片方を満たせばよいです。 これは、桁がそもそも大…