ABC118 に参加した話
問題
下記リンク
解答
A問題
cin >> a >> b; if(b%a == 0) cout << a+b << endl; else cout << b-a << endl;
B問題
mapに挿入、n個あるものをカウントして出力
int k[31], a[31][31]; map<int, int> mp; int main(void){ ios_base::sync_with_stdio(false); cin.tie(0); int n, m; string s; cin >> n >> m; REP(i, n){ cin >> k[i]; REP(j, k[i]){ int tmp; cin >> tmp; mp[tmp]++; } } int cnt = 0; for(auto itr = mp.begin(); itr!=mp.end(); itr++){ if(itr->second == n) cnt++; } cout << cnt << endl; return 0; }
C問題
A_iの中から小さい数を取り出してmodをとる これを繰り返し、できなくなったら終了 最小値を出力
const int INF = 1e9; int n; ll a[100100]; int mini = INF; int main(void){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n; REP(i,n) { cin >> a[i]; if(a[i] < mini) mini = a[i]; } bool f = true; while(f){ int tmp = mini; int cnt = 0; REP(i, n) { if(a[i]%mini != 0){ a[i] %= mini; } else{ cnt++; } } if(cnt == n) break; REP(i, n) mini = min((int)a[i], mini); } cout << mini << endl; return 0; }
D問題
(時間内に解けなかった) 考えたことは、DPで解けそう→dp[i][j]で長さ最大の文字数を入れればいけそう→経路の復元方法が分からない→貪欲 という流れで貪欲を書いたが、RE
正解は、string型の一次元DPに文字列ごと保持する 文字列長が最大となるものを管理しつつ、長さが同じ場合は辞書順比較で小さいものを常に管理する (他の方のコードを参考にさせていただきました)
//解説AC //https://atcoder.jp/contests/abc118/submissions/4292391 int num[]={0,2,5,5,4,5,6,3,7,6}; int a[10]; int n,m; void cng(string &t, string p){ if(t=="0") t=p; else if(t.size() < p.size())t=p; else if(t.size() == p.size()){ if(t<p) t=p; } } int main(void){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m; REP(i,m) cin >> a[i]; string dp[100100]; REP(i, n+1) dp[i] = "0"; dp[0] = ""; REP(i, n+1){ if(dp[i] == "0") continue; REP(j, m){ cng(dp[i+num[a[j]]], dp[i]+(char)(a[j]+'0')); } } cout<<dp[n]<<endl; }
感想
D問題、解けない問題ではないので、頑張って解きたかった... 引き続き精進します
学んだこと
- 文字列の辞書順比較はoperator >, <で可能
例えば '9' > '11' はtrueになる- (char)(a[j]+'0')でint->char変換