AOJ 2884 Tanka Number

解法

二分探索 + 桁DP ……ではなく貪欲に解く。
基本的に上の桁から順番に数字を確定させていって、
n 番目を超えないギリギリを選択する、というよくあるやり方。
当然だが各桁は小さい数字から順番に選択していくようにする。

まず、ちょうど d 桁の短歌数は 81 * (2^(d-1) - 1) 個あるので、答えが何桁かは簡単に決定できる。
(2つの数字の決め方で 9 * 9 通り、2桁目以降の数字の割り当て方で 2^(d-1) 通りで、すべてが1桁目と同じ数になる 1通りを省くと先の式になる)
あとは数字を決めるだけ。

上から1桁目は簡単で、1桁目を決めたら、そのような短歌数は 9 * (2^(d-1) - 1) 個あるわけだから、これを超えないギリギリが1桁目で確定する。

2桁目以降は、小さい数字から(同じように)順番に見ていくのだが、

  • これまでにすでに2つの異なる数字を選んでいるか
  • まだ1つの数字しか選んでいないなら、今の桁に割り当てようとしている数字が1桁目と同じかどうか

に注意して短歌数の個数を数える必要がある。

計算量は O(logN)

ソースコード

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

using ll = long long;

int main() {
    ll n;
    while(cin >> n, n) {
        ll keta = 2, cnt = 0;
        while(cnt + 9 * 9 * ((1LL << (keta - 1)) - 1) < n) {
            cnt += 9 * 9 * ((1LL << (keta - 1)) - 1);
            keta += 1;
        }
        cnt = n - cnt;

        string ans;
        function<void(int, int, int)> solve = [&] (int d, int a, int b) {
            if(d == keta) return;
            if(a == -1) {
                for(a = 1; a <= 9; ++a) {
                    if(cnt > 9 * ((1LL << (keta - 1)) - 1)) {
                        cnt -= 9 * ((1LL << (keta - 1)) - 1);
                        continue;
                    }
                    break;
                }
                ans += '0' + a;
                solve(d + 1, a, b);
            } else if(b == -1) {
                for(b = 0; b <= 9; ++b) {
                    if(a != b) {
                        if(cnt > (1LL << (keta - d - 1))) {
                            cnt -= 1LL << (keta - d - 1);
                            continue;
                        }
                        break;
                    } else {
                        if(cnt > 9 * ((1LL << (keta - d - 1)) - 1)) {
                            cnt -= 9 * ((1LL << (keta - d - 1)) - 1);
                            continue;
                        }
                        break;
                    }
                }
                ans += '0' + b;
                if(a == b) solve(d + 1, a, -1);
                else       solve(d + 1, a, b);
            } else {
                const int ma = max(a, b), mi = min(a, b);
                if(cnt > (1LL << (keta - d - 1))) {
                    cnt -= 1LL << (keta - d - 1);
                    ans += '0' + ma;
                } else {
                    ans += '0' + mi;
                }
                solve(d + 1, a, b);
            }
        };
        solve(0, -1, -1);

        cout << ans << endl;
    }
}

感想

模擬国内本番では二分探索 + 桁DP (数が大きいので文字列同士の足し算をする) で解いてしまったので、まともなほうで解き直した。

AOJ 2787 Pipe Fitter and the Fierce Dogs

解法

一番上の行のすべての家は special pipe 確定だから、(W + 1) / 2 > K なら不可能であり、それ以外は可能である。
それ以外については、一旦 special pipe を使わないとして考えよう。
すると、以下の dp で解くことができる。
dp[i][j][k] := i 行目 j 列目の家まで考えた時に、使った家の状態が k である場合の最小コスト
i, j は家がないところを圧縮しておく(MLEするため)。
家の状態 k についてだが、これは (左上が使われている) or (真上が使われている) の2通りしかないので、丁寧に場合分けして十分。

こうして求まった答えを X とする。
もし犬を完全に回避できれば、((H - 1) / 2) * ((W + 1) / 2) のコストで common pipe を配置できる。
もし X がこれを超えていれば、その分だけ犬のマスに pipe を配置したことがわかる。
あとは、残っている special pipe を犬のマスに優先的に割りあて、それでも special pipe が残っているなら、その数だけ答えから引いてやれば良い。
サンプルにもあるが、引きすぎて負の値にならないようにすること。

