ICPC国内予選2020に参加しました
3完68位で国内予選を突破したみたいです. いまいち実感がないのですがアジア地区でも頑張りたいと思います.
やったこと
ずば抜けて強い人がいないので, A~Cを早く解けるように適当な年度のA~Cを解くみたいなのを2度ほどやった
個人としては、DEFが解けるようにAOJ-ICPCあたりを適当に埋めた
Cだけを解きました. だいたい20秒くらいで出力が終わる
ll ans ; map<ll,ll> factorize(ll x) { map<ll,ll> res; for (ll i = 2; i * i <= x; i++) { while (x % i == 0) { x /= i; res[i]++; } } if (x != 1) res[x]++; return res; } void dfs(ll a, ll b, ll c, vector<ll>& v, int idx, map<ll,ll>& mp){ if(idx == v.size()){ ans = min(ans, a+b+c); return; } for(int i=0; i<=mp[v[idx]]; i++){ for(int j=0; j<=mp[v[idx]]-i; j++){ int k = mp[v[idx]]-i-j; ll na = a, nb = b, nc = c; for(int t=0; t<i; t++){ na *= v[idx]; } for(int t=0; t<j; t++){ nb *= v[idx]; } for(int t=0; t<k; t++){ nc *= v[idx]; } dfs(na, nb, nc, v, idx+1, mp); } } } int main() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(6); ll p; while(cin >> p, p){ if(p == 1){ cout << 3 << endl; continue; } auto mp = factorize(p); ans = 1e17; vector<ll> tmp; for(auto e: mp){ tmp.push_back(e.first); } dfs(1LL, 1LL, 1LL, tmp, 0, mp); cout << ans << endl; } return 0; }
Dは文字固定が方針の一つとして浮かびましたが, それ以降考察が進まなかったので精進不足でした.
2度目のアジア地区予選になるので, 前より良い結果を残せるように頑張りたいです