Codeforces I. Photo Processing (2017-2018 ACM-ICPC, NEERC, Southern Subregional Contest)

解法

求めたい値は二分探索で求めましょう.
あとはある x にたいして題意を満たす分割が可能か調べます.
写真の値はソートしておくと,題意の分割は連続部分列の分割になります.
その上で,以下の累積和を考えます.
dp[i] := 写真 [0..j] ( j <= i ) だけを考えた時,題意を満たす分割が可能な j の個数

写真 i について考えます.この写真は少なくとも i - k より左にある写真を含むような列に含まれなければなりません.また,vi - x 以上である値を持つ最も左の写真より左側の写真を一緒に含めることも出来ません.
r = i - k,l = (vi - x 以上の最も左の写真の位置) とすると,l から r の間でうまく分割できれば,この写真を分割することができます.
これは先程の累積和を使って言い換えると,l から r の間に dp[j] != dp[j + 1] となるような位置があれば良いということになります.
したがって,dp[l - 1] と dp[r] の値を比べて,それらが違えば間に分割できる位置があると判定することが出来ます.

計算量は O(N log V) です.

ソースコード

fn lower_bound<T: Ord>(v: &Vec<T>, first: usize, last: usize, val: T) -> usize {
    let (mut lb, mut ub) = (first, last);
    while ub - lb > 0 {
        let mid = (ub + lb) / 2;
        if v[mid] < val {
            lb = mid + 1;
        } else {
            ub = mid;
        }
    }
    return ub;
}

fn main() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin);

    let n: usize = sc.read();
    let k: usize = sc.read();
    let mut v: Vec<i32> = vec![0; n + 1];
    for i in 1..n+1 {
        v[i] = sc.read();
    }
    v.sort();
    let v = v;

    let (mut lb, mut ub): (i32, i32) = (-1, 1e9 as i32);
    while ub - lb > 1 {
        let mid = (lb + ub) / 2;
        let mut dp: Vec<i32> = vec![0; n + 1];
        dp[0] = 1;
        for i in 1..n+1 {
            dp[i] = dp[i - 1];
            let l = lower_bound(&v, 1, n + 1, v[i] - mid) - 1;
            if i < k {
                continue;
            }
            let r = i - k;
            if r >= l && dp[r] > if l > 0 { dp[l - 1] } else { 0 } {
                dp[i] += 1;
            }
        }
        if dp[n] == dp[n - 1] {
            lb = mid;
        } else {
            ub = mid;
        }
    }
    println!("{}", ub);
}

AOJ 0597 Xiao Long Bao

解法

汁が飛び散る範囲が小さいので,それを利用します.
ある連続する8個の区間を考えると,そのなかで各小籠包がどの順で食べられるかさえわかれば,答えを求めることができます.
7! = 5040 なので,以下の dp を考えます.
dp[i][p] := 右端を i 番目まで見た時に,そこから ( i 番目も含めて) 手前7個の食べる順番が p であるようなときの最大
ただし,p は順列です.

dp[i][p] の状態から遷移を考えます.区間内の小籠包が互いにどれだけ点数を与えるかはすでに求まっているということになるので,新しい i + 1 番目の小籠包を p に付け加えることになります.
付け加える前に,i - 6 番目(つまり左端)の小籠包は今後みるひつようがないので,取り除きます.この小籠包が x 番目に食べられるとするなら,区間内の y ( < x) 番目に食べられる小籠包を,y + 1 番目に食べられるということにしておきます.
つぎに,i + 1 番目の小籠包が,区間内で何番目に食べられるかをすべて試します.k 番目に食べられるとするなら,そこから距離 d[i + 1] 以内で,かつ自分よりあとに食べることになる小籠包の数だけ,a[i + 1] を加算します.また,k 番目より先に食べる小籠包についても,同様に考えて加算します.
さて,先程取り除いた左端の小籠包ですが,もし i + 1 番目の小籠包,あるいは左端の小籠包の汁の飛び散る範囲が 7 なら,この2つの順番も考慮する必要があります.
これは,i + 1 番目の小籠包も x 番目に食べるとしたときに,左端の小籠包とどちらを先に食べるか(これは自由に決めて良い.なぜなら他の小籠包の順番はもう決まっていて,これとは独立だから.)を試して良い方を取ります.
それ以外のときは,他の小籠包と同様に単純に x と k を比較すれば良いです.