計算量は O(wh) となる。

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
const int inf = 1e9;
 
int main() {
    int w, h, k; cin >> w >> h >> k;
    int n; cin >> n;
    vector<vector<int>> cost(w, vector<int>(h / 2, 1));
    for(int i = 0; i < n; ++i) {
        int x, y; cin >> x >> y;
        x--, y--;
        if(y % 2 == 0) continue;
        cost[x][y / 2] = 2;
    }
 
    k -= (w + 1) / 2;
    if(k < 0) {
        cout << -1 << endl;
        return 0;
    }
 
    const int hz = (h - 1) / 2, wz = (w + 1) / 2;
    vector<vector<int>> dp(wz + 1, vector<int>(2, inf));
    dp[0][0] = 0;
    for(int y = 0; y < hz; ++y) {
        for(int x = 0; x < wz; ++x) {
            if(dp[x][0] != inf) {
                dp[x + 1][0] = min(dp[x + 1][0], dp[x][0] + cost[x * 2][y]);
                if(x != wz - 1) {
                    dp[x + 1][1] = min(dp[x + 1][1], dp[x][0] + cost[x * 2 + 1][y]);
                }
            }
            if(dp[x][1] != inf) {
                dp[x + 1][0] = min(dp[x + 1][0], dp[x][1] + cost[x * 2 - 1][y]);
            }
        }
        const int ns = dp[wz][0];
        for(int x = 0; x <= wz; ++x) {
            for(int S = 0; S < 2; ++S) {
                dp[x][S] = inf;
            }
        }
        dp[0][0] = ns;
    }
 
    int ans = dp[0][0];
    const int tcnt = min(k, ans - hz * wz);
    const int ocnt = max(0, k - tcnt);
    ans = max(0, ans - tcnt * 2 - ocnt);
    cout << ans << endl;
}

感想

cost の2次元配列が贅沢すぎるから、map とか使ってもいいかもしれない。
ほかはまあこんなもんでしょう。

AOJ 2432 Sports Days 2.0

解法

行列累乗で解く。
A[u][v] := u -> v のウォークで最大となるもの
と定義すると、A を n 回かけた行列 An は、長さ n のウォークについて考えたものになる。これは超典型。
行列積の計算だが、A[i][j] = max(A[i][j], B[i][k] + C[k][j]) とする。
max は結合則を満たすので、上で定義した行列積について繰り返し二乗法を用いることができる。

よって、入力で行列を作ったあと、ウォークの長さ n についての二分探索をする。これで長さは求まる。
このとき、パスを陽に持つと当然TLEするので、パスの復元は後にやる必要がある。
具体的に出力する必要があるパスの長さは最大100だから、これは愚直に dp で求め直してやれば良い。

計算量は O(V^3) だが、まあまあ重いため、定数倍に注意。
以下の実装は定数倍改善をあまり考慮せずに書いているが、TL 3sec のところ 2.6sec だった。

ソースコード

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

using matrix = vector<vector<int>>;

matrix mat_op(matrix a, matrix b) {
    const int n = a.size();
    matrix res(n, vector<int>(n, -1));
    for(int k = 0; k < n; ++k) {
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < n; ++j) {
                if(a[i][k] == -1 || b[k][j] == -1) continue;
                res[i][j] = max(res[i][j], a[i][k] + b[k][j]);
            }
        }
    }
    return res;
}

matrix matpow(matrix a, int n) {
    const int V = a.size();
    matrix res(V, vector<int>(V, -1));
    for(int i = 0; i < V; ++i) {
        res[i][i] = 0;
    }
    while(n > 0) {
        if(n & 1) res = mat_op(move(res), a);
        a = mat_op(a, a);
        n >>= 1;
    }
    return res;
}


