B - Neutralize
問題概要
個の数列が与えられる。個の連続する数字を選んで0にできる。の最大値を求めよ。
B - Neutralize
解法
動的計画法。
が最大値となる数列に含まれるか、あるいは0になるか二通り存在するので、
番目の数字を使った時までの最大値
番目の数字を使わない場合の最大値
とする。
更新は
番目の数字を使うとすると、直前まで0になった場合が存在するので
同様に、使わなかった場合と、の数字を含めてちょうど個の数字を使った場合があるので
最初状態が3通り(使う、0になる列に含まれる、使わない)だと思ってたんですが、使う場合と使われない場合だけで漸化式を書けてしまってアって感じでした。
#include<bits/stdc++.h> using ll = long long; #define int ll #define rep(i,n) for(int i=0;i<n;i++) #define INF (sizeof(int) == 4 ? (int)1e9:(int)1e18) using namespace std; template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return vector<Value>(head, v); } template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return vector<decltype(inner)>(x, inner); } signed main(){ int n; int k; cin >> n >> k; auto dp = vectors(2,n,-INF); vector<int>v(n); for(auto & e : v) cin >> e; dp[0][0] = v[0]; dp[1][k-1] = 0LL; rep(x,n){ if(x){ dp[0][x] = max(dp[0][x-1], dp[1][x-1]) + v[x] ; if(x-k>=0)dp[1][x] = max(dp[1][x-1],dp[0][x-k]); } } cout << max(dp[0][n-1],dp[1][n-1]) << endl; }
AOJ Sum of Integers Ⅱ
改めてみると解けるようになっていたのでメモ
解法
をやります。
数字iを見ているときに、k個の数字を使っていて、和がjのときの場合の数
でも解けますが、
k個の数字を使ってていて、和がjの時の場合の数
としても解けます。dpの更新を後ろから行うと、異なる数字だけを使う数え上げができます。
参考になるかもしれない記事。
#include<bits/stdc++.h> using ll = long long; #define int ll #define rep(i,n) for(int i=0;i<n;i++) using namespace std; template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return vector<Value>(head, v); } template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return vector<decltype(inner)>(x, inner); } signed main(){ int n,s; auto dp = vectors(11,1001,0LL); dp[0][0] = 1; for(int num = 0; num <= 100;num++){ for(int k = 9; k>= 0;--k){ for(int crt = 0; crt <= 1000;crt++){ if(dp[k][crt] != 0 and crt + num <= 1000){ dp[k+1][crt + num] += dp[k][crt]; } } } } while(cin >> n >> s,n+s){ cout << dp[n][s] << endl; } }
Macのシステム容量が極端に増えるのをどうにかしたい。
題名通りですが、解決できたので自分用にメモ。 実行は自己責任でお願いします。
結論からいうとビルドファイルのキャッシュやiOSシミュレーターのキャッシュを削除すると40GBほど容量が増えました。
不可視ファイルを目に見えるようにする。
Terminalに貼り付けます。
defaults write com.apple.finder AppleShowAllFiles true; killall Finder
逆の動作(不可視ファイルを見えなくする)場合は
defaults write com.apple.finder AppleShowAllFiles false; killall Finder
FInderでサイズを確認できるようにする。
ファインダーで⌘+Jを押し、[すべてのサイズを計算]にチェックを入れて少し待ちます。
これで具体的にどのディレクトリが容量を消費しているかわかります。
~/Library/Developper に原因があると下の解決策が有効です。
キャッシュを消す
sudo rm -rf ~/Library/Developer/Xcode/DerivedData
これ以外にも、こちらでより詳しく紹介されてます。
visualstudioをダウンロードして削除したことがある方は関連ファイルが残っていることがあります。
docs.microsoft.com
これだけでもかなり容量が増えます。IDEってこんなに重いのか。。。と感じました。
ACPC2018-参加記-
今年も参加しました。
Day 0
移動中にHaskellをやっていました。関数型言語をやりたい&楽しそうだったのですが意外とむずかしい。。。継続していやっていきたい。
景色は相変わらずど田舎。 晩御飯はマルモ食堂で食べました。美味しかった。
Day1
ジャッジをやりました。大悪魔さんの自己紹介が面白かったです。ヅの食堂がおしゃれで美味しかったのが印象的でした。
Day2
imulanさんとnadareさんとチームを組みました。
AとCを解いてEとFの考察を行いました。
・C問題は足してmodを取れば嬉しいなぁとすぐ気づいたんですが、バグを仕込みそうだったのでimulanさんに確認してもらいながらAC
・F問題は似たような問題を見たことがあったので、nadareさんと相談しながらDijkstraやるだけでは?みたいな気持ちになる。
・imulanさんに↑の概要を伝えると、辺のコストに単調性がないと指摘を受ける。自分の考察力の無さと詰めの甘さを思い知りました。imulanさんが通してAC
・E問題はnadareさんと一緒に数学をやりました。自分一人でやってると詰められないところもnadareさんがしっかり詰めてくださってAC。途中は苦しかったんですが結果オーライ。
Day2 懇親会
・c7c7さんやprdさん、nadareさん、北大*1さん、UTの方と一緒のテーブルになりました。
・お酒を飲む方が多くてびっくりしました。初めてお会いしたとは思えなぐらい喋りました。
・競プロの懇親会だけあって、プログラミングのことが好きな方が多かったので、競プロ以外のプログラミングのことについても話しました。自分より強い方の話を伺う機会は多くないので貴重な体験でした。
Day3
tomaさんとshotさんでチームを組みました。
AとDと戦犯を担当しました。
・A問題を通すまで55分4WAをしました。引退案件です。
・DはDPがDijkstraかなぁと思った。DPはバグらせた思い出しかないので、shotさんに方針を確認してもらって拡張Dijkstraを書くがWA。
・d[0][0]の初期化を忘れていることに気づいてAC。
・shotさんが虐殺としていたBとEをACしてプロ。コーディング力見習いたいです。
・TomaさんはFをこれはA~Fの中で一番簡単といってAC。想定解ではない方法らしいです。
・最後の一時間にD,E,Fがポンポン通ったのが印象的でした。
最後に
三度目の参加となりましたが、とても楽しかったです。2年前と比べると成長しているようなしていないような。。。
チームを組んでくれた皆様、会津大学・北海道大学の皆様、ありがとうございました。
後期もしっかり精進していきたいと思います。
*1:実はこのときまで同学年の北大競プロerを一人も知りませんでした。
Mujin Contest D - うほょじご
問題文
解く前に考えていたこと
・絶対これ考察するだけでしょwと思ってたら違った。
・規則性を見出すことが全くできなかった。シュミレーションの選択肢を除外した。
正解
・解答を見ると閉路を探し出すような解答になっていたが、わからなかったのでメモ化再起で解いた。
・なので、2次元配列で状態を持てる。
・無限ループに突入する部分の判定が勉強になった。
if(visit[x][y] > 0) return true; if(visit[x][y] < 0) return false; int tx = x,ty = y; visit[x][y] = true; x < y ? x = rev(x) : y = rev(y); x < y ? y = y - x : x = x - y; if(x <= 0 or y <= 0){ visit[tx][ty] = -1; return false; } visit[tx][ty] = (dfs(x,y) ? 1 : -1); return visit[tx][ty] == 1;
まず、に対し、に1を一時的に格納する。
に対して操作を行った後、閉路に突入する(つまり、に戻ってくる)と、格納されている1が帰る。
そうでない場合は途中で-1に更新され、その組は解になりえない事がわかる。
#include<bits/stdc++.h> using ll = long long; #define int ll using namespace std; int rev(int num){ auto s = to_string(num); reverse(begin(s),end(s)); return stol(s); } signed main(){ int n,m; cin >> n >> m; int ans = 0; vector<vector<int>>visit(1000,vector<int>(1000,0)); function<bool(int,int)> dfs = [&](int x, int y) -> bool{ if(visit[x][y] > 0) return true; if(visit[x][y] < 0) return false; int tx = x,ty = y; visit[x][y] = true; x < y ? x = rev(x) : y = rev(y); x < y ? y = y - x : x = x - y; if(x <= 0 or y <= 0){ visit[tx][ty] = -1; return false; } visit[tx][ty] = (dfs(x,y) ? 1 : -1); return visit[tx][ty] == 1; }; for(int i = n; i >= 1; --i){ for(int j = m; j >=1;--j){ ans += dfs(i,j); } } cout << ans << endl; }
ABC106 AtCoder Express 2
解く前に考えていたこと
区間を数える典型なので、解き方は雰囲気で知ってた(実装はしてません)。
実装の際に盛大にバグらせたので戒めとして書きました。
解法
+ クエリ先読みのオフラインアルゴリズムというらしい
#include<bits/stdc++.h> using ll = long long; #define rep(i,n) for(int i=0;i<n;i++) #define erep(e,v) for(auto && e :v) #define all(in) in.begin(), in.end() #define INF (sizeof(int) == 4 ? 1e9:1e18) using namespace std; template<class T> void join(T a){for(auto itr :a){if(itr != *a.begin())cout << " "; cout << itr;} } using pii = pair<int,int>; using piii = pair<int,pii>; int bit [1000] = {},n; int sum(int i){ int s = 0; while (i > 0) { s += bit[i]; i -= i & -i; } return s; } void add (int i,int x){ while (i <= n) { bit[i] += x; i += i & -i; } } signed main(){ int m,q; cin >> n >> m >> q; vector<piii>v( m + q); rep(i,m+q) { int a,b; cin >> a >> b; piii temp; temp.first = a, temp.second.first = b; temp.second.second = i; v[i] = temp; } sort (all(v),[](auto const x,auto const y) { return ( x.second.first < y.second.first or (x.second.first == y.second.first and x.second.second < y.second.second) ); }); int ans[100000] = {}; erep(e,v){ int left = e.first; int right = e.second.first; bool isQuery = e.second.second >= m; int index = e.second.second - m; if (isQuery){ ans[index] = sum(right) - sum (left - 1); } else { add(left, 1); } } rep(i,q) cout << ans[i] << endl; }
9/6 追記
一応segtreeの解答も載せておこうかな
https://beta.atcoder.jp/contests/abc106/submissions/3096327
ABC038 D - プレゼント
問題概要
解く前に考えていたこと
・AOJのマトリョーシカと非常に似ている。
・ただし、この問題は制約がで解は部分点しか取れない。
・LISであることは間違えないので、比較関数を書き換えて蟻本にあるのLISを書くがWA
・途中でpair型dpを更新していた。
正解
まず前提として、プレゼントがプレゼントの中に梱包される条件とは、
> > が成立することである。
プレゼントの順番は自由に並びかえることができるので、ソートして考えるのが良い。
を昇順にソートして に関してLISを考えればうまくいきそう。
以下,二分探索で、番目の要素の更新位置を探す解法を考える。
・番目の要素でLISの配列を上書きする場合を考える。ただし、上書きされる要素は番目()とする。
・このとき、が成り立っていると、となっているため、上書きできない。(直感的に説明すると、番目の要素の方が番目の要素より条件が厳しい)
逆に言えば、のときとなっていれば、通常通り更新することができる。
追記
6/10 別解で解いたので、その解法を載せる.
通常のLISと同じく、lower_boundを用いて更新していく(ただし、今回はpair型のdp)。
更新する位置は、以上の要素がある部分である。
さて、この問題でより真に大きいとは、 && が成り立つことである。
さらに, 以上とは、 or となる。なので、適当に二分探索して置き換える位置を探す。
この定義を採用すると、同値のまたはの更新時に厄介なことになる。よって最初の同じく、比較関数をよしなにしてソートすること。
lower_boundといっておきながら普通の二分探索の理由は、また比較関数を書き換えないと行けないので。(比較関数を書き換えたver)
#include<bits/stdc++.h> using namespace std; using Int = long long; constexpr Int inf =1e18; template<class F, class T> auto minimize(T imin,T imax,F &f){ while(imax - imin > 1){ T mid = imin + (imax - imin)/2; if(f(mid)) imax = mid; else imin = mid; } return imax; } int main(){ int N; cin >> N; vector<pair<Int,Int>>v(N); for(auto& p : v) cin >> p.first >> p.second; sort(v.begin(),v.end(),[&](const auto& l, const auto& r){ if(l.first == r.first) return l.second > r.second; return l.first < r.first; }); pair<Int,Int>p; vector<pair<Int,Int>>dp(N,make_pair(inf,inf)); auto f = [&](int mid){ return dp[mid].first >= p.first or dp[mid].second >= p.second; }; for(int i = 0; i < N; ++i){ p = v[i]; int id = minimize(-1,N - 1,f); dp[id] = p; } cout << count_if(dp.begin(), dp.end(), [&](auto p){ return p != make_pair(inf,inf); }) << endl; }