2020年 6月 26日
まえがき
にゃーん
今日はスティッチの誕生日ですね。
ということで今日の一曲は...
大学ﾀﾞﾘ~
どうせやってないのに常にみはられてる気分。うぜえ
健康管理
大学のせいで絶不調ですね。
略して絶頂（は？）
何した
何したってかこれから何するだけど、まず2時間後に始まるフランス語の単語テストの勉強する。
具体的に
今日解いた問題
ABC145 E- All-you-can-eat
- [ﾁｮｯﾄﾖｸﾜｶﾗﾅｲ,最適化,分かったかも]
注文する料理の中で、時間が最も係るものを最後に注文すればいい。だから時間で昇順にソートしておくと良い。
さらに、ただのDPだけでは解けず、
rep(i,n){
rep(j,t){
chmax(dp[i+1][j], dp[i][j]);
int nj = j + p[i].first;
if(nj < t)
chmax(dp[i+1][nj], dp[i][j] + p[i].second);
}
int now = dp[i][t-1]+p[i].second; // ここが要
chmax(ans,now);
}
int now = dp[i][t-1]+p[i].second;
が重要アル
こいつが、一個だけ食べるのに係る時間を無視して食える。みたいなことを意味している。
だめだ、やっぱり難しいよ。
ABC133 E- Virus Tree 2
- [木,mod数え上げ]
解けた！！
どの頂点から色を決めて行っても一緒だろ（数え上げの経験から）
だから、テキトウに根を決めて、其の色を塗る。
BFSで次の頂点を見る。（この時の注目する頂点をvとする)
vの周りで、既に色が塗られている頂点を数えて、vをk-(今数えた数)通りで塗る。
って言うことをやっていきました。既に塗ったかどうかはboolの配列で管理しました。
int main() { int n, k; cin >> n >> k; rep(i,n-1){ int a, b; cin >> a >> b; --a, --b; // 0 -indexedにしておく。 G[a].push_back(b); G[b].push_back(a); } queue<int> que; que.push(0); ll ans = 1; vector<bool> seen(n+1,false); ans *= k; seen[0] = true; while(que.size()){ int p = que.front(); que.pop(); int now = k-1; // 頂点pは既に色を塗っているので、使える色が一色減る for(int i = 0; i < G[p].size(); i++){ // 頂点pに隣接する頂点で色が塗られている分だけ使える色が減る int x = G[p][i]; if(seen[x]){ now--; } } for(int i = 0; i < G[p].size(); i++){ int x = G[p][i]; // 頂点 x を塗る if(seen[x]) continue; seen[x] = true; ans *= now; ans %= mod; now--; que.push(x); } } cout << ans << endl; }
ABC132 E- Hopscotch Addict
- [有向グラフ,グラフの拡張,ちょうどゴール]
始めて見るタイプの難しいグラフの問題でした。写経ACです。
頂点sから頂点tに、どうにかして３の倍数回の移動でゴールしたい
そんなときは、頂点に状態を持たせて、1つの頂点を3倍に拡張してやるといいらしいです。
まぁ、ちょっと理解あれだけど、知識増えたってことでヨシ。
ABC113 D- Number of AMidakuji
- [DP,bit全探索,頑張れ]
dp[i][j] := ある高さ i の時点で、 左から j 番目のあみだに行くためのあみだくじの本数は何通りかんがえられるか(i + 1 以降のあみだには線を引かない時)とした。
(j は0-indexed)
こんな感じで、高さh,横からw番目のあみだに行くためには、
1. 高さhの時点でw-1番目とw番目をつなぐ線を書く。
2. 高さhの時点で,w番目とw+1番目をつなぐ線を書く
3. w番目の左にも右にも線を書かない
の3通りがあります。(端っこのときは2通り)
後は経路数え上げのノリでやりました。
(雑すぎるな…)
#include <bits/stdc++.h> using namespace std; using ll =long long; typedef pair<int,int> P; #define SORT(a) sort((a).begin(),(a).end()) #define rSORT(a) reverse((a).begin(),(a).end()) #define For(i, a, b) for(int i = (a) ; i < (b) ; ++i) #define rep(i, n) For(i, 0, n) #define debug(x) cerr << #x << " = " << (x) << endl; template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } //Write From this Line const int MAX = 510000; const int MOD = 1000000007; long long fac[MAX], finv[MAX], inv[MAX]; void COMinit() { fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for (int i = 2; i < MAX; i++){ fac[i] = fac[i - 1] * i % MOD; inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD; finv[i] = finv[i - 1] * inv[i] % MOD; } } long long COM(int n, int k){ if (n < k) return 0; if (n < 0 || k < 0) return 0; return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD; } ll dp[110][8]; const int mod = 1e9+7; int main() { COMinit(); ll h, w, k; cin >> h >> w >> k; --k; // 0-indexedにしてもろて dp[0][0] = 1; // 最初は0番目の縦線にいる。 for(int tate = 1; tate <= h; tate++){ for(ll tmp = 0; tmp < (1 << (w-1)); tmp++){ bitset<8> bit(tmp); debug(bit); // まず、1が2つ連続で並んでたらダメ。(不正なあみだくじ)<br> bool ok = true; For(i,1,w-1){ if(bit.test(i) && bit.test(i-1)){ // ダメ //cout << "dame" << endl; ok = false; } } if(ok){ vector<bool> check(w+1,false); // ある縦線が、隣接する縦線と繋がっているかどうか管理する<br> rep(i,w-1){ if(bit.test(i)){ dp[tate][i+1] += dp[tate-1][i]; dp[tate][i] += dp[tate-1][i+1]; dp[tate][i+1] %= mod; dp[tate][i] %= mod; check[i] = true; check[i+1] = true; } } rep(i,w){ if(!check[i]){ // 左からi番目の縦線が、左右の縦線と高さtateにおいて繋がってい無い時、上から行くしかねぇ dp[tate][i] += dp[tate-1][i]; dp[tate][i] %= mod; } } } } } cout << dp[h][k] << endl; }
解けてしまえば俺がやったことは全て正しいと思えるので気持ちいですね…（ﾌﾌﾌ
あとがき
おなかすいたー
以下は毎回記事に貼っているテンプレート
基本的に読書はTwitterで絡みのある人だけだと思いますが、僕のブログだけ見てるって人もいるかもしれないので、一応自己紹介っぽいことをしている記事を貼っておきます - 瑞々しぃにぼしの自己紹介(自己紹介の記事です)