int main() {
    int V, E, K; cin >> V >> E >> K;
    matrix a(V, vector<int>(V, -1));
    for(int i = 0; i < V; ++i) {
        a[i][i] = 0;
    }
    for(int i = 0; i < E; ++i) {
        int u, v, c; cin >> u >> v >> c;
        a[u][v] = max(a[u][v], c);
    }

    auto check = [&] (int cnt) {
        const auto res = matpow(a, cnt);
        for(int i = 0; i < V; ++i) {
            for(int j = 0; j < V; ++j) {
                if(res[i][j] >= K) return true;
            }
        }
        return false;
    };
    int lb = 0, ub = K + 1;
    while(ub - lb > 1) {
        const auto mid = (lb + ub) >> 1;
        (check(mid) ? ub : lb) = mid;
    }

    if(ub == K + 1) {
        cout << -1 << endl;
        return 0;
    }

    cout << ub << endl;
    if(ub <= 100) {
        vector<int> dp(V);
        vector<vector<int>> path(V);
        for(int i = 0; i < V; ++i) {
            path[i] = {i};
        }
        for(int i = 0; i < ub; ++i) {
            vector<int> ndp(V, -1), nfrom(V, -1);
            vector<vector<int>> npath(V);
            for(int from = 0; from < V; ++from) {
                if(dp[from] == -1) continue;
                for(int to = 0; to < V; ++to) {
                    if(from == to || a[from][to] == -1) continue;
                    if(ndp[to] < dp[from] + a[from][to]) {
                        ndp[to] = dp[from] + a[from][to];
                        nfrom[to] = from;
                    }
                }
            }
            for(int j = 0; j < V; ++j) {
                if(nfrom[j] == -1) continue;
                npath[j] = path[nfrom[j]];
                npath[j].push_back(j);
            }
            dp = move(ndp);
            path = move(npath);
        }
        vector<int> ans_path;
        int maxi = -1;
        for(int i = 0; i < V; ++i) {
            if(dp[i] > maxi) {
                maxi = dp[i];
                ans_path = path[i];
            }
        }
        for(int i = 0; i <= ub; ++i) {
            cout << ans_path[i] << " \n"[i == ub];
        }
    }
}

感想

典型良問と言えるのかな。
AOJ-ICPC 700点 にしては簡単だった。

AOJ 0389 Dungeon 2

解法

木DP。つらい。
以下自分の解き方を書くけど、他の人のコード読む限り状態数はまだ減らせそう?
すくなくともテーブルでもつ必要のある状態は減らせると思う。まあいいか。

まず、部分木の根が全体としてどういう使われ方をしうるかを丁寧に見よう。
適当に考えると少なくとも以下の4通り考えればよさそう。

  • 場合1:根ノードが始点。終点は(部分木の)どこでも
  • 場合2:根ノードが終点。始点は(部分木の)どこでも
  • 場合3:根ノードが始点かつ終点
  • 場合4:根ノードはウォークの中間頂点
場合1:根ノードが始点

子から場合3のもので得をするものを使う。
また、子のうち一つは場合1のものを選択して良い。

場合2:根ノードが終点

子から場合3のもので得をするものを使う。
また、子のうち1つは場合2のものを使って良い。
ほとんど場合1と同じ。

場合3

子から場合3のもので得をするものを使う。以上

場合4

これはちょっと面倒だった。大きく分けて2通りあるからである。

  • 場合3の子ノードで得をするものを使う。子のうち1つは場合4のものを選択
  • 場合3の子ノードで特をするものを使う。子のうち2つは場合2と場合1を1つずつ選択

1つ目については、例えば子 v が中間頂点とするウォークを考えると、v から今の頂点に寄り道してまた子 v に戻るようなウォークがあるからである。
2つ目は、子 c1 から今の頂点に移ってきて、また別の子 c2 に入っていくようなウォークである。
2つ目はいいけど1つ目のを忘れやすい気がする。状態の持ち方によるかも。

計算量は O(nlogn)

ソースコード

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

using pii = pair<int, int>;

constexpr int inf = 1e9;

