yukicoder

Codeforces Round #388 (Div. 2) D. Leaving Auction

問題 codeforces.com 考察 人が消えるオークションをする問題です。 注意点として、間の人が消えてある人が連続したら、その場合は圧縮されて落札可能な最も安い値段になります。 参加者の数もクエリの数もと多いですが、 除外する参加者の数が最大なので、…

yukicoder ★★★ No.307 最近色塗る問題多くない?

問題 No.307 最近色塗る問題多くない? - yukicoder 考察 同じ色で塗った時、塗りつぶしは行われずすぐ終わります。 違う色で塗った時、少なくとも1つはマスの色が変わります。 違う色で塗る処理はその色を全て辿ればいいので、最悪でもで終わります。 また…

yukicoder ★★★ No.1 道のショートカット

おみくじで記念すべき1を引きました。 問題 No.1 道のショートカット - yukicoder 考察 グラフ、に見せかけて、パスは番号が増加するものしかないためDPできます。 お金、時間の2つのパラメーターがあるため、1つはDP表に入れてしまえば答えを求めることがで…

yukicoder ★★★ No.413 +5,000,000pts

問題 No.413 +5,000,000pts - yukicoder 考察 一風変わった問題ですね。 Hackできるケースを考える問題のようです。 与えられたコードを読むと、いかにもな解の公式が書かれています。 +側しか取っていませんが、tは最大の整数なので問題なさそうです。 全く…

yukicoder No.402 最も海から遠い場所

問題 No.402 最も海から遠い場所 - yukicoder 考察 チェビシェフ距離はあまり見慣れない名前ですが、自分を円の中心とした距離のようなものです。 海からチェビシェフ距離が一番遠いマスはどのような箇所でしょうか。 とある点を中心に、全方向になるべく距…

yukicoder No.50 おもちゃ箱

問題 ★★★ No.50 おもちゃ箱 - yukicoder 考察 おもちゃ・箱の数は少なく、大きさの最大値も小さいです。 ただ、2つのバラバラな数列があるため、単純に手前からとはいきません。 そこで、箱を順番に処理し、「その箱の中でどれだけ使っているか」「どのおも…

yukicoder ★★★ No.416 旅行会社

問題 No.416 旅行会社 - yukicoder 考察 1の島から各島にたどり着けるかどうかはUnionFind木を作ればわかります。 が、削ることはできないため、橋を削る都度作っているとTLEしてしまいます。 かと言って、橋が落とされた時の変化を求めるのも大変そうです。…

yukicoder ★★ No.415 ぴょん

問題 No.415 ぴょん - yukicoder 考察 とっかかりとしては、NとDが互いに素であれば全て巡ることができそうです。 ここからgcdあたりが関係しそうだなと思いつきます。 一度踏んだ足場をもう一度踏むループに入った時、最初に踏むのは必ず初期位置の足場です…

yukicoder ★★ No.414 衝動

問題 No.414 衝動 - yukicoder 考察 ある数Mの約数は、までに存在します。 そのため、2から探索を開始して、割り切れる数値が見つかればそのペアを出力し、見つからなければ1とMを出力すれば終わりです。 コード int main() { ll M; cin >> M; REP(i, 2, sqr…

yukicoder ★★ No.39 桁の数字を入れ替え

問題 No.39 桁の数字を入れ替え - yukicoder 考察 1回しか入れ替えられないので、実際に二重ループを回して入れ替え、大小を比較すれば解けます。 桁は9桁以下なので、ごく僅かなループ数で済みます。 簡単なコード int main() { string N; cin >> N; string…

yukicoder ★★★ No.269 見栄っ張りの募金活動

yukicoderは解説に溢れているので書く必要はあまり無いような気もします。 問題 No.269 見栄っ張りの募金活動 - yukicoder 考察 普通のDPのようですが、払わないといけない金額が前の人に依存するため、この制約では計算量が大きくなりすぎます。 dp[i][j][k…