CODE FESTIVAL 2014 予選B D: 登山家

問題

D: 登山家 - CODE FESTIVAL 2014 予選B | AtCoder

解法

Sparse Tableを構築して、高さの高い山小屋から、見ることができる山小屋の個数を決定していく。遷移はお決まりの分割統治で行う。

山小屋の高さが親の山小屋の高さと一致するとき、解は親の解と一致する。

そうでないとき、解は 区間の長さ-1 となる。

別解は多数ある。考察と実装が楽になるようにデータ構造を選ぶのが良いだろう。

using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Globalization;
using System.Diagnostics;
using static System.Console;
//using System.Numerics;
//using static System.Math;
using pair = Pair<int, int>;
 
class Program
{
    static void Main()
    {
        SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
        new Program().solve();
        Out.Flush();
    }
    Scanner cin = new Scanner();
    readonly int[] dd = { 0, 1, 0, -1, 0 };
    readonly int mod = 1000000007;


    void solve()
    {
        int N = cin.nextint;

        var H = new pair[N];
        for (int i = 0; i < N; i++)
        {
            H[i] = new pair(-cin.nextint, i);
        }
        var S = new SparseTable<pair>(H, N);
        var ans = new int[N];
        calc(0, N, 1, 1, ans, S);
        foreach (var item in ans)
        {
            WriteLine(item);
        }
    }
    void calc(int l, int r, int pheight, int pans, int[] ans, SparseTable<pair> S)
    {
        if (l >= r) return;
        var p = S.query(l, r);
        //WriteLine(p.ToString());
        int v = p.f;
        int m = p.s;
        if (v == pheight)
        {
            ans[m] = pans;
        }
        else
        {
            ans[m] = r - l - 1;
        }
        calc(l, m, v, ans[m], ans, S);
        calc(m + 1, r, v, ans[m], ans, S);
    }
}

class SparseTable<T> where T : IComparable<T>
{
    const int K = 18;
    T[][] st = new T[K][];
    public SparseTable(T[] a, int n)
    {
        st = st.Select(i => new T[n]).ToArray();
        Array.Copy(a, st[0], n);
        for (int k = 1; k < K; k++)
        {
            for (int i = 0; i + (1 << k) <= n; i++)
            {
                st[k][i] = st[k - 1][i].CompareTo(st[k - 1][i + (1 << (k - 1))]) < 0 ? st[k - 1][i] : st[k - 1][i + (1 << (k - 1))];
                //st[k][i] = Math.Min(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
            }
        }
    }
    //min[a,b)
    public T query(int a, int b)
    {
        int k = 31 - builtin_clz((uint)(b - a));
        return st[k][a].CompareTo(st[k][b - (1 << k)]) < 0 ? st[k][a] : st[k][b - (1 << k)];
        //return Math.Min(st[k][a], st[k][b - (1 << k)]);
    }
    int builtin_clz(uint x)
    {
        int i = 0;
        while ((x >> (31 - i) & 1) == 0)
        {
            i++;
        }
        return i;
    }
}

class Pair<T, U> : IComparable<Pair<T, U>> where T : IComparable<T> where U : IComparable<U>
{
    public T f;
    public U s;
    public Pair(T f, U s)
    {
        this.f = f;
        this.s = s;
    }
    public int CompareTo(Pair<T, U> a)
    {
        return f.CompareTo(a.f) != 0 ? f.CompareTo(a.f) : s.CompareTo(a.s);
    }
    public override string ToString()
    {
        return f + " " + s;
    }
}

class Scanner
{
    string[] s; int i;
    char[] cs = new char[] { ' ' };
    public Scanner() { s = new string[0]; i = 0; }
    public string[] scan { get { return ReadLine().Split(); } }
    public int[] scanint { get { return Array.ConvertAll(scan, int.Parse); } }
    public long[] scanlong { get { return Array.ConvertAll(scan, long.Parse); } }
    public double[] scandouble { get { return Array.ConvertAll(scan, double.Parse); } }
    public string next
    {
        get
        {
            if (i < s.Length) return s[i++];
            string st = ReadLine();
            while (st == "") st = ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            i = 0;
            return next;
        }
    }
    public int nextint { get { return int.Parse(next); } }
    public long nextlong { get { return long.Parse(next); } }
    public double nextdouble { get { return double.Parse(next); } }
}

まとめ

いい感じの考察ができたので久しぶりにブログを書いた。軽くでいいから記事にする問題をこれから増やしたいと思う。↑のコードは solve関数 から見てください。