以上で解くことが出来ました.
計算量は O(n * 7 * 6 * 7!) となり,間に合います.

ソースコード

fn next_permutation<T: Ord>(v: &mut Vec<T>) -> bool {
    if v.len() == 0 || v.len() == 1 {
        return false
    }
    let mut i: usize = v.len() - 1;
    let n = v.len();
    loop {
        let ii = i;
        i -= 1;
        if v[i].cmp(&v[ii]) == Ordering::Less {
            let mut j = n - 1;
            while v[i].cmp(&v[j]) != Ordering::Less {
                j -= 1;
            }
            v.swap(i, j);
            for k in 0..(n - ii) / 2 { // reverse
                v.swap(ii + k, n - k - 1);
            }
            return true
        }
        if i == 0 { // i == first
            v.reverse();
            return false
        }
    }
}
 
fn main() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin);
 
    let n: usize = sc.read();
    let mut d: Vec<usize> = vec![0; n];
    let mut a: Vec<usize> = vec![0; n];
    for i in 0..n {
        d[i] = sc.read();
    }
    for i in 0..n {
        a[i] = sc.read();
    }
    let d = d;
    let a = a;
 
    let mut dp: Vec<HashMap<Vec<usize>, usize>> = vec![HashMap::new(); n];
    let mut perm: Vec<usize> = (0..7).collect();
    while {
        dp[0].insert(perm.clone(), 0);
        next_permutation(&mut perm)
    } {}
 
    for i in 0..n-1 {
        let mut nxt: HashMap<Vec<usize>, usize> = HashMap::new();
        for (p, r) in &mut dp[i] {
            let mut np: Vec<usize> = vec![0; 7];
            for j in 0..6 {
                np[j] = p[j + 1];
                if p[0] > p[j + 1] {
                    np[j] += 1;
                }
            }
            for _j in 0..7 {
                let mut rr = *r;
                for kk in 0..6 {
                    if i >= kk {
                        if np[6 - kk - 1] < np[6] && d[i - kk] >= kk + 1 {
                            rr += a[i - kk];
                        }
                        if np[6 - kk - 1] > np[6] && d[i + 1] >= kk + 1 {
                            rr += a[i + 1];
                        }
                    }
                }
                if i >= 6 && p[0] == np[6] {
                    let t1 = if d[i - 6] == 7 { a[i - 6] } else { 0 };
                    let t2 = if d[i + 1] == 7 { a[i + 1] } else { 0 };
                    rr += max(t1, t2);
                } else if i >= 6 && p[0] > np[6] {
                    rr += if d[i + 1] == 7 { a[i + 1] } else { 0 };
                } else if i >= 6 && p[0] < np[6] {
                    rr += if d[i - 6] == 7 { a[i - 6] } else { 0 };
                }
                if nxt.contains_key(&np) {
                    let r2: usize = *nxt.get(&np).unwrap();
                    nxt.insert(np.clone(), max(rr, r2));
                } else {
                    nxt.insert(np.clone(), rr);
                }
                np[6] += 1;
                for k in 0..6 {
                    if np[k] == np[6] {
                        np[k] -= 1;
                    }
                }
            }
        }
        dp[i + 1] = nxt;
    }
 
    println!("{}", dp[n - 1].iter().fold(0, |ans, (_, a)| max(ans, *a)));
}

感想

これは普通に難しかった.遷移が少しややこしい.

AOJ 0624 Food stalls

解法

bitDP で解きます.
あるマスにいるとき,それまでに買った屋台の情報を持つのですが,右か下にしかいけないことから,保存すべき場所が少なくなります.
具体的には,右,下,右上,左下の4箇所の購入状況を保存しておけば十分です.
あとは,実際に移動した時の買い方を全部試すだけで良いです.

空きマスは0円の屋台としても答えは変わらないので,そうすると一部実装がサボれるかも.

計算量は O(16 * HW)

ソースコード

