出てなかったので。

A - 点数変換

普通に。listっぽかったのでhaskellした。

得点が全部同じ場合は考え漏らしてて、サンプルに助けられた。

module Main where

import Control.Applicative
import Control.Monad
import Text.Printf

main :: IO ()
main = do
    [n, a, b] <- map read . words <$> getLine
    xs <- replicateM (round n) readLn
    let p = b / (maximum xs - minimum xs) :: Double
    if isInfinite p
        then print (-1)
        else do
            let q = a - p * (sum xs / n)
            printf "%.7f %.7f\n" p q

pythonにもmin,max,sumはあるので、そちらの方が綺麗だったかも。

B - 難易度

DPっぽいのした。配列なのでc++で。解説のと同じ。

入力はソート済みだと誤認して1WA。サンプルがそうだったから勘違いした。 ソート済みという事実を使うコードを書くときはassert (std::is_sorted(...));を置くようにすべきか。

#include <iostream>
#include <vector>
#include <algorithm>
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
#define repeat(i,n) repeat_from(i,0,n)
typedef long long ll;
using namespace std;
constexpr ll p = 1000000007;
int main() {
    int n; cin >> n;
    vector<int> d(n); repeat (i,n) cin >> d[i];
    sort(d.begin(), d.end());
    vector<int> dp[4]; repeat (k,4) dp[k].resize(n);
    repeat (i,n) dp[0][i] = 1;
    repeat_from (k,1,4) {
        ll acc = 0;
        int i = 0;
        int j = 0;
        while (j < n) {
            while (i < j and 2 * d[i] <= d[j]) {
                acc += dp[k-1][i];
                acc %= p;
                ++ i;
            }
            dp[k][j] = acc;
            ++ j;
        }
    }
    ll acc = 0;
    repeat (i,n) {
        acc += dp[3][i];
        acc %= p;
    }
    cout << acc << endl;
    return 0;
}

DPには苦手意識があるけど書けたよやったねってなった。でも累積和を横に置きながら舐めてるのでメモ化再帰に直せないしDPではない気がする。

C - 転倒距離

5WA。つらかった。

  • AとBに同じ置換をしても転倒距離は保存されるから、Aがa[i] == iとなるように置換すればよい
  • そのように置換したBの各要素のそれより後ろでそれより小さい要素の数の総和が転倒距離
  • range sum query とか使うのかな？

とここまで考えて、これ以上分からないし、segment tree嫌いだし、と諦めて解答を見た。見てからも大苦戦した。 segment treeへの苦手意識を少しでも削ろうと書き下ろしたのもまずかった。 assert (false);とか置いたのを提出してバグ切り出すなどして無理矢理通した。人に見せたくないコードが出来上がっていた。111行。

off-by-oneだとかの数値系のバグは苦手だ。誰か隣で見ていてくれたらと思う。

また、領域外アクセス時でなくdestructorでsegvしてgdbが効かないのがあったので、以前人に教えてもらったa.at(i)を試した。 a[i]と違ってアクセス前に境界checkをしてくれるすごいやつ。とても便利だった。