あまり良くない勝ち方でしたが、とはいえ5完で勝ち。最近は連勝できているのでこの調子でレートを増やしたいです。

A - 12435

埋め込むかどうかで少し迷いますが、5個は少し多いなーと思ったのでシミュレーションします。url

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (ll i=0;i<n;++i)

void solve() {
    int a[5];
    int n = 5;
    rep(i, n) cin >> a[i];

    rep(i, 4) {
        swap(a[i], a[i+1]);
        bool flag = true;
        rep(j, 5) {
            if (a[j] != j+1) flag = false;
        }
        if(flag) { 
            cout << "Yes
";
            return;
        }
        swap(a[i], a[i+1]);
    }
    cout << "No
";
}

B - Geometric Sequence

等比数列ってなんでしたっけ(あの？)となったのでググります。1つめの比をベースとして、それと全て同じになっていることを判定すれば良さそうです。ただし、小数演算は誤差が怖いので

と式変形をして小数を用いずに判定すれば安全にACできます。提出

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for (

また、言語によりますが、有理数ライブラリを利用するのも手かと思います。有理数ライブラリ解(Rust)

use itertools::Itertools;
use num_rational::Ratio;
use proconio::input;

fn main() {
    input! {
        n: usize

C - Paint to make a rectangle

黒マスの内、最も右/左/下/上にあるもの場所を記録します。その内側にあるものは黒の領域で外側は白の領域となるので、内側の領域に白いマスが存在しないことを判定すればよいです。 提出

void solve() {
    int h, w; cin >> h >> w;
    vector<string> bd(h); rep(i, h) cin >> bd[

D - Stone XOR

見るからに全探索です。しかも、特に工夫のいらない全探索に見えます。というのも、うまくやることで省略できるという要素がなさそうで、しかも特にメモ化できる要素が無い¹ので、再帰で全列挙すればよいです。提出(1142ms)

use std::collections::BTreeSet;
use proconio::input;

fn dfs(v: &mut Vec<u64>, i: usize, a: 

計算量解析はせずにまぁ間に合うだろで投げましたが、このような区別できる要素を1つ以上のグループに分ける場合の数のことをベル数というらしいです²。$i$番目のベル数を$B_i$と書くことにすると、計算量は$O(B_{N}\log{B_{N}})$となります。、のとき、でありですから、じつはかなりの定数倍勝負だったみたいです。特に、C++ではが実はあまり早くないこともありかなりの人が沼にハマったようでした。

Rustでも、BTreeSetではなく単にVecに入れておいて、最後にsortしてdedupすることでより高速に解くことができました。提出(Rust, 369ms)

E - Vitamin Balance

まず、シンプルなdpが見えました。dp[i][j][k] := カロリーi, ビタミン1がj, ビタミン2がkだけ接種したときのビタミン3としてあり得る最大値としたい気持ちになりますが、困ったことにメモリが全然足りません。無限のメモリを使いたい。

仕方がないので別の方針を考えます。よく見ると各食べ物はビタミンを1つしか持っていないので、それぞれについて「カロリーiだけ接種したときの接種ビタミンとしてあり得る最大値」とすれば、これは$O(NX)$で求めることができます。さらに、この結果を用いて、「カロリーを$X$以下だけ接種したときに、各ビタミンを$m$以上接種することは可能か？」を判定して二分探索をすることによって、$O(NX + N\log(\sum A))$でこの問題を解くことができます。

なお、本番の私は何を考えたか毎回動的計画法をやり直す$O(NX\log(\sum A))$という実装をしました³が、ぎりぎり通ったのでOK。提出(1653ms)

use proconio::{input, marker::Usize1};

fn dp(key: i64, x: usize, v: &Vec<(i64, usize

        v

                res

F - Double Sum 3 (Upsolve)

手も足も出ず。ある区間を削除する際に、できるだけ長い区間を削除したいです。具体的には、3, 2, 4, 6, 7が与えられたときは、$l=2, r=4$を選んで数列を6, 7とし、その後$l=6, r=7$を選ぶのが最適となります。 ここで答えを求めることは難しいので、数え上げる対象を読み替えることにします。すべての操作を行った結果、$i=1,$それぞれについてとして削除を行った回数を数え上げることができれば、この問題を解くことができます。

ここで、操作において$l=A_i$として削除を行う条件を考えると、それは「対象の区間において$A_j = A_i - 1$なるが存在しない」です。なぜなら、そのようなが存在するのであればそちらを左端として処理するほうが良いからです。逆に言うと、そのようなが出てくるまでの間はとして削除するのが最適となりますから、であるであってを満たすようなのうち最も大きいもの(存在しなければとする)と、であるであってを満たすようなのうち最も小さいものが高速にわかれば良く、これは二分探索などを用いることで対数時間で求めることができます。 また、同じ区間を重複して数えてしまうケースがあるため、「削除する区間に同じ値が含まれる場合は最も左にある値を使う」というルールをつけ、上とのmaxをとることで重複を排除できます。

以上より、この問題が$O(N\log N)$と十分高速に解くことができます。なお、実装が辛いなーと言いながら工夫をしていたら$O(N)$になっていました。。提出

use proconio::input;

fn main() {
    input! {
        n: usize,
        a: [usize; n],
    }

    let
            idx