naoya_t@hatenablog

いわゆるチラシノウラであります

SRM554 DIV1 Medium<500> : TheBrickTowerMediumDivOne

DIV1 Medium Random Challenge第1回。

1. 塔の高さは高い順に使うけど、1回しか現れちゃいけない

てことは大きい順に使っていけば(一番大きいやつは端に来るべき)いいのか? ソートして [4 7 5] -> [(4 0) (7 1) (5 2) ] -> [(4 0) (5 2) (7 1)] -> (0 2 1)

一番小さいやつと2番めに小さいやつの位置が入れ替わっても結果を左右しない -> 頭の2つは入れ替え可能

→WA

反例。5347126 → 5312467 (=0145263) でOK(1234567じゃなくて) 一番低い1を挟んで、左が\\、右が//になってるのか

2. 塔の高さが、大きい順に(一番低い塔の高さを除いた)N-1個が使われる:\///(底が1つだけ)ならどういう順番でもいい;一番大きいやつは端に来るべき

一番左は必ず0にできる;

大きい順にソートして、インデックスちっちゃいのを見つけて貪欲に左に置いていくか

5347126 → (5 0) (3 1) (4 2) (7 3) (1 4) (2 5) (6 6) 
ソートして (1 4) (2 5) (3 1) (4 2) (5 0) (6 6) (7 3)

cdrを取って4512063、ないしその逆の3602154 から、辞書順トップを編み出したい。左から貪欲に、一番小さいのを拾っていくだけ、か。使わなかったやつを右に(逆順で)くっつける。

同じ値が複数来る場合どうしたらいい?1つの値で代表させてみては

→WA

45 17 33 41 17 12 17とかアウトだった

3. インデックスだけじゃなくて、元の数字を覚えてないとダメだ。

そのためには、pair<int, int> の第2要素でソート、みたいな事をサクッと書きたい。 元の値を保持してさえいれば、逆順insert、とかややこしく考えずに単純ソートで行けるから。

→AC

今回学んだこと

  • λで済むことはλで済まそう
auto p = [](ii a, ii b) { return a.second < b.second; };
int a = (int)(min_element(du.begin()+ix, du.end(), p) - du.begin());

実装

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <functional>

#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#define NDEBUG
// BEGIN CUT HERE
#include "cout11.h"
#undef NDEBUG
// END CUT HERE
#include <cassert>

using namespace std;
#define rep(var,n)  for(int var=0;var<(n);++var)
#define all(c)  (c).begin(),(c).end()
#define found(s,e)  ((s).find(e)!=(s).end())
typedef pair<int,int> ii;

inline int argmin(vector<int>& vec, int from, int to) {
    return (int)(min_element(vec.begin()+from, vec.begin()+to) - vec.begin());
}

template <typename T>
inline int argmin(vector<T>& vec, int from, int to) {
    return (int)(min_element(vec.begin()+from, vec.begin()+to) - vec.begin());
}

class TheBrickTowerMediumDivOne {
    public:
    vector<int> find_01_WA(vector<int> heights) {
        int N = heights.size();
        vector<ii> tmp(N);
        rep(i, N) tmp[i] = ii(heights[i], i);
        sort(all(tmp));
        if (N >= 2) {
            if (tmp[1].second < tmp[0].second) {
                swap(tmp[0], tmp[1]);
            }
        }
        vector<int> ans(N);
        rep(i, N) ans[i] = tmp[i].second;
        return ans;
    }
    vector<int> find_02_WA(vector<int> heights) {
        int N = heights.size();
        vector<ii> du(N);
        rep(i, N) du[i] = ii(-heights[i], i);
        sort(all(du));

        vector<int> ord;
        map<int, int> vis;
        map<int, set<int> > mp;
        rep(i, N) {
            int v = du[i].first, x = du[i].second;
            if (found(vis, v)) {
                int x0 = vis[v];
                mp[x0].insert(x);
            } else {
                vis[v] = x;
                ord.push_back(x);
                mp[x].insert(x);
            }
        }

        int ix = 0;
        vector<int> head, tail;
        while (ix < ord.size()) {
            int a = argmin(ord, ix, ord.size());
            tail.insert(tail.end(), ord.begin()+ix, ord.begin()+a);
            head.insert(head.end(), ord[a]);
            ix = a+1;
        }
        head.insert(head.end(), tail.rbegin(), tail.rend());

        vector<int> ans;
        for (int i=0; i<head.size(); ++i) {
            int x = head[i];
            ans.insert(ans.end(), all(mp[x]));
        }
        return ans;
    }
    vector<int> find(vector<int> heights) {
        int N = heights.size();
        vector<ii> du(N);
        rep(i, N) du[i] = ii(-heights[i], i);
        sort(all(du));

        int ix = 0;
        vector<ii> head, tail;
        while (ix < N) {
            auto p = [](ii a, ii b) { return a.second < b.second; };
            int a = (int)(min_element(du.begin()+ix, du.end(), p) - du.begin());

            for (int i=ix; i<a; ++i) {
                tail.push_back(ii(-du[i].first, du[i].second));
            }
            head.insert(head.end(), du[a]);
            ix = a+1;
        }
        sort(all(tail));
        head.insert(head.end(), all(tail));

        vector<int> ans(N);
        for (int i=0; i<N; ++i) {
            ans[i] = head[i].second;
        }
        return ans;
    }
};