2月24日精進録
まえがき
なんか、記事の頭についてる謎のコード置いとけば数式が書きやすくなるって話だったのに、入れても数式がちゃんとなってないんだけど…
わけわからん
わけわからんけど治すのめんどくさいから頑張って読んでね。
最近は、生活リズムを12:00に寝て、22時頃に起きるようにしようと思っているのですが、 そうする場合って、ブログを書く時間が22:00から12時間経った10:00頃になるんですよね。その場合、ブログの記事のタイトルを22:00に起きた日にするかそれともその次の日にするか悩むんですよね…
基本的には朝起きて夜ふかししたら寝るまでがその朝起きた日付だと考えるじゃないですか(考えるんですよ) でも夜に起きた場合って昼が夜じゃないですか…???
何言ってるのかよくわからないね
今日学んだこと
繰り返し二乗法最高。
AtCoder 解説動画のmintは便利。ライブラリに入れようね。
今日(?)解いた問題
ABC104 D-We Love ABC
[動的計画法、数え上げ,mod]
青パフォで少しむずかしめの問題。ABCが何組あるか。みたいな…。 実質写経ACみたいな感じ。
コメント
dpの問題は、どういう状態が有るかを考えればいいらしい。
この問題だと,dp[i][j] := i文字目まで見たときに、状態がjであるのは何通り有るか。 というのを用います。
n = s.size() 文字の中からどの3文字を使ったABCを数えるか。っていうノリなのですが、 - 状態0:= まだ何も決まっていない状態 - 状態1:= Aまで決めた状態 - 状態2:= Bまで決めた状態(つまり、後Cでどれを使うか決めればABCの数が増える) - 状態3:= Cまで決まった状態。
このように状態を考えることで、最終的に出力する答えは dp[n][3] := n文字(つまり全部の文字)見たときに、Cまで決まった状態が何通りあるか。
当然ながら、A、B,Cの順番に決めて行かないと行けないので、$$ dp[i]0 >= dp[i][1] >= dp[i][2] >= dp[i][3] $$ ですね(別にどうでもいいです)
i文字目を見ていくとき、'?'だったら、状態を維持したまま、その状態の数はi-1文字目まで見たときの3倍の値にすることが出来ます。
また、i文字目が'B'だった場合、dp[i-1][1](i-1文字目まで見て、Aまで決めた数)をdp[i][2]に足すことが出来ます。 こんな感じのことをシていけば求まりマス。
すごい!!
ABC156 D- Bouquet
[mod,nCm,繰り返し二乗法、数え上げ]
可能な花束の作り方は $$ 2n - 1 - nCa - nCb $$ です。 2n - 1 … n種類の花束それぞれについて、選ぶ、選ばないのふたとおりがあるから。そして0本の花束はありえないので、n種類どれも取らないという1種類を抜く。
さらに、a,種類選ぶ、b種類選ぶは禁止されているのでそれをひきます。 よって、$$ 2n - 1 - nCa - nCb $$を求めればいいです。
コメント
繰り返し2乗法かっけえ!!!
mint f(int n) { // 2 ^ n を求める if(a==0) return 0; mint res = f(n/2); res *= res ; /*mint res = f(n/2) * f(n/2);とすると、呼び出し回数が増えそうなのでres *= resというふうにした if(n % 2 ) res *= 2 ; return res ; }
まあ、res ×= res としたところで、繰り返し2乗法でan を求めるのは O(log n)なので大した改善にならないのでどうでも良さそうですよね。 解説ACです。なるほどこうやって求めればよかったのか。
花の選び方が全部で2nということに気が付きませんでした
今回の問題はnがとても大きくなることがあって、COMinit()じゃ対応出来ないことだそうです。 5C2 = 5 * 4 / (2 * 1)みたいに求めるの大事。(僕はnCm = n!/(m! (n-m)!)というのをそもそも覚えていないのですが)
こういう問題、そろそろ本番で通してあたたまれるようになりたいです。
AGC003 B- Simplified mahjong
[貪欲法]
なんか説明しようと思ったけど難しい。 1から順にペアを作っていくのが良くて、まず1だけでペアを作る。そして1が余ったなら(1枚しか余る枚数としてありえるものはない)、2とペアを作れるなら作る。
1が1枚余って、2が4枚あるとき、1と2でペアを作ったほうが良いです。
すると、次に2は1ペア作れて1枚余ります。
このように、1枚余らせておくことで自身(2)以上である数3とのペアを作ることが出来ます。 (つまり貪欲法で勝てる)
最大化出来ない例として、1が3枚、2が4枚、3が2枚あったとき、 2で2ペア作ってしまうようなものはアホです。
1で1ペア,3で1ペア、合計4ペアしか出来ません。バーカバーか
ABC054 C- One-Stroke Path
[グラフ,無向グラフ,簡単グラフ,全順列]
簡単ではありません… グラフの道順検索に慣れる問題的なノリですね。自力AC出来てうれしいです。 1から初めて、n頂点全部通ることが出来るか…ってね
同じ頂点を通ったらダメ、というのを、わざわざ頂点kは通ったから…って感じに保持するのはだるいです。 今回 n <= 8ですので、(8-1)!個の通り方を全部見ていけばいいです。
ねくすとぱーみゅてーしょん!!
あとがき
水色なりたいなりたいなりたいなりたい!!!!
杏林堂の餃子めちゃくちゃ美味いです。最高。