7K12 blog

猫でも分かるアルゴリズム解説

2020-04-01から1ヶ月間の記事一覧

ABC146 E - Rem of Sum is Num

https://atcoder.jp/contests/abc146/submissions/12441749 青dif問題は天才解法すぎる… 要素の和・余りということで、とりあえず累積和のMODを取ってみる。 MOD([R, L]の総和) = MOD(累積和R - 累積和L) = MOD(indexR - indexL) が成立すれば良い(indexR -…

ABC164に参加した感想

A2分、B5分、C2分、の3完だった。凡人なので一生fizzbuzzしか書けない虚しさ。 世の中7割以上の人間がfizzbuzzしか書けないと考えると仕方ないのか…。 A - Sheep and Wolves https://atcoder.jp/contests/abc164/submissions/12351154 if文を書く。 B - Batt…

Educational DP Contest P - Independent Set

https://atcoder.jp/contests/dp/submissions/12329034 初期値はall(dp)=1 繰り返しはDFSの再帰 漸化式はdp[i][stW] *= (dp[i][stB]+dp[i][stW]); / dp[i][stB] *= dp[i][stW]; 最終目標はdp[0][stW] + dp[0][stB] 親が白なら子は白と黒の両方あり得る。親が…

ABC100 D - Patisserie ABC

https://atcoder.jp/contests/abc100/submissions/9797243 サンプル3が分かりやすい。 綺麗さ、旨さ、人気、それぞれ±あるので全通り全探索して最も値が大きかった組み合わせを採用する。 ある最適な選び方をしたときの答えがans=|Σx|+|Σy|+|Σz|で,その時Σx…

Educational DP Contest O - Matching

https://atcoder.jp/contests/dp/submissions/10980341 ビット全探索をする 男[i]に対してnCi全通りの更に男女[i][j]=1になってるj通りのループ 制約が21しかないのでビット全探索が出来そうと推測できる。男性[i]までにマッチングが成立した女性の組み合わ…

ABC162に参加した感想

A6分、B10分、C3分、D60分、の4完だった。 間違えてC++でなくCで提出したため、CEになってABの提出が遅れた。 A - Lucky 7 https://atcoder.jp/contests/abc162/submissions/11801855 問題文に答えが書いてある。 B - FizzBuzz Sum https://atcoder.jp/conte…

ABC108 D - All Your Paths are Different Lengths

https://atcoder.jp/contests/abc108/submissions/9690709 dif1800なので数学的考察力が必要、難しい。 各頂点をビットと考えると2進数で表現できそうという気持ちになる。頂点[0]から頂点[19]まであるのでで若干足りないが、とりあえずなら各頂点を0との両…

Educational DP Contest N - Slimes

https://atcoder.jp/contests/dp/submissions/11718958 一見どんな順番で合成しても同じように感じるが、それだと問題にならないので合成する順番によって答えに差が出る(ぇ 他人の解説を見るまで気づかなかったが、最初に足したものが何度も足されるため、…

ABC150 D - Semi Common Multiple

https://atcoder.jp/contests/abc150/submissions/15845505 偶数 は にする 小数を整数にする → を素因数分解したとき因数2の個数が全て等しい必要がある のlcmだが、偶数倍はカウントしないので答えは約半分の個数になる 青difなので数学的センス必須。まず…