ツバサの備忘録

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

ABC070 D - Transit Tree Path

問題 提出コード 解法 最短経路を求める問題で、頂点数があるので、各クエリごとにダイクストラ法を適用していたのでは間に合いそうにありません。 そこで、経由する点がで固定であり、この木が無向グラフであることに注目すると、から各頂点への最短距離を…

ABC018 D - バレンタインデー

問題 提出コード 解法 部分点が、どうせ男女の組み合わせについてすべてのパターンを試すんだろうなぁ、という感じがしたので、どうせ男子か女子どちらかのみを探索すると答えを求めるようにすることで高速化をするのかなぁ、という気持ちになります。 とい…

ABC068 D - Decrease (Contestant ver.)

問題 提出コード 解法 操作が2種類あって考えづらいので、操作をひとまとめにします。 答えとなる数列の全ての数字にを足し、1回の操作を行うと、数列の最大値を1つ選びを減らす、というようにすると、回操作を行った後の状態はもともとの条件と同じ数列にな…

ABC071 D - Coloring Dominoes

問題 提出コード 解法 縦になっているドミノ1本と、横になっているドミノ2本をそれぞれ1セットとして考えていきます。これは、文字目の上下が一致しているかどうかを調べるだけで簡単に判断できます。横になっているセットについては、次のセットに行くとき…

ABC067 D - Fennec VS. Snuke

問題 提出コード 解説の解法が綺麗すぎますね!! 解法 1とN以外の頂点を、 1から、Nを通らないとたどり着けない頂点 Nから、1を通らないとたどり着けない頂点 1とNどちらも、もう片方の頂点を通らずにたどり着ける頂点 の3種類に分けることができます。図で…

ABC017 D - サプリメント

問題 提出コード 解法 番目までのサプリメントを飲む方法数 とします。 番目のサプリメントを飲むときは、 番目のみを1日で飲む 番目と番目の2つを1日で飲む 番目から番目の3つを1日で飲む というように、同時に飲むこともできます。 しかし、番目から番目の…

ABC065 D - Built?

問題 提出コード 解法 考察でごり押したら最小全域木とかいうやつを使っていたみたいです。 初期状態だと辺の可能性が約本あるので、これだと何をするにも不便です。 ですが、実は本程度まで減らすことができます。 個の座標をxについてソートした場合の隣り…

ABC063 D - Insertion

問題 提出コード 解法 基本的に、"("を追加するのは文頭、")"を追加するのは末尾で大丈夫です。 正しい括弧列Xと任意のYが存在したとき、 "("を追加すべきパターンは X)Y, )XY, XY) のようなパターン(最後のパターンのみ、Yも正しい括弧列という条件付き)で…

ABC063 D - Widespread

問題 提出コード 解法 全員を倒すまでにかかる回数が、最悪回なので、かぐらいまで計算量を落としたいです。 すると、倒すのにかかる回数を二分探索すると、うまくとlogの計算量に落ち着きそうです。 倒すのにかかる回数を二分探索するということで、 回魔法…

ABC063 C - Bugged

問題 提出コード 解法 CはDPのC!(n回目)解説PDFによるとオーバーキル解法だそうです… までを利用して、合計得点を10で割った余りがとなるような得点の取り方の最大値 としてDPを解いていきます。 これは、 で解くことができます。 最終的な答えは、 の、の部…

ABC062 D - 3N Numbers

問題 提出コード やること自体は同じだったのですが、想定解がすごい綺麗で感動しました。ここでpriority_queueが使えるのですね~ 解法 この問題は、初期値を(前からNの長さの部分の総和)-(後ろからNの長さの部分の総和)とし、 真ん中のNの長さの部分を、 …

ABC062 C - Chocolate Bar

問題 提出コード これの類題的な感じですね。 解法 縦と横については、向きを入れ替えて同じことを考えればよいので、とりあえず縦と横を固定した状態で考えます。 チョコレートを3つに分けるには、まず2つに分け、そのうち片方をまた2つに分ける、というよ…

ABC061 D - Score Attack

問題 提出コード1 提出コード2 提出コード1は愚直にメモ化再帰をしたものです。実装に2時間以上かかっているのでお話にならないです… 提出コード2は解説PDFと同じものになります。ベルマンフォード法を使ったことがなかったので実装しました。 解法 提出コー…

ABC061 C - Big Array

問題 提出コード 解法 入れる個数と入れる数字をセットにした状態で、入れる数字の昇順でソートします。 そして、前から入れる個数を足していき、K個になった時点で入れた数字が答えになります。

第5回 ドワンゴからの挑戦状 予選 C - k-DMC

問題 提出コード WAしていたコードの冗長な部分をコンパクトに書き直していたら、バグが消えていたのに提出しなかったので、結局時間内にACすることができませんでした…パフォが400ほど変わるのでめちゃくちゃ悔しいです。知らぬ間にバグが消えていたパター…

