Atcoder ABC 埋め 1 ~10
publicに書かないとメモ等はどうせ見ないし忘れるからここに書くことに。 実装力に不安があるため Atcoderなどをやってみる。初心者向けとなる AtCoder Beginner Contestをやってみた感想としては、 ABは言語の基本理解、Cは頭使う、Dからはアルゴリズムの問題といったかんじ。 いまのところDがとけたりとけなかったり。 解けなかった問題などのメモ書きを残していく。どこまで続けるかは不明。
いずれやったほうがよさそうなこと
- snippet, template デバッグ用関数用意
define debug4(...) {printf("%s(%d):", __func__, __LINE__); printf(__VA_ARGS__);}など - inverse-mod, 互除法、グラフ関係の関数など用意
- テスト自動化
- 解けなかったものはメモを残す
環境
bash on windows で clipboard $ clip.exe < filename でコピーできる ペーストはデフォルトではできないが、有志のプログラムが存在 https://stackoverflow.com/questions/17819814/how-can-you-get-the-clipboard-contents-with-a-windows-command
002-D 派閥
全探索はだめだろうと考え頑張ってアルゴリズムを考えたが益なし。 調べてみたら最大クリーク問題といってNP完全らしい。
n < 20 なら全探索でもとけるとのこと http://www.tani.cs.chs.nihon-u.ac.jp/g-2006/s5402031hide/maxclq_last.pdf
完全グラフ: すべてのノードが相互に接続されているノード クリーク:完全グラフを誘導する頂点集合
解法: 探索木による全探索 保持するクリーク(1,3,4) のとき、i=5,6,7, を加えたノードもクラークならば (1,3,4,i) を保持するクリークとして新たに探索する。 はじめはi=5,6,7,,, ではなく i=0 から調べてしまっていたので TLE.
003-D AtCoder社の冬
部分点のほうは求め方は単純だけれども 、 nCr mod P を計算する必要がある modをとった割り算は mod_inverse (モジュラ逆数) と呼び、 互除法で求まる。
完全回答には時間がかかった。 結局解説をみて理解した。 また、パスカルの三角形で nCr mod p を求めるほうがずっと簡単だったことにも解説で気づく。
具体的に集合操作をして解となる式を求めるべきだが、たぶんこうだろうという式を書いたら正解だった。本当はダメ。 また、MOD を求める関数で引数を int にしていて嵌っていた。オーバーフローには気を付けよう。
004-D マーブル
部分点は簡単 完全解は何もわからなかった。考えた末に解説を見る dp でとけるらしい pos まできたときに res 個おいている、という発想がまったっくなかった
再帰関数+memo で素直に実装したが TLE(>2ms)
ほかの人の回答を見ると、メモの内容をすべて、順番に計算しているものがあった。 ためしにやってみると 13ms で AC ランダムアクセスするか順番に計算していくかで 100 倍以上違う,,, なるほどなぁ
005-D
正解。 y方向でループしてメモしたのちに、x方向のループをまわす。そのときおいしさは可算していけるのがポイント
006-D
正解。昇順となる一番おおきなまとまりをみつけるため、dp[pos]
007-D 禁止された文字
正解。 [A,B]について該当数字の数を数える <- [1,B] について求める関数fがかければ十分。 先頭の数字が 4 or 9 or それ以外で場合分け。
f(413) = 13 + 1 + d(399) = 14 + 4 * f(100) f(513) = f(13) + 10**2 + 4 * f(100) f( 10**order ) = 2*10**(order-1) + 8 * f( 10**(order-1) )
みたいに考えればok。
