ABC 009 C問題に使われるアルゴリズム要素は貪欲法です。貪欲法自体は定型のアルゴリズムがあるわけではないので、知識ではなく地頭を問う問題です。 C - 辞書式順序ふたたび 解説：Abc009 問題文 文字列Sとその長さN、そして入れ替えしていい文字数Kが与え…

問題 考えたこと 方針 期待値の線形性を利用して数列の美しさの算出を分解する 例 問題 d = 0の場合と d != 0の場合で場合分けする 解答コード 問題は単純なのだが、解法が全然思いつかず。 問題 C - Ordinary Beauty N, M, D が与えられるとき 1 ～ N まで…

組み合わせ 組み合わせを階乗の式で表す 組み合わせの式 ABC 066 (11) 、解説の解説 問題の考察ヒント 考察 簡単な例 重複を取り除くパターン ABC 040 D問題に使われるアルゴリズム要素は組み合わせ、繰り返し２乗法、階乗のmod逆元、（＋累積和的な処理？）…

競プロ始めた この記事は Competitive Programming Advent Calendar 2017 - Adventar のために書かれました。 競プロ始めた 競プロやろうと思った動機 AtCoderの感触 最初３ヶ月ぐらいの体感 最初３ヶ月ぐらいの気づき 後半３ヶ月ぐらいの体感 後半３ヶ月ぐ…

アルゴリズム 経路圧縮 rankによる木のマージ処理 ABC 040 D問題に使われるアルゴリズム要素はUnion-Findです。Union-Find自体は前回ブログ記事にしていたのですが…これだけでは足りませんでした。ACするためには経路圧縮とrankによる木のマージ処理が必要で…

前回の競プロ！ 解法 Rubyによる解答 TLE D言語による解答 AC! 前回の競プロ！ ダイクストラ法を学んでようやくスタート地点に立てました。ダイクストラ法については以下のエントリを参照。nantonaku-shiawase.hatenablog.com 解法 Rubyによる解答 TLE アル…