int main() {
    int n; cin >> n;
    vector<int> p(n);
    vector<vector<int>> g(n);
    for(int i = 0; i < n; ++i) {
        cin >> p[i];
    }
    for(int i = 0; i < n - 1; ++i) {
        int s, t; cin >> s >> t;
        g[s - 1].push_back(t - 1);
        g[t - 1].push_back(s - 1);
    }

    // 0: start, 1: last, 2: start & last, 3: inter
    int ans = -inf;
    vector<vector<int>> dp(n, vector<int>(4, -inf));
    function<void(int, int)> dfs = [&] (int v, int par) {
        dp[v][0] = dp[v][1] = dp[v][2] = dp[v][3] = p[v];
        vector<int> ch0, ch1, ch2;
        vector<pii> sub0, sub1;
        int sum2 = 0, max_sub3 = 0;
        for(auto to : g[v]) {
            if(to == par) continue;
            dfs(to, v);
            ch0.push_back(max(0, dp[to][0] - 1));
            ch1.push_back(max(0, dp[to][1] - 1));
            ch2.push_back(max(0, dp[to][2] - 2));
            sub0.emplace_back(ch0.back() - ch2.back(), to);
            sub1.emplace_back(ch1.back() - ch2.back(), to);
            max_sub3 = max(max_sub3, max(0, dp[to][3] - 2) - ch2.back());
            sum2 += ch2.back();
        }
        const int sz = ch0.size();
        sort(rbegin(sub0), rend(sub0));
        sort(rbegin(sub1), rend(sub1));
        for(int i = 0; i < sz; ++i) {
            dp[v][0] = max(dp[v][0], sum2 + ch0[i] - ch2[i] + p[v]);
            dp[v][1] = max(dp[v][0], sum2 + ch1[i] - ch2[i] + p[v]);
        }
        dp[v][2] = max(dp[v][2], sum2 + p[v]);
        // inter
        dp[v][3] = max(dp[v][3], sum2 + max_sub3 + p[v]);
        if(sz >= 2) {
            for(int i = 0; i < 2; ++i) {
                for(int j = 0; j < 2; ++j) {
                    if(i == j || sub0[i].second == sub1[j].second) continue;
                    dp[v][3] = max(dp[v][3], sum2 + sub0[i].first + sub1[j].first + p[v]);
                }
            }
        }
        ans = max(ans, *max_element(begin(dp[v]), end(dp[v])));
    };
    dfs(0, -1);

    cout << ans << endl;
}

感想

木DP、毎回頭壊れるんだけどどうすればええんや…
なんか遷移が難しいのばっかりなんだよね。実装が悪いのかなあ。

ACM-ICPC 2018 Seoul Regional 参加記 (コンテスト以外)

はじめに

2018年に韓国で行われた ICPC Seoul Regional の参加記です。
自分はチーム Zerokan_Sunshine としてでました。
チームメイトはいつもの kazuma, nakano です。

この記事はコンテスト以外の部分に絞って書いたものです。
コンテストの内容はこちらから。
suikaba.hatenablog.com


箇条書き形式で書きます。

各日の流れ

出発前日 (10/31)

  • 生活習慣が壊れていたので当然のように徹夜することになる。

出発日 (11/1)

  • 12時ぐらいに出発するいいチケットが取れた
  • 韓国近い、一瞬で到着する
  • 仁川国際空港で昼ごはん。そんなに辛くない

f:id:Suikaba:20181101151720j:plain

  • ホテルまでが遠すぎる(空港から2時間ぐらい)
  • 晩ごはん

f:id:Suikaba:20181101191319j:plain

  • 晩御飯の店、完全に韓国語 only で何言ってるか全くわからなかった
    • 自分が何を注文したのかもわからないまま大量のご飯が出てきた
    • ちなみにかなり美味しかった
  • 疲れたので適当に就寝

ラクティス (11/2)

  • 朝はロッテリア
  • 大学までは近かったので歩いていった
  • ラクティスはまあ適当に、A問題は不可能だった
  • 晩ごはん(会津勢と食べたかったけど、ホテルも遠いしいろいろあってご一緒できなかった)
    • 写真の左のやつがかなり辛かった
    • これとは別に唐辛子単体で出てきたからまるごと一気に食べた
    • これが完全にミスで、あまりの辛さに10分ぐらい喋れなくなった
    • 翌日ずっとお腹壊れてたの完全にこれのせいだろ

f:id:Suikaba:20181102183506j:plain

本番 (11/3)

  • 朝は SUBWAY
  • コンテストは別の記事に
  • 閉会式がほぼほぼ韓国語 only だったので、はっきり言ってかなり暇だった
  • yes/no おじさんが yes/no じゃなかった(韓国語なので)
  • 晩御飯は懇親会で。日本と違い基本的に飯はずっと補給されてそう。まあまあ美味しかった
  • 疲れたので帰って寝る…と言いたかったが Snackdown があった
  • 仮眠とってから kazuma と出た。5完で150位ぐらいだったかも、まあ6完すべきだったぽいけど通過なのでセーフ
  • ほんとに就寝

帰国 (11/4)

  • 寝坊する
  • 時間がないので急いで空港へ
  • 昼ごはん。おいしい

