ABC 197 C ORXOR
問題
考えたこと
N=20なので全探索できそう。区間毎に分ける必要があるが、その方法として値にa[i]をORするか値を初期化してa[i]をORするかを用いた。
解説ではbit全探索があるが、あまり記述に慣れていないため、再帰的な手法を用いて実装。同じ区間に入れる、新しい区間を作るの2パターンで再帰的に実行していくので計算量はO(2N)となる。
最後に
全探索。綺麗に記述することができたが、bit全探索も何も考えずに記述できるようになりたい。
#include <iostream> #include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using namespace std; using ll=long long; using vi=vector<int>; using vll=vector<ll>; # define rep(i, n) for (int i = 0; i < (int)(n); i++) # define rep2(i,start,end) for (int i=(int)(start);i<(int)(end);i++) #define PRINT_AND_EXIT(value) { cout << value << endl; return 0; } #define all(a) (a).begin(), (a).end() // sort(all(a)) #ifdef LOCAL # include <debug_print.hpp> # define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__) #else # define debug(...) (static_cast<void>(0)) #endif int n,m,k,q,l,d,h,w,x,y; ll num,ans=INT_MAX,cnt; ll nl,num2,ans2,cnt2; string s,t; pair<int,int> pa; vi list,Ans; const int INF=2e9; constexpr ll INF2 = (1LL << 60); void dfs(int i,ll ans1,vll &a,int cnt1,ll ans2){ if(i==n){ ans=min(ans,ans1^ans2); return ; } dfs(i+1,ans1|a[i],a,cnt1,ans2); dfs(i+1,a[i],a,cnt1+1,ans2^ans1); return ; } int main() { cin>>n; vll a(n); rep(i,n){cin>>a[i];} ll ans1=a[0],ans2=0; int start=1,cnt1=0; dfs(start,ans1,a,cnt1,ans2); cout<<ans<<endl; }
ABC 322 E Product Development
問題
コストCnのN個中から好きなだけ選んで要素K個を全てP以上にする時の最小コストを求める問題 (0<N<100,1<K,P<=5)
考えたこと
Nが100なのでNの3乗の解の可能性を考える。また、最小コストを求めよということで最小全域木の問題にできないかと考える。スコア毎に0-5として、あるiを採用したら、そのスコアに移動できるような有効グラフを考えるも、いつそのiが採用されるかわからないため、グラフの本数がとても多くなることに気づき、やめる。次に、各iを全てpriority_queueに入れて、小さい順から選択し、別のjを足し合わせてまたpriority_queueに入れるという方針が思いつく。しかし、その間にコンテストがTimeUPとなってしいました。 解答としてはDPを使う方法があります。実際にK=2、P=3の場合を考えてDPテーブルを記述してみます。以下のような形になりテーブルの数はN*(P+1)Kとなっていることがわかります。そして各遷移にはK回の足し算が必要なので最終的な計算量はO(NK(P+1)K)となることがわかります。ナップDPのように採用する採用しないで値を計算していけばよかったのですね。
最後に
priority_queueでやってみたけどWAが6つ。ACできず悔しい。また、制約から計算量がどうなるか予想できない、かつどのあたりの計算まで許されるかわかっていなかったのでコンテスト中は考えがまとまらなかったです。。。
コード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; const static int NIL = -1; const long long INF = 1LL << 60; typedef long long ll; typedef unsigned long long ull; bool is_debug = true; int ini = 1000000001; ull mod = 1000000007; int main(){ int n, k, p; cin >> n >> k >> p; vector<int> c(n); vector<vector<int>> a(n, vector<int>(k)); for(int i = 0; i < n; i++){ cin >> c[i]; for(int j = 0; j < k; j++){ cin >> a[i][j]; } } int limit = 0; int power = 1; for(int i = 0; i < k; i++){ limit += p * power; power *= 10; } vector<vector<ll>> dp(n + 1, vector<ll>(limit + 1, INF)); dp[0][0] = 0; auto display = [](vector<vector<ll>>dp){ for(auto v : dp){ for(ll e : v){ cout << e << " "; } cout << endl; } cout << endl; }; auto calc = [k, p](int current, vector<int> add){ string s = to_string(current); while((int)s.size() < k){ s = "0" + s; } int result = 0; for(int i = 0; i < k; i++){ int sum = (s[i] - '0') + add[i]; sum = min(sum, p); result += sum * pow(10, k - i - 1); } return result; }; /* int temp = 123; vector<int> v = {2, 4, 0}; cout << "--------------" << endl; cout << calc(temp, v) << endl; cout << "--------------" << endl; */ for(int i = 0; i < n; i++){ for(int j = 0; j < limit + 1; j++){ if(dp[i][j] == INF)continue; dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]); int ny = calc(j, a[i]); dp[i + 1][ny] = min(dp[i + 1][ny], dp[i][j] + c[i]); //cout << ny << endl; //cout << dp[i + 1][ny] << endl; } } //display(dp); ll result = dp[n][limit]; if(result == INF){ cout << NIL << endl; }else{ cout << result << endl; } }
ブログ始めてみました！！
初めまして！
ブログを始めることにしました。まず簡単に自己紹介させてください。
・自己紹介
・なぜ始めようと思ったか
最近、研究室の先輩からの勧めで競技プログラミングに触れる。競技プログラミングにはまる。わからない問題をネットで検索する。多くの人が解説を紹介していることに気づく。そこで、自分も他の人の役に立つような記事が書きたいと思った、という感じです！
そのため、これから書きたいと思っている記事としては
・AtcoderのABCで出題される問題の解説
・進捗報告(レートの色が変わったなど)
です。
強い人と比較すると能力、経験は劣りますが色々な解説があるとその分理解しやすくなると個人的には感じていますので、そういう点は気にせず解説記事を上げられたらと思っています。
拙い文章になると思いますが、よろしくお願いします。間違いなどありましたら気軽にコメントしてくださると幸いです。
