AtCoder ABC #145 E All-you-can-eat

問題

E - All-you-can-eat

解説

他の回答を見つつ、公式解説の解法２に沿って回答を作成。

DP難しい。。。

fn solve(t: usize, abs: Vec<(usize, usize)>) -> usize {
    use std::cmp::max;

    let mut abs = abs;
    abs.sort_by_key(|x| x.0);

    let mut dp = vec![0; t + 3001];

    for &(a, b) in abs.iter() {
        for i in (0..t).rev() {
            dp[i + a] = max(dp[i] + b, dp[i + a]);
        }
    }

    dp.into_iter().max().unwrap()
}

AtCoder ABC #139 F - Engines

問題

F - Engines

解説

公式解説結構長めに書いてあるけど実装としては

1. f64.atan2()で角度を求めてソート
2. 連続的に取りうる組み合わせを全て試す

これで で解ける

fn solve(xys: Vec<(i64, i64)>) -> f64 {
    let n = xys.len();
    let mut xys = xys;

    xys.sort_by(|&(x1, y1), &(x2, y2)| {
        let p1 = (y1 as f64).atan2(x1 as f64);
        let p2 = (y2 as f64).atan2(x2 as f64);

        p1.partial_cmp(&p2).unwrap()
    });

    let mut ans = 0.0;

    for i in 0..n {
        let mut x = 0;
        let mut y = 0;

        for j in 0..n {
            let k = (i + j) % n;
            let (ax, ay) = xys[k];
            x = x + ax;
            y = y + ay;

            let r = ((x * x + y * y) as f64).sqrt();
            if ans < r {
                ans = r;
            }

            if (i + j + 1) % n == i {
                break;
            }
        }
    }

    ans
}

AtCoder ABC #136 F - Enclosed Points

F - Enclosed Points

問題

TODO

BIT

解説の前に今回のBITの使いどころについて軽く整理。

いまx座標で昇順に並べた点(例: ) があるとする。

BITを利用すると各点を原点として特定の象限に含まれる点の数を順に求めることができる。

例えば第3象限の場合は以下をx座標昇順に繰り返せば良い。

1. BIT.sum(対象点のy座標)が点の第3象限に含まれる点の数となる
2. BIT.add(対象点のy座標, 1)

第2象限のばあいは例の場合であれば1.が対象のx座標 - BIT.sum(対象点のy座標)となる。 (x座標と対象点の左側にある点の数が一致するため)

第1,4象限の場合は最初にBITの葉を1で初期化しておきBIT.add(対象点のy座標, -1)とすることで同様に求めることができる。

実装

BITの実装は以下の通り。スニペットにしてある

#[derive(Debug)]
struct FenwickTree {
    n: usize,
    bit: Vec<isize>,
}

impl FenwickTree {
    fn new(n: usize) -> Self {
        FenwickTree {
            n: n,
            bit: vec![0; n],
        }
    }

    // [0, i)
    fn sum(&self, i: usize) -> isize {
        let mut s = 0;
        let mut i = i as isize;
        while i > 0 {
            i -= 1;
            s += self.bit[i as usize];
            i &= i + 1;
        }
        s
    }

    fn add(&mut self, i: usize, x: isize) {
        let mut i = i;
        while i < self.n {
            self.bit[i] += x;
            i |= i + 1;
        }
    }
}

解説

コードは以下の通り

• p2に予め2の累乗のMODを記録しておく
• Vec::binary_search()を用いて各点の座標を0〜N-1に圧縮
• 2つのBIT（左象限用、右象限用）を作成し右象限用は1で初期化
• r1〜r4は対象点を原点とした各象限の点数
• pr1〜pr4は各象限の点が取りうる場合の数（の剰余）

あとは公式解説に従って2⁴通りについて場合を求めて足し合わせている。

これでACにはなるのだが、長い、長すぎる。他の回答はこれほどは長くはないので、何かしらもう少し効率よく記述できると思われるがとりあえずTODOとしておく。

static MOD: isize = 998244353;

