ツバサの備忘録

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

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つの五芒星の最短距離を…

AOJ 2640 - 不審者

問題 提出コード 解法 言われた通りに実装をしましょう。 感想 最後に出力すべきものを誤読していたため、時間がかかってしまいました… 行う操作によって手数が変わるかもしれない、とdpっぽくやっていったのですが、(本来の)答えが一意に決まることに気づい…

AOJ 2608 - Minus One

問題 提出コード 解法 、それぞれを始点とする任意の頂点への最短距離をあらかじめ求めておきます。から頂点への最短距離を,から頂点の最短距離をとします。また、との距離をとします。 頂点に辺を張った際、仮にの順に頂点を通り、問題の条件を満たすとする…

AOJ 2241 - Usaneko Matrix

問題 提出コード 解法 それぞれの盤面の数字に対して、どの位置に書かれているか、を記録します。 あとは、枚のカードを愚直にシミュレーションしていけばよいです。 一直線に個の数字がそろったかどうかは、現在行目、列目にいくつ数がそろっているか、をカ…

AOJ 2299 - Tiles are Colorful

問題 提出コード 解法 まずは、それぞれの文字について、2つの座標をペアで記録しておきます。 あとは、残っている文字のペアについて、消せるかどうかを確認→消せるなら消去、を繰り返せばよいです。 文字のペアは最大でも26しかないので、この操作を26回行…

AOJ 2426 - 宝探し

問題 提出コード 解法 宝について、x座標の昇順であらかじめソートしておきます。 セグ木を用いて宝を管理していきます。 を表す頂点には、先ほどソートした宝のについて、今度はy座標のみを取り出し、これを昇順に並べた数列を持たせます。 すると、あるク…

AOJ 2003 - Railroad Conflict

問題 提出コード 解法 経路は線分で、入力が与えられた時点で全て決まっているため、選ぶことができるのはどの箇所を地上に、どの箇所を地下にするか、です。 新しくつくる路線が既存の路線と交差する地点もはじめから決まっているので、それらはあらかじめ…

AtCoderで黄色になりました

青になってから半年と少しがたち、ようやく黄色になることができました。 振り返りをします。自分が書きたいことを書いているので、黄色になるための秘訣!みたいな記事ではないです。ご了承ください。 黄色になりましたーー!!! pic.twitter.com/XTVUlTpE…

ABC033 D - 三角形の分類

問題 提出コード 解法 直角三角形と鈍角三角形について、それぞれ直角、鈍角な角は1つの三角形につき1つです。それ以外は全て鋭角となるので、 直角三角形→直角の個数 鈍角三角形→鈍角の個数 鋭角三角形→から上2つの個数を引いたもの が答えになります。 あ…

Educational DP Contest / DP まとめコンテスト Z - Frog 3

問題 提出コード 解法 番目の足場へ行く最小コスト とします。すると、 となります。 これを式変形すると、 となります。は最後に足して問題ないことがわかります。 とすると、 という式になり、調べたいのは、 のの際の最小値 となります。 これは直線の式…

Educational DP Contest / DP まとめコンテスト Y - Grid 2

問題 提出コード 解法 包除原理を用いて解きます。 個以上の壁を通り、番目の壁に到達するような通り方の場合の数 とします。ここで、壁について、行、列の順で昇順ソートしておくと、番目の壁を通る際に、番目以降の壁を先に通ることはありえなくなるので、…

Educational DP Contest / DP まとめコンテスト X - Tower

問題 提出コード 解法 現在、積まれているブロックの重さの総和をとします。 ここに、2種類のブロックを、どちらの順番で新しく下に置くかを考えます。 の方がより上にくる場合 の方がより上にくる場合 1つめの条件は、結局2つのブロックを乗せることにした…

Educational DP Contest / DP まとめコンテスト W - Intervals

問題 提出コード 解法 文字目を"1"にした場合に、で得られる得点の最大値 を考えます。 すると、 が間に含まれているものを除いた区間達について計算した場合の、で得られる得点の最大値に、が間に含まれている区間の得点の総和が、の値になります。 これを…

ICPC 2019 Asia Yokohama Regional参加記

ということで、チーム CoprimEとして、ICPCのアジア予選に参加してきました。 チームメイトはTsuzu君、mi君です。 1日目 ~リハーサル前 リハーサル リハーサル後 2日目 本番 コンテスト後 3日目 感想 1日目 ~リハーサル前 一部コーチの奢りです、わーい pi…

Educational DP Contest / DP まとめコンテスト V - Subtree

問題 提出コード 解法 全方位木dpをします。 初めに頂点1が根である際の値を求めます。 を根とする部分木について、を黒で塗った際の部分木の塗り方 とすると、頂点の子の集合をとして、 となります。 を根とした際の求めるべき答え とすると、 となります。…

第16回JOI本戦 A - フェーン現象 (Foehn Phenomena)

問題 提出コード 解法 それぞれのタイミングでの、の差がわかれば、のどちらかをかけつつ総和を求めればよいです。 それぞれの差について注目すると、ある区間が与えられたときに、に影響が出るのは、の2つのペアのみになります。これ以外の部分、およびこれ…

第13回JOI予選 D - 部活のスケジュール表 (Schedule)

問題 提出コード 解法 日目に参加した部員の状態がであるような、から日目までの部員の組み合わせの通り数 とします。 すると、 の中に、責任者が含まれていなければならない という条件があるので、もしの中に責任者がいなければ、 となります。 そうでない…

ARC064 E - Cosmic Rays

問題 提出コード 解法 あるバリア内は好きな座標に移動できます。 ので、あるバリアから、別のバリアへと移動することを考えます。 そのとき、2つのバリアについて重複する箇所が存在すれば、そのバリア同士は自由に行き来することができます。そうでないと…