なんとな~くしあわせ?の日記

「そしてそれゆえ、知識そのものが力である」 (Nam et ipsa scientia potestas est.) 〜 フランシス・ベーコン

AtCoder

AtCoder Beginner Contest 009 (辞書式順序ふたたび) を解いてみた

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

SoundHound Inc. Programming Contest 2018 - (Ordinary Beauty) 再考

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

AtCoder - AtCoder Beginner Contest 066 (11) を解いてみた

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

競プロ始めた - アドカレ用

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

AtCoder - AtCoder Beginner Contest 040 (道路の老朽化対策について) を解いてみた

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

AtCoder - AtCoder Beginner Contest 012 (バスと避けられない運命) を解いてみた

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