fn solve(xys: Vec<(isize, isize)>) -> isize {
    let n = xys.len() as isize;
    let mut p2 = vec![0 as isize; 200002];
    p2[0] = 1;
    for x in 1..p2.len() {
        p2[x] = (p2[x - 1] * 2) % MOD;
    }

    let mut sortedx = xys.iter().map(|&(x, _)| x).collect::<Vec<_>>();
    sortedx.sort();

    let mut sortedy = xys.iter().map(|&(_, y)| y).collect::<Vec<_>>();
    sortedy.sort();

    let mut compressed = vec![(0, 0); xys.len()];
    for (i, &(x, y)) in xys.iter().enumerate() {
        let ix = sortedx.binary_search(&x).unwrap() as isize;
        let iy = sortedy.binary_search(&y).unwrap() as isize;
        compressed[i] = (ix, iy);
    }

    compressed.sort_by_key(|&(x, _)| x);

    let mut lft = FenwickTree::new(xys.len());
    let mut rft = FenwickTree::new(xys.len());
    for i in 0..xys.len() {
        rft.add(i, 1);
    }

    let mut ans = 0;

    for (x, y) in compressed {
        let r3 = lft.sum(y as usize) as usize;
        let r2 = (x - r3 as isize) as usize;
        let r4 = rft.sum(y as usize) as usize;
        let r1 = (n - x - 1 - r4 as isize) as usize;

        let pr1 = p2[r1] - 1;
        let pr2 = p2[r2] - 1;
        let pr3 = p2[r3] - 1;
        let pr4 = p2[r4] - 1;

        // 各象限と自身のみ
        ans += pr1 + pr2 + pr3 + pr4;
        ans %= MOD;

        // 隣り合う象限と自身
        ans += if r1 > 0 && r2 > 0 {
            (pr1 * pr2) % MOD
        } else {
            0
        } + if r2 > 0 && r3 > 0 {
            (pr2 * pr3) % MOD
        } else {
            0
        } + if r3 > 0 && r4 > 0 {
            (pr3 * pr4) % MOD
        } else {
            0
        } + if r4 > 0 && r1 > 0 {
            (pr4 * pr1) % MOD
        } else {
            0
        };
        ans %= MOD;

        // r1+r3, r2+r4 (自身を含む場合と含まない場合で２倍)
        ans += if r1 > 0 && r3 > 0 {
            (pr1 * pr3) * 2 % MOD
        } else {
            0
        } + if r2 > 0 && r4 > 0 {
            (pr2 * pr4) * 2 % MOD
        } else {
            0
        };
        ans %= MOD;

        // 3象限を含む場合
        ans += if r1 > 0 && r2 > 0 && r3 > 0 {
            (((pr1 * pr2) % MOD) * pr3 * 2) % MOD
        } else {
            0
        } + if r2 > 0 && r3 > 0 && r4 > 0 {
            (((pr2 * pr3) % MOD) * pr4 * 2) % MOD
        } else {
            0
        } + if r3 > 0 && r4 > 0 && r1 > 0 {
            (((pr3 * pr4) % MOD) * pr1 * 2) % MOD
        } else {
            0
        } + if r4 > 0 && r1 > 0 && r2 > 0 {
            (((pr4 * pr1) % MOD) * pr2 * 2) % MOD
        } else {
            0
        };
        ans %= MOD;

        // 全て含む場合(自身を含む場合と含まない場合で２倍)
        ans += if r1 > 0 && r2 > 0 && r3 > 0 && r4 > 0 {
            (((((pr1 * pr2) % MOD) * pr3) % MOD) * pr4 * 2) % MOD
        } else {
            0
        };
        ans %= MOD;

        lft.add(y as usize, 1);
        rft.add(y as usize, -1);
    }

    ans += n;
    ans %= MOD;

    ans
}

AtCoder ABC #136 E - Max GCD

E - Max GCD

問題

数列に対して、あるものにすると同時に、別の項にをするという操作をK回以下おこなって、取りうる最大のGCDを求めるという問題。

解説

ポイントは操作を行っても数列の総和は変わらず、かつ総和はGCDの倍数になっているはず、というところ。 よって総和の約数を大きい順で条件を満たすか試していけば良い。

どういう条件を調べるかと言うと

1. 各項を約数dで割った余りを求める（あまりは全て足すとdの倍数になるはずである）
2. 余りから0を除外して昇順にならべる
3. 前半を操作、後半を操作するとして最小操作回数を算出
4. 操作回数がK以下なら答え

コードにするとこうなる

fn solve(aa: Vec<isize>, k: usize) -> isize {
    let sum: isize = aa.iter().sum();

    let mut divs = (1..)
        .take_while(|x| x * x <= sum)
        .filter(|x| sum % x == 0)
        .flat_map(|x| {
            if sum / x == x {
                vec![x]
            } else {
                vec![x, sum / x]
            }
        })
        .collect::<Vec<_>>();
    divs.sort();

    for &d in divs.iter().rev() {
        let mut rs: Vec<isize> = aa.iter().map(|&x| x % d).filter(|&x| x != 0).collect();
        rs.sort();

        let rsum = rs.iter().sum::<isize>();
        let need = rs
            .iter()
            .take(rs.len() - (rsum as usize) / (d as usize))
            .sum::<isize>();
        if need <= k as isize {
            return d;
        }
    }

    -1
}

3.を求めるのが難しそうだがコードだと

        let need = rs
            .iter()
            .take(rs.len() - (rsum as usize) / (d as usize))
            .sum::<isize>();

たったコレだけだ。言われてみるとたしかにそのとおりなのだが制限時間内にコレを思いつくのはなかなか難しそうだ。

