ツバサの備忘録

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

ABC130 E - Common Subsequence

問題 提出コード 解法 LCSや編集距離に近いものを感じたので、似たような遷移のDPを考えていきます。 までを見終えた段階でできる、問題の条件を満たす整数列の個数 とします。 初期値としては、です。いずれのパターンでも、共に1つも選ばない1通りの整数列…

ABC130 D - Enough Array

問題 提出コード 解法 を0-indexed( ~ ) で考えていきます。 ある区間についてのの総和が以上となっているとき、を満たす区間については全て部分列の総和が以上となります。 ということで、それぞれのについて、を満たすの最小値を求め、の総和を求めれば答…

ABC130 C - Rectangle Cutting

問題 提出コード 解法 2つに分かれる長方形の面積の差を縮めることを考えると、長方形の面積をちょうど半分に分けるような直線を引くのが最適になります。 与えられている点と、長方形の中心(対角線の交点)を通るような直線を引くと、面積を半分に分けること…

ABC129 E - Sum Equals Xor

問題 提出コード 解法 制約を見ると明らかに桁DPのような匂いがするので桁DPをしました。 の上から桁目をとします。 となるが存在した場合、をすると繰り上がりが発生するので、となります。逆に、それ以外のはどれを使用してても問題の条件を満たします。 …

ABC129 D - Lamp

問題 提出コード 解法 が間に合うので、に設置した際に照らすことができるマスの個数がで求まれば、全探索をしつつ最大値を求めることでこの問題に答えることができます。 ということで、前計算をします。 まず、縦に伸びる光と横に伸びる光は無関係のため、…

ABC129 C - Typical Stairs

問題 提出コード 解法 段目の階段にたどり着くには、段目もしくは段目から移動する2つの方法のどちらかを利用する必要があります。 つまり、段目に行く移動の種類数と、段目に行く移動の種類数がわかれば、段目に行く移動の種類数はその総和で表すことができ…

AOJ 1195 - 暗号化システム

問題 提出コード 解法 最悪ケースを考えると、サンプルにあるような17711通りのパターンになります。 ということで、全部列挙してから文字列をソートし、10個出力するのが十分間に合います。 あとは、全部列挙する方法を考えていけばよいです。 操作終了後の…

AOJ 1131 - Unit Fraction Partition

問題 提出コード 解法 DFSで答えを探します。 まず、分母の値が小さいものから順番に使用していくとします。そして、以下の情報を持ちながら探索していきます。 一番最後に使用した単位分数の分母の値 現在の総和(分母、分子) 現在いくつの単位分数を利用し…

AGC034 B - ABC

問題 提出コード 解法 ABCがBCAになるので、これが連鎖的に続くことを考えると、 AAA...BCがBC...AAAになる、もしくはA...BCBCがBCBC...Aになる、の2通りです。 後者のパターンは、前者のパターンをBCが連続している個数だけ繰り返す、とみなすことができる…

AGC034 A - Kenken Race

問題 提出コード まずは、すぬけ君とふぬけ君がどちらか1人だけの時に、目的地にたどり着くことができるかを調べます。 それぞれ、の範囲に岩#が2個以上連続して配置されている場合、プレイヤーが移動した結果、Pをプレイヤーとすると、 P##のようになり、こ…

M-SOLUTIONS プロコンオープン C - Best-of-(2n-1)

問題 提出コード 解法 引きわけがネックなので、どうにか別処理できないか、を考えてみます。すると、 回勝負がつくまでにかかるゲームの回数の期待値 とすると、 から、 と計算することができます。 この計算により、回でゲーム全体が終了する場合について…

ABC127 E - Roadwork

問題 提出コード 解法 0.5うんぬんという条件がありますが、結局は時刻の間で座標に到着した場合、その人はそれ以上進めない、ということになります。 これを言い換えると、時刻の間に座標を出発する人は、少なくともより先に進むことができなくなります。 …

ABC128 D - equeue

問題 提出コード 解法 から取り出した宝石をに再び詰めた後、再びその宝石を取り出すのは、ただ操作回数を無駄にしているだけなので、先に取り出す宝石の個数を決めた後、捨てる宝石を全て捨てるのが最適になります。 の左から取り出す宝石の個数を個、の右…

ABC128 C - Switches

問題 提出コード 解法 スイッチと電球の個数がとても少ないので、番目の電球に対して機能するスイッチの情報、およびどのスイッチを押すか、という状態をどちらもbitを利用して、int型の変数1つで持つことができます。 スイッチを押すパターンは通りで、多く…

ABC127 F - Absolute Minima

問題 提出コード 解法 は、とりあえず答えに加算すれば良いので、ほとんど無視して問題ないです。ということで、とについて考えていきます。 の総和を最小化する問題は、をの中央値にすればよいです。現在のがわかっているとき、となるようなについては、そ…