fn main() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin);

    let h: usize = sc.read();
    let w: usize = sc.read();
    let mut map: Vec<Vec<char>> = vec![Vec::new(); h];
    for i in 0..h {
        let s: String = sc.read();
        map[i] = s.chars().collect();
    }
    let map = map;
    let mut val: Vec<Vec<i32>> = vec![vec![0; w]; h];
    for i in 0..h {
        for j in 0..w {
            if map[i][j] == '.' {
                val[i][j] = 0;
            } else {
                val[i][j] = (map[i][j].to_digit(10)).unwrap() as i32;
            }
        }
    }
    let val = val;

    let mut dp: Vec<Vec<Vec<i32>>> = vec![vec![vec![INF; 1 << 4]; w]; h];
    dp[0][0][0] = 0;
    for i in 0..h {
        for j in 0..w {
            for b in 0..(1 << 4) {
                if i + 1 < h { // go down
                    let (ny, nx) = (i + 1, j);
                    let mut pay = 0;
                    if b & (1 << 1) == 0 {
                        pay += val[ny][nx];
                    }
                    let mut v: Vec<(i32, usize)> = Vec::new();
                    let nb = 0b0110 | ((b & (1 << 2)) << 1);
                    if ny + 1 < h {
                        v.push((val[ny + 1][nx], (1 << 1)));
                        pay += val[ny + 1][nx];
                    }
                    if nx + 1 < w {
                        v.push((val[ny][nx + 1], (1 << 2)));
                        pay += val[ny][nx + 1];
                    }
                    if nx != 0 && b & (1 << 0) == 0 {
                        v.push((val[ny][nx - 1], INF as usize));
                        pay += val[ny][nx - 1];
                    }

                    if v.len() == 0 {
                        dp[ny][nx][nb] = min(dp[ny][nx][nb], dp[i][j][b] + pay);
                    }
                    for (nobuy, bb) in v {
                        let nb = if bb == INF as usize { nb } else { nb ^ bb };
                        dp[ny][nx][nb] = min(dp[ny][nx][nb], dp[i][j][b] + pay - nobuy);
                    }
                }

                if j + 1 < w { // go right
                    let (ny, nx) = (i, j + 1);
                    let mut pay = 0;
                    if b & (1 << 2) == 0 {
                        pay += val[ny][nx];
                    }
                    let mut v: Vec<(i32, usize)> = Vec::new();
                    let nb = 0b0110 | ((b & (1 << 1)) >> 1);
                    if ny + 1 < h {
                        v.push((val[ny + 1][nx], 1 << 1));
                        pay += val[ny + 1][nx];
                    }
                    if nx + 1 < w {
                        v.push((val[ny][nx + 1], 1 << 2));
                        pay += val[ny][nx + 1];
                    }
                    if ny != 0 && b & (1 << 3) == 0 {
                        v.push((val[ny - 1][nx], INF as usize));
                        pay += val[ny - 1][nx];
                    }

                    if v.len() == 0 {
                        dp[ny][nx][nb] = min(dp[ny][nx][nb], dp[i][j][b] + pay);
                    }
                    for (nobuy, bb) in v {
                        let nb = if bb == INF as usize { nb } else { nb ^ bb };
                        dp[ny][nx][nb] = min(dp[ny][nx][nb], dp[i][j][b] + pay - nobuy);
                    }
                }
            }
        }
    }
    println!("{}", dp[h - 1][w - 1].iter().min().unwrap());
}

感想

実装に若干失敗しています.右に移動する時と左に移動するときで共通処理が割りとあるので,コード量的にはもっと減らせるはずです.
が,変にまとめて混乱するよりは愚直に書いてみるかということでそうなりました.

Rust で SkewHeap を書いてみた

タイトルのまんま.
純粋関数型データ構造っぽさを意識して書いてみました.

use std::rc::Rc;
enum SkewHeap<T: Ord + Clone> {
    Empty,
    Node(T, Rc<SkewHeap<T>>, Rc<SkewHeap<T>>)
}

impl<T: Ord + Clone> Clone for SkewHeap<T> {
    fn clone(&self) -> SkewHeap<T> {
        match *self {
            SkewHeap::Empty => SkewHeap::Empty,
            SkewHeap::Node(ref v, ref l, ref r) => SkewHeap::Node((*v).clone(), (*l).clone(), (*r).clone()),
        }
    }
}

