普通に難しかった。 E - Weights on Vertices and Edges 問題 N頂点M辺の無向グラフが与えられる。頂点と辺には重みがついている。 このグラフから辺を何本か取り去って、残っている辺がすべて以下の条件を満たすようにしたい: 辺の重みをYとすると、その辺…

こういう、適切な貪欲をやる問題が苦手すぎる…。 D - Various Sushi 問題 N個の寿司があり、i個目の寿司の種類はt_i、美味しさはd_iである。この中からK個選び、美味しさd_iの総和とt_iの種類数の2乗の和を最大化したい。最大値を求めよ。 解法 寿司を美味し…

楽しいコンテストだった 来社 寝坊して9:24頃到着した(受付は9:00-9:50)。運良くコンセントのある席が残っていてよかった。 本戦問題コード部門 DISCO presents ディスカバリーチャンネル コードコンテスト2019 本戦 - AtCoder A (00m00s-07m56s): 「300にし…

まあ実家だよね。 D - DISCO! 問題 'D', 'I', 'S', 'C', 'O'のみからなる文字列Sが与えられる。このとき、以下のQ個の質問に答えよ: SのL_i文字目からR_i文字目までからなる部分文字列を考える。この文字列に部分列として含まれる"DISCO"は何通りあるか? つ…

実装が大変すぎる。 F - 文字列大好きいろはちゃん / Iroha Loves Strings 問題 文字列の列s_1, ..., s_Nが与えられる。これの部分列を順序を保ったまま連結して、長さKの文字列を作ることを考える。ありえる文字列の辞書順最小値を求めよ。 制約 1 1 1 \sum…

色々な解き方があって本当に面白い問題だと思う。 E - Connecting Cities 問題 整数N, Dと長さNの整数列A_iが与えられる。以下の完全グラフの最小全域木の重みを求めよ。 頂点数はN 頂点iと頂点jを結ぶコストはD|i - j| + A_i + A_j 解法 Code Festival 2017…

母関数おじさんにとっては多分実家。 F - Paper Cutting 問題 長方形の中に縦線がH個、横線がW個ある。これからK本の辺を選んで、順番にその線に従って長方形をカットする。 各カットについて、そのスコアはカット後の分割された長方形の個数である。P(H + W…

1.7年前(2017/4/22)の本番では解法の見当もつかなかったが、改めて考えてみたら分かった。 F - Dam 問題 数Lと数列v_1, ..., v_N, t_1, ..., t_Nが与えられる。このとき、各1 許容量Lリットルのダムに水を流入させることを考える。1日目にt_1度の水v_1リット…

最初面倒 + 間違っている方針を考えていたが、某にもっと簡単な方法があると言われたので簡単な方法に気づくことができた。 F - Shift and Decrement 問題 N個の非負整数A_1, ..., A_Nが黒板に書かれている。以下の操作をK回まで行う。 以下の2個から一つ選…

最初見た時こんなの無理だろと思ったが、期間をおいて考え直したら分かった。 F - Prime Flip 問題 無限枚のカードがある。カードには1番から番号が振られている。最初x[1], ..., x[N]番目のカードは表向きで、それ以外は裏向きである。 以下の操作を何回か…

当時E問題と同じセットで出題され、全完が5人しかいなかった。強い人にとっては典型。 例: F 程よい典型詰め合わせだと思うんだけどなんでこんなに解かれてないんだろう— エレベーターに乗ったら行先階ボタンを押す (@DEGwer3456) 2018年3月25日 F - Dark Ho…

本番解けなかったけど、知識が増えた状態でやり直してみたら解けたのでよかった。 E - Bichrome Spanning Tree 問題 N頂点M辺の無向グラフがある。各辺を白か黒で塗るとき、以下の条件を満たすような辺の塗り方を求めよ。 白い辺と黒い辺を1個以上含む全域木…

この手の全体の中から一つ取り除くタイプの問題は、「sigmaさんが『yosupoがこういうの得意です』と言っていたタイプの問題」という印象が強い。 F - Two Faced Edges 問題 N頂点M辺の有向グラフがある。各辺について、その辺だけの向きを反転した時、グラフ…

2019年の目標です。 競技プログラミング レーティングをAtCoder 2900以上、Codeforces 2500以上(、Topcoder 2200以上)にする 週に1回は、難しい問題を解説を見て通す 実装が難しい問題が望ましい 競プロ共通ライブラリプロジェクトを進める 開発 RustやErlan…

本番見すらしなかった問題だけど、解説を見たりドワコン5th本戦C問題の準備をしたりして理解が深まったので解けた。 J - Tree MST 問題 辺に重みがついているN頂点の木、および長さNの数列Xが与えられる。このとき、以下の完全グラフの最小全域木の重みを求…