AtCoder ABC #134 E - Sequence Decomposing

E - Sequence Decomposing

問題

数列 が与えられたとき、数列を単調増加となるような部分数列に分けた場合に最小のグループ数を答える問題。

解説

公式解説には「広義の単調減少列の最大の長さ」を求めれば良いとあるが、ここがあまりしっくり来ていない。

が、とりあえず上記に従って解いてみる。

fn solve(aa: Vec<isize>) -> usize {
    let n = aa.len();
    let mut dp = vec![std::isize::MAX; n];

    for a in aa {
        let a = -a;
        let p = dp.upper_bound(&a);
        if a < dp[p] {
            dp[p] = a;
        }
    }

    dp.lower_bound(&std::isize::MAX)
}

upper_bound(), lower_bound()は自前のスニペット(TODO: 解説)だが、C++と似た仕様である。

「広義の単調減少列の長さ」を求めるアルゴリズムは「LIS(Longest Increasing Subsequence)」で検索すると見つかる。

dp[i]を「i+1の長さを持つ数列の内、最後の項がもっとも小さいもの」と置いている。今回は単調増加ではなく、単調減少列を見つけるため、項を負の数にして(let a = -a;)単調増加に変換していることに注意。

また「広義の単調増加」を見つけるため、lower_bound()ではなくupper_bound()を使用している点も注意。

最大の長さはdp[i]の定義からlower_bound()で簡単に見つけることができる。

AtCoder ABC #132 F - Small Products

F - Small Products

問題

正の整数K個を一列に並べたものであって、隣接して並んでいるどの2つの整数の積もN以下であるものの個数を10⁹+7で割った余りを求めてください。

解説

公式解説にあるようにxが最後の整数となるようなi個の整数を並べて条件を満たす場合の数dp[i][x]を使ったプログラムをまず書いてみる。

const MOD: i64 = 1000000000 + 7;

fn solve(n: usize, k: usize) -> i64 {
    let mut dp = vec![vec![0i64; n + 1]; k + 1];

    for i in 1..(n + 1) {
        dp[1][i] = i as i64;
    }

    for i in 2..(k + 1) {
        for j in 1..(n + 1) {
            dp[i][j] = (dp[i - 1][n / j] + dp[i][j - 1]) % MOD;
        }
    }

    dp[k][n]
}

累積和を使ってることに注意。ただし、もちろんこいつはLTEとなる。

次に公式解説に従ってがとなるように改良する。

例えばの場合商が同じになる方の組み合わせは以下のようになる。

レイヤ	法	商
1	1	25
2	2	12
3	3	8
4	4	6
5	5	5
6	7,8	3
7	9,..,12	2
8	13,..,25	1

DPをレイヤごとに構築してやるとが達成される。

const MOD: i64 = 1e9 as i64 + 7;

fn solve(n: usize, k: usize) -> i64 {
    let sqn = (n as f64).sqrt() as usize;
    let q = n / (sqn + 1);
    let r = sqn + q;

    let mut dp = vec![vec![0i64; 2 * r]; k + 1];

    let mut num = vec![0; r + 1];
    for i in 1..(r + 1) {
        if i <= sqn {
            num[i] = 1;
            dp[1][i] = dp[1][i - 1] + 1;
        } else {
            num[i] = (n / (r - i + 1) - n / (r - i + 2)) as i64;
            dp[1][i] = dp[1][i - 1] + num[i];
        }
    }

    for i in 2..(k + 1) {
        for j in 1..(r + 1) {
            dp[i][j] = (dp[i - 1][r - j + 1] * num[j] + dp[i][j - 1]) % MOD;
        }
    }

    dp[k][r]
}

AtCoder ABC #131 E - Friendships

E - Friendships

問題

N頂点単純連結無向グラフで最短距離が2である頂点対がK個あるものを構築する。

解説

まず最短距離が2である頂点対が最大となるのはある１点（仮に「中心点」と呼ぶ）が他の全ての点と辺を持ち、それ以外の辺が存在しないときである。

このとき頂点対の数はである。したがってKがこれより大きい場合は構築不可である。

そして中心点以外の頂点を辺でつなぐとその頂点対のみ最短距離は1となって最短距離が2の辺数を1だけ減らすことができる。

コードは以下のようになる

fn solve(n: u64, k: u64) -> Option<Vec<(u64, u64)>> {
    if k > (n - 1) * (n - 2) / 2 {
        return None;
    }

    let mut ans = (2..(n + 1)).map(|i| (1, i)).collect::<Vec<(u64, u64)>>();

    let times = (n - 1) * (n - 2) / 2 - k;
    let mut cnt = 0;
    let mut s = 2;
    let mut e = 3;

    while cnt < times {
        ans.push((s, e));
        if e == n {
            s += 1;
            e = s + 1;
        } else {
            e += 1;
        }
        cnt += 1;
    }

    Some(ans)
}