impl<T: Ord + Clone> SkewHeap<T> {
    fn push(&self, val: T) -> SkewHeap<T> {
        self.meld(SkewHeap::Node(val, Rc::new(SkewHeap::Empty), Rc::new(SkewHeap::Empty)))
    }

    fn meld(&self, other: SkewHeap<T>) -> SkewHeap<T> {
        match *self {
            SkewHeap::Empty => other.clone(),
            SkewHeap::Node(ref v1, ref l1, ref r1) => {
                match other {
                    SkewHeap::Empty => self.clone(),
                    SkewHeap::Node(ref v2, ref l2, ref r2) => {
                        if v1 < v2 {
                            let r = r1.clone();
                            //SkewHeap::Node(v1.clone(), l1.clone(), Rc::new(r.meld(other.clone())))
                            SkewHeap::Node(v1.clone(), Rc::new(r.meld(other.clone())), l1.clone())
                        } else {
                            let r = r2.clone();
                            //SkewHeap::Node(v2.clone(), l2.clone(), Rc::new(r.meld(self.clone())))
                            SkewHeap::Node(v2.clone(), Rc::new(r.meld(self.clone())), l2.clone())
                        }
                    }
                }
            }
        }
    }

    fn pop(&self) -> (Option<T>, SkewHeap<T>) {
        match *self {
            SkewHeap::Empty => (None, SkewHeap::Empty),
            SkewHeap::Node(ref v, ref l, ref r) => {
                (Some(v.clone()), l.meld((**r).clone()))
            }
        }
    }
}

使ってみた

試しに以下の問題を解いてみた.
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_9_C

結果は 3.99 sec で TLE.まあ clone しまくってるのでそれはそう.予想より早い(もっと遅いと思っていた)

追記
木の形偏ってるなあと思っていたら,meld するときに swap するの忘れてた.すると 3.99 sec から 3.07 sec に改善した.

感想

もし競プロならこのままだと使えない.純粋関数型っぽさを捨てれば早いのは書ける.Rust はライフタイムの制約が厳しすぎて,変更が加わらなかったノードは共有するみたいなコードを書くのが難しい.どうかけばいいかわからん.

AOJ 1386 Starting a Scenic Railroad Service

解法

一方はいもす法やるだけなのはすぐわかると思います.
もう一方が問題ですが,これも累積和で簡単に求まります.
じつは,乗客 i のデータの区間 [a[i], b[i]] に対して,端点以外で少しでもかぶっている他の乗客の区間の数を M_i とすると,M = max{ M_i } が答えになります.

以下ちゃんとした(仰々しい)証明.
求めたい答えを A とすると,A >= M である.区間 [a[i], b[i]] に少しでもかぶる乗客の集合を S_i (これには乗客 i も含める) とする.S_i のうち,互いに区間がかぶらない乗客が優先的に予約をしていくと考えれば,少なくとも |S_i| 席が必要である.仮に s ( < |S_i| ) 席しかないとする.互いに区間がかぶらない乗客の数が s 人以上であれば,そのうちの s 人で先に席を埋めてしまうと,乗客 i が予約できなくなるので,s 席では足りない.乗客の数が s 人未満でも同じ.よって,A >= |S_i| だから A >= M が示せた.
次に A <= M であることを示す.とはいっても明らかで,ある区間に同時にのる乗客の数以上の席は明らかに必要ない.

以上より,A = M = max{ |S_i| } であり,累積和で求めることができる.
具体的には順方向の累積和 sum[i] ( b[i] を用いる ) と逆方向の累積和 rsum[i] ( a[i] を用いる ) を用意すれば良い.この時,
sum[i] := 区間 [0..i] に完全に含まれる乗客の数
rsum[i] := 区間 [i...] に完全に含まれる乗客の数
になる.

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n;
    int MAX = 1e5 + 2;
    vector<int> a(n), b(n);
    vector<int> imos(MAX), sum(MAX), rsum(MAX);
    for(int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
        imos[a[i]]++;
        imos[b[i]]--;
        sum[b[i]]++;
        rsum[a[i]]++;
    }
    for(int i = 1; i < MAX; ++i) {
        imos[i] += imos[i - 1];
        sum[i] += sum[i - 1];
    }
    for(int i = MAX - 1; i >= 1; --i) {
        rsum[i - 1] += rsum[i];
    }
    int ans1 = 0, ans2 = *max_element(imos.begin(), imos.end());
    for(int i = 0; i < n; ++i) {
        ans1 = max(ans1, n - sum[a[i]] - rsum[b[i]]);
    }
    cout << ans1 << ' ' << ans2 << endl;
}

