年始初めてのRatedコンテストはcodechefでした。良くもなく、悪くもなく。

Happy New Year!

わかりやすい英語で助かります。24時の何時間前か、なので24-xでよいです。

void solve() {
    int x;
    cin >> x;
    cout << 24-x << "
";
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    solve();
}

Delete Not Equal

一瞬面白いと思ったがギャグ。 0と1が両方あるときは適当に消していくことで残り1つまで消すことができるので1、反対にどちらかしかないときは操作ができないのでNが答えになります。

#define rep(i,n) for (ll i=0;i<n;++i)
void solve() {
    int n;
    string s;
    cin >> n >> s;
    bool flag = true;
    rep(i, n-1) {
        if(s[i] != s[i+1]) {
            flag = false;
        }
    }
    if(flag) {
        cout << n << "
";
    } else {
        cout << "1
";
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t; cin >> t;
    while(t--) solve();
}

Lottery Tickets

$A$をソートします。自分の持っている値の左右を見て値があるならその中央まで、なければ$1$($10^6$)までを取ることができます。これらを足し合わせた結果が、自分が勝てる数です。 数直線を書いて、自分が勝てる範囲を図示するとわかりやすそうです。

#define all(v) v.begin(),v.end()
#define rep(i,n) for (ll i=0;i<n;++i)

void solve() {
    int n;
    cin >> n;

    vll a(n);
    rep(i, n) cin >> a[i];
    ll me = a[0];
    sort(all(a));

    rep(i, n) {
        if(a[i] == me) {
            ll ans = 1;
            if (i != 0) {
                ans += (a[i]-a[i-1])/2;
            } else {
                ans += a[i]-1;
            }
            if (i != n-1) {
                ans += (a[i+1]-a[i])/2;
            } else {
                ans += 1000000 - a[i];
            }
            cout << ans << "
";
            return;
        }
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while(t--) solve();
}

はじめは$1$から$10^6$のそれぞれについて、「その値は自分が勝てる値であるか？」を判定する事を考えていました(二分探索で可能)が、途中で軌道修正できてよかったです。

Temperature Balance

どのように温度を移動させても(つまり、どの部屋で0をつくっても)合計のコストは変わらさそうです。ということで、左から順に「自分より右にある正負が反対の部屋」に移動させる貪欲法で解くことができます¹。

#define rep(i,n) for (ll i=0;i<n;++i)
void solve() {
    int n;
    cin >> n;

    priority_queue<P, vector<P>, greater<P>> pos, neg;
    int a;
    rep(i, n) {
        cin >> a;
        if(a > 0) {
            pos.push({i, a});
        } else if(a < 0) {
            neg.push({i, a});
        }
    }

    ll ans = 0;
    while(!pos.empty() && !neg.empty()) {
        auto [pi, pval] = pos.top();
        auto [ni, nval] = neg.top();

        pos.pop();
        neg.pop();
        ll res = pval + nval;
        if(pi < ni) {
            ans += pval * (ni - pi);
        } else {
            ans += -nval * (pi - ni);
        }
        if(res>0) {
            pos.push({max(pi, ni), res});
        } else if(res<0) {
            neg.push({max(pi, ni), res});
        }
    }
    cout << ans << "
";
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while(t--) solve();
}

Grid Construction (Odd)

$N=5$の構築を試すと、

1 2 4 5 3
2 4 5 3 1
4 5 3 1 2
5 3 1 2 4
3 1 2 4 5

が条件を満たしそうです。これを見ると、右上から左下への対角線にいい感じに配置していけば良さそうです。で、実際にこれはうまくいきます。証明はAC(は？)

#define rep(i,n) for (ll i=0;i<n;++i)
#define rep2(i,a,n) for (ll i=a;i<n;++i)
using vvll = vector<vector<ll>>;

void solve() {
    int n;
    cin >> n;
    vvll a(n, vll(n));

    rep(i, n) {
        a[n-i-1][i] = (n+1)/2;
    }

    int now = 1;
    rep(i, n-1) {
        int j = 0;
        int k = i;
        while(k >= 0) {
            a[k][j] = now; 
            k -= 1;
            j += 1;
        }
        now += 1;
        if(now == (n+1)/2) {
            now += 1;
        }     
    }

    now = 1;
    rep2(j, 1, n) {
        int i = n-1;
        int k = j;
        while(k < n) {
            a[i][k] = now;
            k += 1;
            i -= 1;
        }
        now += 1;
        if(now == (n+1)/2) {
            now += 1;
        }     
    }

    rep(i, n) {
        rep(j, n) {
            cout << a[i][j] << ((j == n-1 ? "
" : " "));
        }
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while(t--) solve();
}

Grid Construction (Even)

こいつに脳を破壊されました。

とりあえず、Oddの構築の拡張を考えます。対角線同士の和を$2\times\sum_{i=1}^Ni$にすれば良さそうなので、とりあえず対角線には$\frac{N}{2}$と$\frac{N}{2}+1$をそれぞれ置いておきます。 ここでOddで作った構築をよく見ると、各行と各列にはそれぞれ1からNの値が1個ずつ入っており、この形なら自明に条件を満たしそうです。これを簡単に作る方法を色々と試すと、偶数なら左下に、偶数なら右下の方に伸ばしていけば良さそうです。そとにはみ出した分はトーラスだと思うことにすると、この構築がうまくいきます。

構築例($N=6$)

4 1 2 5 6 3
1 4 5 2 3 6
6 5 4 3 2 1
5 6 3 4 1 2
2 3 6 1 4 5
3 2 1 6 5 4

ということで、これを頑張って実装すると通ります。例によって証明はACです。

#define rep(i,n) for (ll i=0;i<n;++i)
#define rep2(i,a,n) for (ll i=a;i<n;++i)
using vvll = vector<vector<ll>>;

void solve() {
    int n;
    cin >> n;
    vvll a(n, vll(n, -1));

    rep(i, n) {
        a[n-i-1][i] = n/2;
    }
    rep(i, n) {
        a[i][i] = n/2+1;
    }

    ll now = 1;
    ll addr = -1;
    rep2(j, 1, n-1) {
        ll k = j;
        rep(i, n) {
            a[i][(k+2*n)%n] = now;
            k += addr;
        }
        addr *= -1;
        now += 1;
        if(now == n/2) {
            now += 2;
        }

    }
    rep(i, n) {
        rep(j, n) {
            cout << a[i][j] << ((j == n-1 ? "
" : " "));
        }
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while(t--) solve();
}

Grid Construction (Even)を通した時点で残り2分も残っておらず、ここで時間切れでした。構築をノーペナでもっと早く解けるようになりたい...