f:id:Suikaba:20181104131454j:plain

  • おみやげを買うはずが時間がない、適当に入ってなんか勧められた(?)やつを買う
    • 韓国のりかったら5000円ぐらいした、こんなに高いとは知らなかった
  • 搭乗予定時刻より10分ぐらい遅刻したけど大丈夫だった
  • 帰国

まとめ

観光できなかったのは残念だったけど、ご飯については割と色々食べられたので満足。
ホテルもいいところだったし。
もし今度来ることがあったら、そのときはちゃんと観光したい。

ACM-ICPC 2018 Seoul Regional 参加記 (コンテスト)

はじめに

2018年に韓国で行われた ICPC Seoul Regional の参加記です。
自分はチーム Zerokan_Sunshine としてでました。
チームメイトはいつもの kazuma, nakano です。

この記事はコンテストについて書いたものです。

チームの役割分担は以下の通り

  • nakano (考察担当、基本的に実装はしない)
  • kazuma (考察、実装担当、理想は僕と交代交代で書く)
  • suibaka (実装担当、めんどくさいやつとかやるだけとか構文解析とか幾何とか)

ちなみに kazuma 視点の参加記もあります。
ICPC Seoul Regional 2018 参加記 - kazuma8128’s blog

コンテスト

一応コンテストの流れに沿って(覚えてる範囲で)書く。

D 問題

  • PCの設定とかやってたら D がやるだけだと教えられる
  • なんだこの問題はたまげたなあ
  • AC(15分)

虚無

  • いつもならここで次のコーディングにすぐ入るはず…
  • しかし今日は書く問題が降ってこない、完全に異常事態
  • どうもパット見の難易度判定に失敗しまくったらしい
    • D の次 C とか考え始めてたからね、やばいね
  • ここでなんと1時間以上溶けた。

F 問題

  • やることがないのでやるだけの F を書き始める
  • さっさと解くつもりだったがバグる
  • 一番外側にカッコが付いていてはいけないのを完全に忘却していて時間を溶かしてしまう
    • (a + b) とかはだめだったけど OK 判定だった
  • K、L のあとになったけど通す。これは大反省

K 問題

  • 僕が別のやってる間に kazuma にやってもらった
  • nakano から問題概要を聞いた時、脳内で R, G, B の3色があると思って悩んだ
  • nakano が2色だと教えてくれた
  • kazuma も僕と同じく3色だと思っていたらしく、2色なら 2-SAT やるだけやんけ!となり、書いて AC (103min)