感想

本番ではチームメイトが累積和のやり方を考えてくれて,僕が正当性を詰めました.
詰めると言っても流石にここまで丁寧に詰めたわけではないですが…

AOJ1133 Water Tank

方針1

いわゆるやるだけ問題ですが,頑張って通して満足するだけで終わると得られるものがなさそうな問題.
こういうので実装方針を詰める練習をしなければいけないと思う(あくまで僕の意見ですが).

まず,仕切りを外しても状態が変わらないような水槽は統合してしまってよいことがわかる.仕切りを外してよいのは,どちらか一方の水が溢れており,かつ水の高さが等しい時.

次に,シミュレーションするなら1秒毎ではなくて,どこからか水が溢れ始める時点で区切れば良さそうに見える.

溢れた時にどうするかだが,これは蛇口の場所を変えるのと同値であると考えれば見通しが良さそうにみえる.つまり,

  • 水がどちらにもあふれる場合,今見ている水槽にある蛇口を2分割して左右の水槽に分配する
  • 水が左にあふれる場合,今見ている水槽にある蛇口を左に移動させる.右にあふれるときも同様.

蛇口の移動は隣に移動させるだけじゃなくて,連続して移動しうる(移動先がすでに溢れている場合)ので,隣に移す処理を水槽の数だけループを回せば,いずれ蛇口は正しい位置に移動できる.

あとは L 回のクエリを時系列順にソートしておいて,そのタイミングが来たら答えを計算する.

入力サイズはかなり小さいのでよっぽどひどい実装でない限り計算量は気にならない.

ソースコード1

#include <bits/stdc++.h>
using namespace std;

constexpr double eps = 1e-6;

struct tank {
    double wall_l, wall_r;
    double in;
    double w, h;
    tank() : wall_l(0), wall_r(0), in(0), w(0), h(0) {}
};

tank merge(tank const& left, tank const& right) {
    tank res;
    res.wall_l = left.wall_l;
    res.wall_r = right.wall_r;
    res.in = left.in + right.in;
    res.w = left.w + right.w;
    res.h = left.h; // (= right.h)
    assert(fabs(left.h - right.h) < eps);
    return res;
}

int main() {
    constexpr double width = 100, height = 50, depth = 30;
    int D; cin >> D;
    while(D--) {
        int N; cin >> N;
        vector<tank> ts(N + 1);
        ts[0].wall_l = ts.back().wall_r = height;
        for(int i = 0; i < N; ++i) {
            int B, H; cin >> B >> H;
            ts[i].w = B;
            ts[i].wall_r = ts[i + 1].wall_l = H;
        }
        ts[N].w = width;
        for(int i = N; i >= 1; --i) {
            ts[i].w -= ts[i - 1].w;
        }
        int M; cin >> M;
        double total_in = 0;
        for(int i = 0; i < M; ++i) {
            int F, A; cin >> F >> A;
            total_in += A;
            int x = 0;
            for(int j = 0; j <= N; ++j) {
                x += ts[j].w;
                if(x > F) {
                    ts[j].in += A / depth;
                    break;
                }
            }
        }

        int L = 0;
        cin >> L;
        vector<tuple<int, int, int>> qs;
        for(int i = 0; i < L; ++i) {
            int P, T; cin >> P >> T;
            qs.emplace_back(T, P, i);
        }
        sort(begin(qs), end(qs));

        vector<double> ans(L);
        double now_t = 0;
        int qi = 0;
        while(qi < L) {
            int T, P, idx;
            tie(T, P, idx) = qs[qi];
            if(T >= width * height * depth / total_in) {
                ans[idx] = height;
                qi++;
                continue;
            }
            double dt = T - now_t;
            for(auto& tk : ts) {
                if(tk.in > 0) {
                    double wall_h = min(tk.wall_l, tk.wall_r);
                    dt = min(dt, (wall_h - tk.h) * tk.w / tk.in);
                }
            }
            for(auto& tk : ts) {
                tk.h += dt * tk.in / tk.w;
            }
            vector<tank> nxt_ts = {ts[0]};
            for(int i = 1; i < (int)ts.size(); ++i) {
                if(fabs(ts[i].h - nxt_ts.back().h) < eps && fabs(ts[i].h - ts[i].wall_l) < eps) {
                    nxt_ts.back() = merge(nxt_ts.back(), ts[i]);
                } else {
                    nxt_ts.push_back(ts[i]);
                }
            }
            ts = move(nxt_ts);
            now_t += dt;
            for(int loop = 0; loop < 10; ++loop) {
                for(int i = 0; i < (int)ts.size(); ++i) {
                    bool to_l = fabs(ts[i].wall_l - ts[i].h) < eps,
                         to_r = fabs(ts[i].wall_r - ts[i].h) < eps;
                    if(to_l && to_r) {
                        ts[i + 1].in += ts[i].in / 2;
                        ts[i - 1].in += ts[i].in / 2;
                        ts[i].in = 0;
                    } else if(to_l) {
                        ts[i - 1].in += ts[i].in;
                        ts[i].in = 0;
                    } else if(to_r) {
                        ts[i + 1].in += ts[i].in;
                        ts[i].in = 0;
                    }
                }
            }
            if(fabs(now_t - T) < eps) {
                double x = 0;
                for(auto& tk : ts) {
                    x += tk.w;
                    if(x > P) {
                        ans[idx] = tk.h;
                        break;
                    }
                }
                qi++;
            }
        }

        for(auto h : ans) {
            cout << fixed << setprecision(6) << h << endl;
        }
    }
}

