ABC145

ABCのおかげで心の調子が戻った。

A - Circle

久しぶりにすごく簡単なAで、タイムも31秒と短かった。

B - Echo

s[i]とs[i + n / 2]を比較するだけやんと思いドヤ顔でサンプルを試すも通らない。Nが奇数のケースを見落としていた。これの難しいバージョンみたいな問題がEとかで出されるときは「Nは偶数」みたいな制約あるじゃん。思い込みだね。サンプルなかったら気づくのにどれくらいかかったんだろう。

C - Average Length

Nが小さいので言われたとおりに実装するだけ。これN!通りの列挙を素早くやるの、どうやるんだったかなあ。素早くは書けないけど普通に書けるので書いたけど。Nがかなり小さいのでDFSの深さを持つ必要もないということで、経路の数は末端ではなく道の数/(N-1)とした。ちょっと誤差が気になったけど提出してAC。

が、言われてみれば当然のO(N^2)解法が存在した。Nが小さいのを見てN!に行ってしまうの本当にお前その頭は何のためについてるんだという感じ。しかも提出したコードは間違っていた。ちゃんとACが取れるコードではあるけど、それはO(N^2)解法が存在するような順番関係ない問題だからで。あと、N!のときにnext_permutationを思いつかなかった。

D - Knight

碁盤を用意して行ける場所に石を置いていくとパスカルの三角形になるので、あとは証明というか詰めていくだけ。まず（到達できるためには）X+Yは3の倍数である必要がある（和は移動毎に3増えるため）。3で割れば移動回数がわかる（和は移動毎に3増えるため）。んで共通する(1, 1)のナナメ移動を引いてやれば、まんまパスカルの三角形になる。コンビネーションを1回だけ求めるという状況が珍しいので、どうやるか迷った（ライブラリの最近使ってなかったやつを貼った）。

E - All-you-can-eat

時間が来ても注文できなくなるだけで食べる続けることはできるという点がスパイスで、あとは完全にただのナップサック問題。ナップサックは書けるけど苦手。スパイスの部分を楽しむ前に脳内で復習しないといけない。ソートしてDPというのが浮かぶけど、最後に食べるのは時間がかかるものがいいし美味しいものがいいしで、何でソートするかわからない。たぶん、そんなことしなくても順番を変えて2回やれば通るんだろうなとも思った。しかしそれはやりたくないので考える。ナップサックは順番関係ないが、この問題の場合は多少関係あって、食べる料理の中で最も時間がかかるものが最後であれば十分とわかる。つまり美味しさ関係なく時間が短い順にソートして、i番目までで実現できる満足度を各（0からT-1までの）時間毎に求めて、残りの中で美味しさ最大のものを追加で一つ食べるとすればよい。

と、これを書いていて気づいたけど、自分の実装は微妙に嘘だった。以下の入力で1と出力してしまう（正しくは2）。最初の要素が時間内に食べきれない場合、その選択肢を捨ててしまう。最初で最後に食べるんなら時間内じゃなくてもいいのに。うーん。思考がガッチリしてないなあ。

2 1
1 2
1 1

F - Laminate

コンテスト中に書いたソースコードとコメントをここに供養する。全くわからなかった。DPは思いつかないなあ。こういう、横につながったやつで不可能に思えるものはDPっていうの忘れてたなあ。セグ木はちょっと考えたけど。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;
using ll = long long;

int main() {
    int n, k;
    cin >> n >> k;

    vector<int> h(n);
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }

    vector<int> v(h);
    v.push_back(0);
    sort(v.begin(), v.end());
    auto it = unique(v.begin(), v.end());
    int m = it - v.begin();

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (h[i] == v[j]) {
                h[i] = j;
                break;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        cout << h[i] << ' ';
    }
    cout << endl;

    //座標圧縮というかランレングスみたいなことする必要あるかな
    //そもそもK=0でもけっこう難しい
    //下から見ていって、一旦分離したら戻ることはない
    //増やすのがいいこともある
    //階段になっているときは一番高いのを消す（または他の高さに合わせる）しか意味ない 平らにする意味はない
    //端っこはノーリスクで消せる 山を消すか谷を埋めるかの判断難しくない？
    //谷があるのはまずいが山があるのはまあいい Kによって戦略が変わる
    //最終的な高さを決め打ちしてしまう
    //目標より高いのは問答無用で低くする しかしどこまで低くするかはわからない
    //中央に消し切れない幅の塔が立っていたら高さ決め打ちしても簡単にならないよな
    //端っこをノーリスクで消せるならKは使い切るとしていいな

    return 0;
}