2020年 5月 30日
まえがき
なんか書きてえけどなあ、。何書こうかな
あーーーーーーーーーー今日はね、お家のお掃除をしたよ
野村プロコン
ﾚｰﾄｻｶﾞｯﾀｱｱｱｱｱｱｱｱｱｱｱｱｱｱ！！！！！！！！！！！！！！！！！！！１ 5月中に水色の目標は…だめでした
いやまぁ、これは俺が悪い。5月の前半全く競技プログラミングやってなかったもん。
健康管理
う。。。健康
何した
お部屋掃除等など
具体的に
!!!#I!#FJLDSA!!!
今日解いた問題
ABC089 D- Practical Skill Test
[累積和,コスト,割った余り]
LとRが与えられた時、L -> R のコストは L % D を K とした時（ただし,K = 0のときはK = Dとする), K -> R のコストから K -> L のコストを引いたものとして求められる。
(A -> B -> C という経路があれば、BとCの距離はAとCの距離引くAとBの距離的な）
これを使えば、
D = 2のとき、
1 -> 3 -> 5 -> 7 -> 9 と瞬間移動するときのコストを
1 -> 1, 1 -> 3 , 1 -> 5, 1-> 7 , 1->9のコストをメモする。
2 -> 2, 2 -> 4, 2 -> 6, 2 -> 8 のコストをメモする。
この計9個(H * W個）の配列を用意してあげれば、各L,Rに対して1回の計算で求められる。
まず僕が書いた汚いコードがこちら
#include <bits/stdc++.h> using namespace std; using ll =long long; #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; using P = pair<int,int>; //Write From this Line int main() { int h, w,d; cin >> h >> w >>d; map<int,P> mp; rep(i,h){ rep(j,w){ int a; cin >> a; mp[a] = {i,j}; } } vector<int> cost[d+1]; for(int i = 1; i <= d; i++) { cost[i].push_back(0); int ind = i; int bef = 0; while(ind + d <= h * w){ P from = mp[ind]; P to = mp[ind + d]; int to_next = 0; to_next = abs(from.first - to.first) + abs(from.second - to.second); //debug(to_next); cost[i].push_back(bef + to_next); bef += to_next; ind += d; } //for(auto x:cost[i]){ // cout << x <<" "; //} cout << endl; } int q; cin >> q; rep(i,q){ int l, r; cin >> l >> r; int root = l %d; if(root == 0)root+= d; // cost[root]を見る // l , rまで行くまでに何回か int toL = (l + d - 1) / d - 1; int toR = (r + d - 1) / d - 1; // debug(toL); // debug(toR); // debug(cost[root][toL]); // debug(cost[root][toR]); cout << cost[root][toR] - cost[root][toL] << endl; } }
やってることは、
cost[1] = {1->1のコスト, 1->3のコスト, 1->5 のコスト, 1->7のコスト, 1 -> 9 のコスト}
cost[2] = {2 -> 2のコスト, 2 -> 4 のコスト, ..., } というふうな配列を作る。
で、7 に行くためのコストはcost[1]の何番目だ？みたいなのを考えてやってました。
でも、そもそも7にいくためのコストは1 から 7 に行くだけで、 2 から 7 には行かないから,cost[7]に1->7へのコストを持たせればいいじゃん。って気づきました。
そうして改良舌コードが次です。
#include <bits/stdc++.h> using namespace std; using ll =long long; #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; using P = pair<int,int>; //Write From this Line int main() { int h, w,d; cin >> h >> w >>d; map<int,P> mp; rep(i,h){ rep(j,w){ int a; cin >> a; mp[a] = {i,j}; } } ll cost[h*w+1]; for(int i = 1; i <= h * w; i++) { if(i <= d) { cost[i] = 0; continue; } cost[i] = cost[i-d] + abs(mp[i].first - mp[i-d].first) + abs(mp[i].second - mp[i-d].second); } int q; cin >> q; rep(i,q){ int l, r; cin >> l >> r; cout << cost[r] - cost[l] << endl; } }
水色パフォの問題が自力で解けると嬉しいですね。嬉しいです。
SoundHound Inc Programming Contest2018 C- Ordinary Beauty
[期待値の線形性]
なんや難しそうな問題だなぁ…
隣り合う二項について美しさを獲得できるかどうかで求めていけないかな…うんぬん…とかしていて結局解けないことが分かりました。
解説PDFを見て1mm理解,その後、数学/競プロメモこの方の記事を読んで1cm位理解しました。 なるほど。まぁ、二項間について着目しようという発想はヨカッタですね。各2項間について、得られる美しさの期待値を求める。他の2項間についても、美しさを得られる期待値は同じなので、存在する二項間がm-1個あるから、各二項間の美しさの期待値 * (m-1)が答え。ふうん。面白いじゃん。 期待値の線形性ね。なるほど。
え、期待値の線形性ってなんだっけ
和の期待値は期待値の和に等しい。
ふむ…？ つまり、各二項間で得られる美しさの期待値をx,全体の期待値をXとすると、 $ X = x + x + x +... (xがm-1個) $ みたいなノリか。
NOMURA プログラミングコンテスト2020 C- Folia
[二分木,木の構築?,葉の数]
ｲﾔｱｱｱｱｱｱｱｱｱｱｱｱｱｱｱｱｱｱｱｱｱｱｱｱｱｱｱｱｱｱｱｱｱｱｱｱｱｱｱｱｱｱｱｱ 解説見ました。 （コンテストで解けなかった問題を復習したのも超久しぶり) なるほど… 深さNのところから順に、あり得る深さiの頂点の区間というものを求めていけばいいのか。天才だな。
あああああああああああああああああ レート挙げてええええええええ 競技プログラミングするぞ
あとがき
ねむいから書かない
以下は毎回記事に貼っているテンプレート
基本的に読書はTwitterで絡みのある人だけだと思いますが、僕のブログだけ見てるって人もいるかもしれないので、一応自己紹介っぽいことをしている記事を貼っておきます - 瑞々しぃにぼしの自己紹介(自己紹介の記事です)