方針2

さっきのもまあ素直な実装だから辛いと言うほどではないが,もう少し上手く処理できる.
ある蛇口に注目して,初期状態から時間 T だけ水を入れた場合にどうなるか観察する.
小さい視点(直接注いでいる水槽)から視野を広げていって,最終的に全体を眺める感じなので,再帰構造が見えてくる.

pour(pos, l, r, a) := pos 番目の水槽に水量 a だけ流した時,水槽 [l..r) はどうなっているか?また,[l..r) について流しきった時に,a はどれだけ残っているか?

さて,仕切り y の位置で水があふれるということを広い視点で眺めてみる.ここでは左からあふれると仮定する.「水が仕切り y の位置で溢れてくる」ことは「仕切り y から左側で,仕切り y よりはじめて高くなる仕切りまでの水槽を考えた時,それらの水位が仕切り y とおなじになっている」ことと言い換えることができる.
つまり,水槽 [l..r) を眺める時,部分構造として,端を除いた [l..r) の仕切りの中で最も高いものを mid として,[l..mid) と [mid..r) を考えればよいということにほかならない.
そのとき,pos が [l..mid) の方にあるか [mid..r) の方にあるかで,先にどちらを処理するかを決めれば良い.
[l..r) に水を流した後に流すべき水が残っているなら,その水については一段上の再帰段階で処理するものである.

ソースコード2

#include <bits/stdc++.h>
using namespace std;

void pour(int pos, int l, int r, double& a, vector<double> const& x, vector<double> const& h, vector<double>& ans) {
    if(r - l > 1) {
        int mid = l + 1;
        for(int i = l + 1; i < r; ++i) {
            if(h[mid] < h[i]) {
                mid = i;
            }
        }
        if(pos < mid) {
            pour(pos, l, mid, a, x, h, ans);
            pour(pos, mid, r, a, x, h, ans);
        } else {
            pour(pos, mid, r, a, x, h, ans);
            pour(pos, l, mid, a, x, h, ans);
        }
    }

    double side_h = min(h[l], h[r]);
    double add = max(0.0, (side_h - ans[l]) * (x[r] - x[l]));
    add = min(add, a);
    a -= add;
    for(int i = l; i < r; ++i) {
        ans[i] += add / (x[r] - x[l]);
    }
}