第5回 ドワンゴからの挑戦状 予選 B - Sum AND Subarrays

bit

問題 提出コード 解法 たかだか1000個の数字しかないので、まずはあり得る部分列の和をすべて書き出します。 その後、一番大きい数字を2進数に直したときの、一番左側のビットから順番に、使用できるかどうかを判定していきます。 左側から順番に使用すると…

ABC060 D - Simple Knapsack

問題 提出コード 解法 ナップサックと書いてあるのでとりあえずDPを考えます。 をすべての重量から引いていくと、どれも0~3のいずれかの重量に置き換えることができます。 この重さを利用して、次のようなDPを考えていきます。 番目までの荷物の中で、個使用…

ABC060 C - Sentou

問題 提出コード 人目の人がボタンを押したタイミングで、まだお湯が流れていた場合は、を追加、流れていなかった場合は秒が経過しているので、を追加していきます。 これを繰り返し、最後の人が押してから流れる秒分を最後に追加すればよいです。 結局は、 …

ABC059 C - Sequence

問題 提出コード 解法 一番最初を正でスタートするか、負でスタートするかの2通り試し、より良い方を答えとして出力します。 までの総和が、次になるべき符号と同じであればそのままに進みます。符号が異なっていれば、 負になるべきならば、総和が-1になる…

ABC016 D - 一刀両断

問題 提出コード 解法 分割される部分が1つ増えるには、線分ABと交差する多角形の辺が2本増える必要があります。 交差する多角形の辺が奇数になることは必ず存在しないので、多角形の辺と交差する辺の本数を2で割り、最後に1追加したものが答えとなります。 …

ABC057 D - Maximum Average Sets

問題 提出コード 解法 平均値の計算方法を思い出すと、 ですので、データの個数はより少なく、そしてデータの値の総和はより大きいものを選んだ方が得になります。 ということで、一番少ない個数になるのは個だけ選んだ時で、データの選び方は降順にソートし…

ABC057 C - Digits in Multiplication

問題 提出コード 解法 からまで順番に調べ、その中のがで割り切れたら桁数をそれぞれ計算し、答えの更新を行います。 桁数は10で割れる回数で、0になるまで10で割っていけばよいです。 と両方について桁数を求め、そのうち大きい方がの答えになりますので、…

ABC056 D - No Need

問題 提出コード サンプル3についてなんとなく考えると、不必要なカードは2,3,4の3つであり、これはすべてのカードの中で小さい3つを選ぶ形になります。 ということで、なんとなく、昇順にソートすると前の方が不必要、後ろの方が必要なカードになりそうなこ…

ABC056 C - Go Home

問題 提出コード ジャンプする時刻の最大値をとすると、から順番に1ずつ減らしてみていき(今見ている時刻を とします)、よりが小さければ時刻がのときにジャンプすることにしてからを引く、という操作を繰り返していけば、ジャンプする時刻を求めることがで…

ABC077 D - Small Multiple

問題 提出コード 桁和関連の問題は本当に解ける気がしないです…方針が立ちません。解説を読んでもわからないので、数日寝かせていました。 解法 について、基本的には1を足すと桁和が1増加し(例外があります)、10倍すると桁和は据え置きです。 ということで…

ABC055 D - Menagerie

問題 提出コード 構築です。 解法 番目の動物は、と番目の動物が何か判明していれば、自動的に決まります。 これは4通りあり、 番目が〇か×か、そして番目の動物がどっちであるか、です。 番目が〇で羊の場合 番目は番目と同じ動物になります。 番目が〇で狼…

ABC055 C - Scc Puzzle

問題 提出コード 解法 cを2つ利用してSを作成するのは、Sの在庫がなくなってからでいいです。 ので、まずはSを1つ、cを2つ使ってSccを作成します。 この方法で作れるSccの個数は、Sの個数と、cを2で割ったもののうち小さい方になります。 これが終わってなお…

ABC077 C - Snuke Festival

問題 提出コード 中段について、番目のパーツを使うとしたときに、使うことができる下段のパーツはとなるパーツ番号の場合です。このようなのうち最小のものをもとめれば、それより大きい個のパーツはすべて使用できます。 ということで、まずはそれぞれのパ…

ABC054 D - Mixing Experiment

問題 提出コード 解法 DPをします。 番目までの薬品で、がグラム、がグラムになるような選び方の最小値 とします。 初期値は、、それ以外はです。 あとは、 という遷移をしていけば大丈夫です。 最終的な答えは、 となります(ここで、は1以上です)。

ABC019 C - 高橋くんと魔法の箱

問題 提出コード 解法 ある数字について、2でi回割る、もしくはi回書けたものは必ずすべて同じ数字が出てきます。ということで、それを手っ取り早くするために、同じ数字の中で最小のものを採用して重複の無いようにカウントしていきます。 なので、方針は次…