7K12B blog

猫でも分かる何か

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

確率DP

Educational DP Contest I: Coins https://atcoder.jp/contests/dp/submissions/10476921 自明に感じる人にとってはfizzbuzzだと思う。 自分は自明に感じなかったので解説ACになってしまった。地頭力がない。 i=coin[i]まで投げた、j=表のコイン数(状態)とす…

ABC130 E - Common Subsequence

https://atcoder.jp/contests/abc130/submissions/10200806 最初に文章を読んだ時unordered_mapでカウントするのかと思った(^^; 解説を読んだらLCS系DPだった。ということで、大前提としてLCSだと気づく必要がある。気づけなかった人は諦めよう(は?) …

今更ナップサック系DPの再勉強

Kyoto University Programming Contest 2019 B: ナップサック問題 https://atcoder.jp/contests/kupc2019/submissions/10107140 もっと早く復習するべきだったが、他にも学ぶアルゴリズムが大量にあって、今更なタイミングになってしまった。 ナップサックDP…

センター試験 数A

Educational DP Contest H: Grid 1 https://atcoder.jp/contests/dp/submissions/10084904 数Aの経験あれば書くだけ。ただし、初期化に若干の特殊ケースがある。通常、0行目と0列目は1で埋めるが、0行目と0列目に#があったとき#以降の0行目と0列目は0になる。

技術室奥プログラミングコンテスト#4 Day2 (diff2000未満)

自力で解けたの1問しかない。 再帰関数って理解できるの天才だけでは、という気分になった。 https://not-522.appspot.com/contest/5153769102770176 A: jumping!! https://atcoder.jp/contests/tkppc4-2/submissions/10063040 やるだけだけど、細かい条件に…

Educational DP Contest: G Longest Path

https://atcoder.jp/contests/dp/submissions/10552064 この問題は動的計画法の勉強というより幅優先探索の勉強という感じ。BFSが実装できればDP部分で苦労することはないと思う。 最短経路でなく辺の長さ最大を求めなければならないので、入次数を管理する…

ABC129 E - Sum Equals Xor

https://atcoder.jp/contests/abc129/submissions/9899468 感想: 頭が悪すぎて一生DP書けない 頭が悪すぎて最初 DP[i][j][k] := i桁目のビット組jが(00,01,10,11)でi-1番目のビットを加算したときキャリービットがkとなる組み合わせの個数 と定義して何も分…

F - Many Slimes

https://atcoder.jp/contests/abc140/submissions/9876531 「第X世代のスライム数は第X-1世代までのスライム合計に等しい」ということに気づいたら、あとは貪欲にスライムを割り当てれば良さそうと判断することが大切(ここの証明は難しいので勘に頼るしかな…

Nim

「山から石を交互に取る」という文章からNimという有名なアルゴリズムだと分かる。 grundy数が0なら後手必勝、0でなければ先手必勝。 https://atcoder.jp/contests/dp/submissions/9877090 各山の値を排他的論理和するのが典型テクニックになるが、今回は山…