int main() {
    int D; cin >> D;
    while(D--) {
        int N; cin >> N;
        vector<double> x(N + 2), h(N + 2);
        for(int i = 1; i <= N; ++i) {
            cin >> x[i] >> h[i];
        }
        x[N + 1] = 100;
        h[0] = h[N + 1] = 50;
        int M; cin >> M;
        vector<double> in(N + 1);
        for(int i = 0; i < M; ++i) {
            int F, A; cin >> F >> A;
            int j = upper_bound(begin(x), end(x), F) - begin(x) - 1;
            in[j] += A / 30.0;
        }

        int L; cin >> L;
        while(L--) {
            int P, T; cin >> P >> T;
            vector<double> ans(N + 1);
            for(int i = 0; i < N + 1; ++i) {
                double a = in[i] * T;
                pour(i, 0, N + 1, a, x, h, ans);
            }
            int j = upper_bound(begin(x), end(x), P) - begin(x) - 1;
            cout << fixed << setprecision(6) << ans[j] << endl;
        }
    }
}

感想

本番だったら,実装方針を詰める時間に実装したほうが早いかもしれないので難しいところですが,練習で解くなら実装方針まで考えたい.

2017年の振り返り

はじめに

2017年の振り返りをします.去年の振り返り記事は自分でも読みづらかったので,今年はできるだけ簡潔に書こうと思います.
基本的に競プロ関係に絞って書くことにします.

1月,2月,3月

  • 記憶がない.多分競プロをほとんどやっていない時期.
  • 2月頭から3月頭にかけて短期バイト(300時間ぐらい働いたかな)してお金を稼いだのは覚えている.
  • 3月末には関西系の大学が集まってやる競プロ合宿に参加した.参加後あたりからちゃんと再開した気がします.

4月

  • 新入生プロジェクトで競プロを教えることになったので,資料作成とか問題選定とかやりまくってたかも.
  • AtCoderのレートがこの月に200ぐらい上がっていた(元が低すぎるってそれ一番言われてるから

5月

  • ICPCに意識を向け始めた頃.AOJ-ICPCを下の方から埋めまくっていた気がする.
  • レートは上がりませんでした.悲しいね.

6月

  • チーム練習をはじめかける頃.AOJ-ICPCの虚無実装問題を埋めていたせいもあって実装担当になってしまう.
  • レートは上がりませんでした.なんでや.

7月

  • ICPCの練習をガリガリやる.
  • 勉学が疎かになっていることに気がつく.
  • 国内予選に学内2位で通過する.これはかなり嬉しかった.

8月

  • 競プロの練習(主に実装系)をちょこちょこやっていた.
  • 問題をたくさん解くというよりは,辛い問題を時間をめっちゃかけて通すみたいなことをしていた(これのせいで瞬発力が必要なコンテストが苦手になっていたかもしれない

9月

  • 練習方法は8月と同じ.DPの問題を中心にやってたかな.
  • レートが今(12月現在)と同じぐらいに上がっていた

10月

  • CODEFESTIVAL 2017で予選通過.かなりギリギリだった.(反省して
  • レートはあまり変わらず.

11月

  • 一瞬黄色になる(競プロはじめました)
  • CODEFESTIVAL 本戦で冷える.青に戻る(競プロ引退)
  • CODEFESTIVAL はなんだかんだ楽しいのでみんなも参加しよう!

12月

  • ICPC アジア地区の季節.
  • ミャンマーの Yangon 大会に出て4位だった.あと1問通していればWFだったので悔しいが,初アジアにしては良い成績だったと思う.
  • Tsukuba大会は冷えた.誤読していて,1問解けない問題になっていたのは反省しないとダメ.でも普通に地力が足りない感じがしたので,来年頑張るぞという気持ちになった.
  • Codeforces でやっと div1 に上がる.div2 の A と B からやっと解放されて嬉しい.

まとめ

  • 競プロのレート変動は以下の通り.
    • AtCoder 1523 -> 1945 (+422)
    • Codeforces 0 -> 1952
    • CSAcademy 0 -> 1759
    • TopCoder 0 -> 1403 (出たのは2回だけ.今後出るつもりはあまりない.
  • ちなみに AOJ-ICPC の得点は 150100 点まで上げた.500まではほとんど全部埋めて,550は7割ぐらい埋めた.
  • ICPCが思ってたより楽しかったので,来年はICPCでいい結果を残せるように頑張りたい.(このままだとチームからいらない子宣言を受けるため

それでは皆さん,良いお年を.