ツバサの備忘録

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

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

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

2019-2020 ACM-ICPC Latin American Regional Programming Contest F. Fabricating Sculptures

リンク 問題文 解法 1段ずつ下からブロックを積んでいくことを考えます。 ある段のある区間にブロックを積んだら、それ以降はその積んだ区間に対してのみ積んでいくかどうかを考えます。 今区間の幅が残りで、ブロックの残り個数が個の際の、そこからの構築…

2019-2020 ACM-ICPC Latin American Regional Programming Contest G. Gluing Pictures

リンク 問題文 解法 これの類題です。 文字目までの文字列を完成させるのに最小となる連続部分列の個数 とします。すると、この配列は広義単調増加になっているはずなので、 は、文字目を右端とするようなの部分文字列の中で最長の長さをとしたとき、となり…

SWERC 2018 K. Dishonest Driver

問題文 解法 区間DPをします。 の区間に対する最小コスト とすると、 になります。 ただし、の文字列を複数回連結するとになる場合のみ、 になります。 この複数回連結、という判定はKMPの周期判定を用いると上手くできます(下のブログ参考)。 ただし、ぴっ…

2019-2020 ACM-ICPC Latin American Regional Programming Contest バチャ 参加記

Dashboard - 2019-2020 ACM-ICPC Latin American Regional Programming Contest - Codeforces なんか解法書こうと思ったんですけど時間かかりそうなのでそこは暇だったらにします しろくんとsuta君と出ました。 流れ 開始後 僕がAから、suta君がDから、しろ…

二項係数の式変形について

ここであまり得意でないパターンの問題が出てきたのでメモです。DEGwerさんの数え上げPDFなんかにはいろんな種類が載っているので、また出てきたら追加します。数式をごちゃごちゃいじるとできるパターンもそのうち載せたいです。 について計算をしたい、と…

AOJ 2334 - 街を駆ける道

問題 提出コード 解法 明らかに、線分とが交差しない場合は、それぞれの街を直接結ぶのが一番距離が短くて済みます。 つまり、今回考えるべきなのは、とが交差する場合になります。 このとき、仮にの経路を、と交差しないように迂回して作成したとすると、ど…

AOJ 2585 - 一日乗車券

問題 提出コード 解法 1日乗り放題になる路線をビットで表したものがとなるようにする際の、1Dayパスポートの合計金額の最小値 をまず求めます。 これは、配るDPを用いて、を繰り返し計算していけばよいです。で求まります。 では、乗り放題の路線を決め打ち…

ABC153 F - Silver Fox vs Monster

問題 提出コード 解法 について、で割り、切り上げをしておきます。これで、が 番目のモンスターを倒すまでにかかる攻撃回数 となります。加えて、全てのモンスターを、の昇順で並び替えます。 1番目のモンスターについて考えると、回どこかで攻撃しなければ…

ABC153 E - Crested Ibis vs Monster

問題 提出コード(1) 提出コード(2) 解法 番目までの魔法を撃ち終えて、だけダメージを与えたときに消費する魔力の最小値 とすると、 のとき のとき となります。 初期値は、答えは、です。 見るべきの範囲は、までなので、最大でも程度になり、このDPによる…

AOJ 2631 - Clique Coloring

問題 提出コード 解法 それぞれの頂点について、回目に選ばれたか選ばれてないか、について考えると、パターンあります。 これらをビットで表すと、だけ、全体から1つ頂点を減らすことができます。 また、回目と回目に同時に選ばれる頂点が2つ以上あることは…

ABC152 F - Tree and Constraints

問題 提出コード 解法 あらかじめ、頂点からへのパスに使われる辺の集合を表すビット列を、前計算で計算しておきます。これは、任意の頂点からBFSで辿っていけば良いです。 個の条件からいくつか選んだ、条件の集合に対して以下のような数を計算します。 少…

ABC152 E - Flatten

問題 提出コード 解法 の値は、明らかに達の最小公倍数になります。 ですが、愚直にやっては途中でオーバーフローをしてしまうため、最小公倍数の素因数を先に列挙してあげることで、後ででMODを取りながら計算してあげると、オーバーフローせずに最小公倍数…

ABC152 D - Handstand 2

問題 提出コード 解法 のうち、をある値に決めた際にペアの相手となりうるの個数がいくらか、を高速で求めることができれば、について全探索をして数え上げれば良いです。 の値を決め打ったときに、の末尾の値と先頭の値は固定されてしまいます。 前者はの先…

AOJ 2748 - 夏合宿の朝は早い

問題 提出コード 解法 人を頂点、(起こす、起こされる)を辺としたグラフについて、強連結成分分解をして同一視される頂点は、一つにまとめることができます。 まとめる頂点集合をとしたときに、まとめた結果新しくできる頂点全体で寝坊する確率は、 とするこ…

ABC149 F - Surrounded Nodes

問題 提出コード 解法 ある頂点が白であったときに、その頂点がに含まれる確率を計算します。すると、この確率は、どの頂点についても独立に計算できるので、全ての頂点について同じことを計算して足すことで、その総和が答えとなります。 また、確率は、に…

ABC149 E - Handshake

問題 提出コード 解法 明らかに、得点の和が高いペアから順番に握手をしていくのが最適です。 ある得点が達成できるとすると、明らかに未満の任意の得点は、全く同じ手を選ぶことで達成でき、達成できないときは以上の得点はどう頑張っても達成できないので…

ABC149 D - Prediction and Restriction

問題 提出コード 解法 次に出す手は、手前の手にのみ依存します。 よって、じゃんけんの出す手は、で割った余りごとに独立して考えることができます。 番目に出す手がであるときにおける、の手番についての得点の総和の最大値 とすると、答えは となります。…

ARC050 B - 花束

問題 提出コード 解法 個の花束を作成できるかどうか、を調べます。 まず、2種類の花束どちらも、1つの花束につき少なくとも1本使用することになるので、最低本ずつ使用することになります。 この部分を除くと、 赤い花を本使用する 青い花を本使用する の2…

ARC044 B - 最短路問題

問題 提出コード 解法 頂点1が距離0でない場合や、頂点1以外が距離0である場合は、明らかに答えが0になるので処理しておきます。 それ以外のグラフについて考えます。 あらかじめ、距離がの頂点の個数をそれぞれカウントしておきます。 距離がである頂点は、…

AOJ 2435 - Zero division checker

問題 提出コード 解法 計算結果は、いずれのタイミングでも、どのように計算しても最大で256通りです。 毎回、2つの変数を用いて演算を適用するので、通りとなります。 演算は未満であることは確実なので、十分計算が間に合います。 よって、可能性のある計…

AOJ 2402 - 天の川

問題 提出コード 解法 任意の五芒星から別の五芒星に向かう際に通る最短距離さえ計算できれば、あとはベガからアルタイルに向けてダイクストラ法で最短経路を計算すればよいです。 五芒星は5本の線分でできています。ということで、2つの五芒星の最短距離を…