問題文 解法 区間DPをします。 の区間に対する最小コスト とすると、 になります。 ただし、の文字列を複数回連結するとになる場合のみ、 になります。 この複数回連結、という判定はKMPの周期判定を用いると上手くできます(下のブログ参考)。 ただし、ぴっ…
Dashboard - 2019-2020 ACM-ICPC Latin American Regional Programming Contest - Codeforces なんか解法書こうと思ったんですけど時間かかりそうなのでそこは暇だったらにします しろくんとsuta君と出ました。 流れ 開始後 僕がAから、suta君がDから、しろ…
ここであまり得意でないパターンの問題が出てきたのでメモです。DEGwerさんの数え上げPDFなんかにはいろんな種類が載っているので、また出てきたら追加します。数式をごちゃごちゃいじるとできるパターンもそのうち載せたいです。 について計算をしたい、と…
問題 提出コード 解法 明らかに、線分とが交差しない場合は、それぞれの街を直接結ぶのが一番距離が短くて済みます。 つまり、今回考えるべきなのは、とが交差する場合になります。 このとき、仮にの経路を、と交差しないように迂回して作成したとすると、ど…
問題 提出コード 解法 1日乗り放題になる路線をビットで表したものがとなるようにする際の、1Dayパスポートの合計金額の最小値 をまず求めます。 これは、配るDPを用いて、を繰り返し計算していけばよいです。で求まります。 では、乗り放題の路線を決め打ち…
問題 提出コード 解法 について、で割り、切り上げをしておきます。これで、が 番目のモンスターを倒すまでにかかる攻撃回数 となります。加えて、全てのモンスターを、の昇順で並び替えます。 1番目のモンスターについて考えると、回どこかで攻撃しなければ…
問題 提出コード(1) 提出コード(2) 解法 番目までの魔法を撃ち終えて、だけダメージを与えたときに消費する魔力の最小値 とすると、 のとき のとき となります。 初期値は、答えは、です。 見るべきの範囲は、までなので、最大でも程度になり、このDPによる…
問題 提出コード 解法 それぞれの頂点について、回目に選ばれたか選ばれてないか、について考えると、パターンあります。 これらをビットで表すと、だけ、全体から1つ頂点を減らすことができます。 また、回目と回目に同時に選ばれる頂点が2つ以上あることは…
問題 提出コード 解法 あらかじめ、頂点からへのパスに使われる辺の集合を表すビット列を、前計算で計算しておきます。これは、任意の頂点からBFSで辿っていけば良いです。 個の条件からいくつか選んだ、条件の集合に対して以下のような数を計算します。 少…
問題 提出コード 解法 の値は、明らかに達の最小公倍数になります。 ですが、愚直にやっては途中でオーバーフローをしてしまうため、最小公倍数の素因数を先に列挙してあげることで、後ででMODを取りながら計算してあげると、オーバーフローせずに最小公倍数…
問題 提出コード 解法 のうち、をある値に決めた際にペアの相手となりうるの個数がいくらか、を高速で求めることができれば、について全探索をして数え上げれば良いです。 の値を決め打ったときに、の末尾の値と先頭の値は固定されてしまいます。 前者はの先…
問題 提出コード 解法 人を頂点、(起こす、起こされる)を辺としたグラフについて、強連結成分分解をして同一視される頂点は、一つにまとめることができます。 まとめる頂点集合をとしたときに、まとめた結果新しくできる頂点全体で寝坊する確率は、 とするこ…
問題 提出コード 解法 ある頂点が白であったときに、その頂点がに含まれる確率を計算します。すると、この確率は、どの頂点についても独立に計算できるので、全ての頂点について同じことを計算して足すことで、その総和が答えとなります。 また、確率は、に…
問題 提出コード 解法 明らかに、得点の和が高いペアから順番に握手をしていくのが最適です。 ある得点が達成できるとすると、明らかに未満の任意の得点は、全く同じ手を選ぶことで達成でき、達成できないときは以上の得点はどう頑張っても達成できないので…
問題 提出コード 解法 次に出す手は、手前の手にのみ依存します。 よって、じゃんけんの出す手は、で割った余りごとに独立して考えることができます。 番目に出す手がであるときにおける、の手番についての得点の総和の最大値 とすると、答えは となります。…
問題 提出コード 解法 個の花束を作成できるかどうか、を調べます。 まず、2種類の花束どちらも、1つの花束につき少なくとも1本使用することになるので、最低本ずつ使用することになります。 この部分を除くと、 赤い花を本使用する 青い花を本使用する の2…
問題 提出コード 解法 頂点1が距離0でない場合や、頂点1以外が距離0である場合は、明らかに答えが0になるので処理しておきます。 それ以外のグラフについて考えます。 あらかじめ、距離がの頂点の個数をそれぞれカウントしておきます。 距離がである頂点は、…
問題 提出コード 解法 計算結果は、いずれのタイミングでも、どのように計算しても最大で256通りです。 毎回、2つの変数を用いて演算を適用するので、通りとなります。 演算は未満であることは確実なので、十分計算が間に合います。 よって、可能性のある計…
問題 提出コード 解法 任意の五芒星から別の五芒星に向かう際に通る最短距離さえ計算できれば、あとはベガからアルタイルに向けてダイクストラ法で最短経路を計算すればよいです。 五芒星は5本の線分でできています。ということで、2つの五芒星の最短距離を…
問題 提出コード 解法 言われた通りに実装をしましょう。 感想 最後に出力すべきものを誤読していたため、時間がかかってしまいました… 行う操作によって手数が変わるかもしれない、とdpっぽくやっていったのですが、(本来の)答えが一意に決まることに気づい…
問題 提出コード 解法 、それぞれを始点とする任意の頂点への最短距離をあらかじめ求めておきます。から頂点への最短距離を,から頂点の最短距離をとします。また、との距離をとします。 頂点に辺を張った際、仮にの順に頂点を通り、問題の条件を満たすとする…
問題 提出コード 解法 それぞれの盤面の数字に対して、どの位置に書かれているか、を記録します。 あとは、枚のカードを愚直にシミュレーションしていけばよいです。 一直線に個の数字がそろったかどうかは、現在行目、列目にいくつ数がそろっているか、をカ…
問題 提出コード 解法 まずは、それぞれの文字について、2つの座標をペアで記録しておきます。 あとは、残っている文字のペアについて、消せるかどうかを確認→消せるなら消去、を繰り返せばよいです。 文字のペアは最大でも26しかないので、この操作を26回行…
問題 提出コード 解法 宝について、x座標の昇順であらかじめソートしておきます。 セグ木を用いて宝を管理していきます。 を表す頂点には、先ほどソートした宝のについて、今度はy座標のみを取り出し、これを昇順に並べた数列を持たせます。 すると、あるク…
問題 提出コード 解法 経路は線分で、入力が与えられた時点で全て決まっているため、選ぶことができるのはどの箇所を地上に、どの箇所を地下にするか、です。 新しくつくる路線が既存の路線と交差する地点もはじめから決まっているので、それらはあらかじめ…
青になってから半年と少しがたち、ようやく黄色になることができました。 振り返りをします。自分が書きたいことを書いているので、黄色になるための秘訣！みたいな記事ではないです。ご了承ください。 黄色になりましたーー！！！ pic.twitter.com/XTVUlTpE…
問題 提出コード 解法 直角三角形と鈍角三角形について、それぞれ直角、鈍角な角は1つの三角形につき1つです。それ以外は全て鋭角となるので、 直角三角形→直角の個数 鈍角三角形→鈍角の個数 鋭角三角形→から上2つの個数を引いたもの が答えになります。 あ…
問題 提出コード 解法 番目の足場へ行く最小コスト とします。すると、 となります。 これを式変形すると、 となります。は最後に足して問題ないことがわかります。 とすると、 という式になり、調べたいのは、 のの際の最小値 となります。 これは直線の式…
問題 提出コード 解法 包除原理を用いて解きます。 個以上の壁を通り、番目の壁に到達するような通り方の場合の数 とします。ここで、壁について、行、列の順で昇順ソートしておくと、番目の壁を通る際に、番目以降の壁を先に通ることはありえなくなるので、…
問題 提出コード 解法 現在、積まれているブロックの重さの総和をとします。 ここに、2種類のブロックを、どちらの順番で新しく下に置くかを考えます。 の方がより上にくる場合 の方がより上にくる場合 1つめの条件は、結局2つのブロックを乗せることにした…
