hamray's blog

主に競プロについて書きます

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

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

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

続きを読む

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
ゴールド到達!

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

続きを読む

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

手短に...
3完68位で国内予選を突破したみたいです。いまいち実感がないのですがアジア地区でも頑張りたいと思います。
国内突破したの意外すぎて、競プロのモチベ上がってきてしまった、どうしよう。卒論壊れる

一応やったことをまとめておく。
他チームと違ってずば抜けて強い人がいないので、とりあえずA~Cを解きたいねという話をしていた。そのため、A~Cを早く解けるように適当な年度のA~Cを解くみたいなのを2度ほどやった。
個人としては、DEFが解けるようにAOJ-ICPCあたりを適当に埋めた。
f:id:becnical:20201108152022p:plain
(結局Dを解けなかったのでこれが意味を成したかというと...)

2度目のアジア地区予選になるので前より良い結果を残せるように頑張りたい。

Cだけしか解いてないので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は文字固定までは一瞬だけど, そこから何も浮かばなかったので精進不足
Eはチームメイトに投げたので読んでない
Fは問題文がよく分からなかったのでそこまで考えてなかった(え?)

icpc1週間前ですよ!!

icpcが近いので本来のブログの使い方をしようと思う. といっても, 解いた問題の感想や気持ちなど雑多なことを書く.

この前の国内予選模擬は2完という結果でかなり悔しかったんですが, そんなこともあって研究をサボって永遠に精進をしている.
Cで詰まると大体調子が狂うのでちゃんと詰めていきたい. 枠減っちゃってるけど国内予選突破できればいいなあ...

AOJ1134 Name the Crossingを解いた.
文章がかなり分かりづらい気がしたが, 本質としては二部グラフ判定と到達性のチェックをすればよい. 二部グラフの判定はBFSでもDFSでも可. 蟻本の方法(DFS)は理解はしているが分かりづらいと感じているので, 普通にBFSで最短距離とってその偶奇を見ればいいと思う. 到達性判定はワーシャルフロイドで見ることができる.

文字列を頂点として与えてくる問題おおくないか?

AOJ2403 The Enemy of My Enemy is My Friendを解いた.
最大安定集合が枝刈り探索をすることで n \leq 40まで間に合うことは有名.
この問題もほぼ最大安定集合を求める流れと変わらないので枝刈り探索を考える. 何を枝刈りするかを30分くらい考えた. とりあえず, 現在の最大スコアをansとしたとき, 残りの全ての頂点を足したとしてもansに到達できないとき枝刈りをすると通った. 計算量が見積もれないので枝刈り全探索を要求される問題はかなり苦手. (てか得意な人いるんだろうか...)
半分全列挙でも解けるらしい. そういやこれもそうだった
atcoder.jp

サイコロのverifyをAOJ2703 サイコロスタンプで行った
いままで構文解析をstackのdfsで無理やり解いていたので再帰下降で解けるように何問か解いた
単純なやつは書けるけどstructを返すとかになると途端に分からなくなる.
→AOJ2255難しい、括弧をマージするイメージでやろうとしているがどうやって全通り試そうかな

AOJ2595 Cookie Counterを解いた.
Dが異常なのでN, Xだけで何かできないか考える. Nは高々2000なので, 高々2000回しか食べる機会はない. よって, DPでi回目で残りの枚数がjである組合せのテーブルを作っておき. (累積和で高速化する)
 \sum_{k=1}^{min(D, N)} {}_D \mathrm{C} _k * dp[k][0]を求めればよい.

10/31
AOJ2631 AOJ2342を解こうとしたがどちらも通らず無限に時間を浪費してしまった. まだ解けてないですhelp!! AOJ2342は枝刈りが本質っぽいけどどこを枝刈りするのかわからない. 座圧して新しいグリッドを作ってそのうえで試したが, 通らない. あまりに通らないのでサンプルを見たら座圧できないサンプルがあって, それでTLEになってた, どうしよう

AOJ2342の解説を見た. マス全体の状態を管理しなくても矛盾する候補は除外できるので, DPでよいらしい. DPは最初にやろうとして前に置いた鏡を貫通してしまうパターンをどう処理すればわからずやめてしまったしもう少し詰めるべきだったと反省.

11/3
なんか無をしていたら11月になってた
AOJのレーティングシステム, 月初めで更新されると思っていたがそうではなさそう
AOJ2681 いつかのABC-Fと同じ問題
AOJ2712 まず, 橋を渡ると戻れなくなることがわかるので二重辺連結成分分解をする. グラフは木になるので, 行き来可能な頂点の点数を取った後(同時に0にする), 根からの最大スコアをdfsで求めればよい.
AOJ1620 構文解析パートは単純だが, 短い論理式をどう生成するかとか作った論理式が有効かどうかをチェックするパートが分からなかったので解説をみた.
生成規則自体は再起的な構造をしているので, 16文字程度であれば高速に列挙することができる. これを元にあらかじめ2^2^4通りの結果についてメモしておき, 与えられる論理式に対して高速に求められるようにしておく

11/5
AOJ 2511 沈みゆく島
問題文がかなりわかりにくい. 初めに橋を架けるのをやめる時間 tを考える. これは前から見ていき, 初めて連結成分の数が1ではなくなったときを求めればよいので, UnionFindを使ってよしなにする.
よくよく考えると, 橋は何度も建設する必要はなく必要最低限の分だけを考えればよい. そのためtから0に逆順に頂点を増やし, 全体の最小全域木を構築していけば必要最低限の橋のコストを求められる.
求める答えは, tにおける最小全域木とtから逆順に見ていった時の橋のコストとなる.
(随時更新します)

AOJ1236 Map of Ninja House

問題リンク
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1236

問題文が長いので, 概要だけ説明すると, 深さとある頂点の辺の数が与えられるので, ここからグラフを復元する問題

解法
まず頂点数は正の数の総数であることが分かる.
すなわち, i番目のデータをみて, それが正ならば頂点番号を振り分ける.
逆に負であればその先に頂点は存在しないので, 巻き戻すみたいな処理が必要になる.

stackに頂点番号, 始点からの距離を持たせて, データが正であれば, その先頭と新しい頂点番号を辺でつなぐ.
データが負であれば, v[i] == dist[to] - dを満たすtoを探してtoとstackの先頭の頂点番号を辺でつなぐ.

データの読み取り後にドアの数がすべて見つかった頂点を先頭から除くことで巻き戻しの操作も可能なのでグラフを復元できる.

提出コード
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4947382#1