L 問題

  • F がなぜか通らない(前述の通り)ので、最悪になる前に L を考える
  • 連続して働く必要のある時間がバラバラだと思っていて、しばらく不可能じゃんとなっていた
  • よく読んだら w は全員固定だった、じゃあ貪欲だねとなる
  • 書いたらなんか RE した。理由は n と m を間違えていた(このミスするの何度目?
  • AC (136min)
  • ちなみに書いてる途中に腹痛がピークを迎えたので、「トイレに行っていい?」と kazuma に聞いたら「ACしたらいいよ」と言われた。鬼か?(まあ当然っちゃ当然ですが

G 問題

  • nakano がずっと式やら図形やらとにらめっこして式を生成していた
  • 生成したのを kazuma になげて書いて AC (172min)
  • 積分せずに楽できるか、みたいな問題だったらしい?しらんけど

A 問題

  • 実は最初からたまに考えていて、簡単に解けるんじゃないの?と思っていた
  • しかし完全に虚無っていたのであまり詰められず、後半まで放置されていた
  • kazuma に投げてしばらくしたら starry sky tree で殴れるね、となりそれで書いてもらうことに
  • なんか細かいミスをしていたらしくWAが生えるが、まあすぐ修正して AC (237min)

B 問題

  • nakano から概要を聞く
  • nakano から解法を聞く
  • 書いて AC (238min)
  • なんでこの問題がここまで放置されていたかと言うと、ここまでなんと誰も読んでいなかった(は???)
  • あと普通に問題文が難しすぎるだろ

E 問題

  • これも最初に考えてはいたんだけど、うーむとなっていた
  • kazuma はなんと max の部分が sum だと思っていたらしい、そりゃ解けんわ(勘違いしているとは思わなかった
  • 解けることはわかっていたが、これに着手したのが最後の20分とかだったので間に合わず…

J 問題

  • nakano に概要を教えてもらう
  • 適当にマージしていったらできるんじゃないの、みたいなふわふわ解法で書き始める
  • 入力を取るのが難しかった(変数の並びが不自然だったような…
  • 書いた、バグバグ
  • バグいっぱい
  • というか解法間違えてない?間違えてるね
  • 終了

C 問題

  • AOJに似たやつがあったけど、あれは並び替え不可能だった
  • どうせいい感じの並びが存在するに決まっていて、という感じだった
  • しかしCの考察にさける時間がほとんどなく、結局よくわからない嘘を書いてサンプルが合わない、みたいなことになっていた気がする

I, H 問題

  • 見るからにヤバイので自然に回避していた、結果的には正しかった

結果

7完 17th でした。大学別では10位という残念な結果に。
UKUNICHIA に負けたのは普通に悔しい。

反省

  • 序盤の動き方が最悪で、ここまでひどいとリカバリー不可能
  • とはいってもこのセットでパット見で難易度推定するのは今の自分達には厳しかったのかなあ
    • 簡単なのは問題文が難しい、読みやすいのは大体そこそこ難しい、みたいな
  • Standings もあんまり活用できなかった、解かれる問題が割とバラバラだったので
  • こういうときは他の人じゃなくて自分たちを信じて、あれこれ行ったり来たりせず解けそうと思った問題にある程度張り付いたほうが良かったのかも?
  • 問題読解が雑すぎた。問題を難しくして解けなくするのは最もやってはいけないこと。
  • 今回は自分はほとんど問題を読まなかったので、多分それも良くない
  • 問題を読むときは Input/Output まできちんと読むべき
  • 問題概要を伝えるときは、聞き手が勝手に脳内補完をしないような伝え方をすべき
  • 逆に問題概要を聞くときは、勝手に脳内補完しないほうがいい

まとめ&感想

今回のセットで10完が当たり前な韓国勢の恐ろしさを感じました。
普通に事故る可能性高いと思うんですが、そうでもないんでしょうか……。
せめて E は通したかったなーという感じです。J は厳しかったかも。
今の実力的には8完で及第点だったのかなと思っています。しかしうまくいかないもんだなあ。
でもいい経験になったと思って、横浜大会ではいい成績を残せるようがんばります。

Codeforces Round #320 (Div.1) C. Weakness and Poorness

* 問題文
http://codeforces.com/contest/578/problem/C

解法

max 取ってるし、x についての weakness を f(x) とすると、下に凸な関数になりそう。
なので3分探索する。
x を決めたときの a[i] - x 列の区間和最大、最小は線形で解ける。
左から累積和を見ていって、それまでの最大値と最小値を持っておけばOK。
よって O(nlog|a|) で解ける。

関係ないけど、区間Add区間和最大セグ木が途中でほしいなーと思って考えて、無理じゃね?となった。(区間Addで壊れる)

ソースコード

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

constexpr double inf = 1e9;
constexpr double gratio = (std::sqrt(5)+1)/2.0;

template <typename F>
double golden_section_search(F f, double lb, double ub, int cnt) {
    double x1 = (ub-lb)/(gratio+1) + lb,
        x2 = (ub-lb)*gratio/(gratio+1) + lb;
    double v1 = f(x1), v2 = f(x2);
    for(int i=0; i<cnt; ++i) {
        if(v1 < v2) {
            ub = x2;
            x2 = x1;
            v2 = v1;
            x1 = (ub-lb)/(gratio+1) + lb;
            v1 = f(x1);
        } else {
            lb = x1;
            x1 = x2;
            v1 = v2;
            x2 = (ub-lb)*gratio/(gratio+1) + lb;
            v2 = f(x2);
        }
    }
    return (lb+ub)/2;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cout << fixed << setprecision(10);
    int n; cin >> n;
    vector<double> a(n);
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    auto f = [&] (double x) {
        vector<double> sum(n + 1);
        double min_s = 0, max_s = 0;
        double res = 0;
        for(int i = 0; i < n; ++i) {
            sum[i + 1] = sum[i] + a[i] - x;
            res = max({res, abs(sum[i + 1] - max_s), abs(sum[i + 1] - min_s)});
            min_s = min(min_s, sum[i + 1]);
            max_s = max(max_s, sum[i + 1]);
        }
        return res;
    };
    const auto opti = golden_section_search(f, -10000, 10000, 100);
    cout << f(opti) << endl;
}