2020-12-01

Codeforces Round #456 (Div. 2) D. Fishes

問題リンク
codeforces.com
問題概要
n*mのグリッドが与えられる. ここにk匹の魚を配置する(各グリッドに高々1匹). このときグリッド上で等確率でr*rの正方形を指定したとき, 魚の個数の期待値を最大化したい. この値を求める.

制約
$1 \leq n, m \leq 10^5$
$1 \leq r \leq min(n, m)$
$1 \leq k \leq min(n×m, 10^5))$

解法
任意の魚について, 現れる回数の総和を最大化したいので, r*rのグリッドの重複が大きい順にk個取る問題と言い換えることができる.
重複数は場合分けをすることでO(1)で求められるので, 始点を(n/2, m/2)としてPriority_queueを使って大きい順に取っていけばよい.

提出コード
Submission #100117320 - Codeforces

2020-11-26

CODINGAME FALL CHALLENGE 2020 参加記

CodinGame FALL CHALLENGE 2020に参加しました。
https://www.codingame.com/contests/fall-challenge-2020

結果は全体267位/7011, 国内67位/320でした。
初めてCodinGameのコンペに参加しましたがゴールドに到達できて嬉しいです。日本人の参加者が多く、良い刺激になりました。

f:id:becnical:20201126022002p:plain — ゴールド到達！

以下にコンペの内容とやったことと反省点を書きます。

2020-11-07

ICPC国内予選2020に参加しました

3完68位で国内予選を突破したみたいです. いまいち実感がないのですがアジア地区でも頑張りたいと思います.

やったこと
ずば抜けて強い人がいないので, A~Cを早く解けるように適当な年度のA~Cを解くみたいなのを2度ほどやった
個人としては、DEFが解けるようにAOJ-ICPCあたりを適当に埋めた
f:id:becnical:20201108152022p:plain

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;
}