ABC127 E - Cell Distance

問題 提出コード 解法 ある位置に置かれた2つの駒のマンハッタン距離が何回加算されるかを考えると、個の残りの駒を配置する種類数そのものになります。ということで、これは回です。任意の位置にある2つの駒について、同じ回数だけ加算されるので、あとは任…

ABC127 D - Integer Cards

問題 提出コード 解法 カードを交換する順番は自由に置き換えても問題なく、もしくはが大きいものから順番にN枚選んでいくのが最も最適な行動になります。 ということで、とのペアをそれぞれ降順にソートし、の先頭との先頭を見比べ、大きいものを枚の中で選…

ABC127 C - Prison

問題 提出コード 解法 枚目のカードを用いて通ることができるゲートの個数 とすると、となるようなの個数が答えになります。 ということで、各ゲートについて与えられる区間について、に1を追加する、という操作をしてあげれば、枚目のカードを用いて通るこ…

Educational DP Contest / DP まとめコンテスト U - Grouping

問題 提出コード 解法 制約から見てbitDPです。 現在グループを組めていないウサギの状態がのときに、それ以降のグループ分けで得ることができる得点の最大値 とします。すると、の部分集合を用いて、 と書くことができます。 ただし、は、というグループを…

ABC126 F - XOR Matching

問題 提出コード 解法 の場合 ならばもしくはもしくはを出力すればよく、それ以外ならばを出力します。 それ以外の場合 の場合、数列に含まれる数字はまでの関係で、どう頑張ってもを作成することができないので答えはになります。 そうでない場合、 という…

ABC126 E - 1 or 2

問題 提出コード 解法 を指定してその数字を特定したとします。 すると、はの偶奇に関わらず、自動的に数字が特定できます。 そして、これが連鎖的に続くことになり、 他にが条件に含まれている部分についても自動的に、もう片方が特定されていきます。 ので…

ABC126 D - Even Relation

問題 提出コード 解法 木、とは書かれているのですが辺に重みがあるのでダイクストラをしてしまいました。 ある頂点と別の頂点の距離が奇数の場合、その部分は確実に色が異なります。 これを繰り返すと、結局はある頂点を一つ決めた際に、そこからの距離の偶…

ABC126 C - Dice and Coin

問題 提出コード 解法 サイコロの目がであったときにすぬけ君が勝つためには、を超えるまでコインの表を出し続ける必要があります。 この回数をとすると、これはがを超えるまで2倍しつつカウントしていけば求めることができます。 ということで、を出した時…

CPSCO2019 Session3 E - Enumerate Xor Sum

問題 提出コード 解法 のときの答えを求めてみます。 については、の累積xorをとっておくことでで求めることができるので割愛します。 とのxorを取った値をとすると、xorの定義から、それぞれの桁について、の立ってるビットの個数が1ならばのその桁は1、そ…

diverta 2019 Programming Contest D - DivRem Number

問題 提出コード 解法 問題の条件を整理すると、 として、 となるので、つまり、 となります。 ということで、かつを割り切るようなの総和が答えとなるので、で約数を列挙し、その総和を求めれば良いです。 感想 割り算の式を思い出すと、ぱっと解ける問題で…

diverta 2019 Programming Contest C - AB Substrings

問題 提出コード 解法 まず、それぞれの文字列の中に含まれるABの個数を調べます。これは、文字列をどのように連結しても、個数が変化することはないので、そのまま答えに加算されます。 では、文字列の連結によってあらたに増えるABの個数を調べます。 文字…

AOJ 1553 Manhattan Warp Machine 1

問題 提出コード 解法 ある地点からは、ボタンを押すと正負2つの向きに進むことができてしまうので、単純なDPを行うことができません。 ので、代わりにダイクストラ法で始点から進んでいくと、うまく計算することができます。 コストを辺の重みとみなし、そ…

AOJ 1551 A White Wall

問題 提出コード 解法 制約を見ると、愚直に全探索しても間に合うことがわかるので、ただひたすらに愚直に実装します。 今回は、の幅に塗りますが、これをに塗ると考えれば、に塗ることをに塗る、と表現できるようになり、配列のカウントに落とし込めます。 …

AGC033 C - Removing Coins

問題 提出コード 解法 それぞれのターンで、ある頂点を指定すると、その頂点を根とする木について、葉になっている頂点が消えることになります。 そして、どのような頂点の選び方をしても、木についている頂点を減らすのに一番時間がかかる部分は、木の直径…

AGC033 A - Darker and Darker

問題 提出コード 解法 マスが黒になるのは、初期状態における黒いマスとのマンハッタン距離を全て調べ、そのうちの最小値回だけ操作を行ったときになります。 ので、全てのマスについて、初期状態に存在している黒いマスとのマンハッタン距離の最小値を調べ…