A - 元気にお使い！高橋君

NR > 1 {
    a += $1 * $2
}
END {
    print int(a * 1.05)
}

詰めて提出したらgolfで1位だった。

B - おとぎの国の高橋君

trが大活躍した。

read b
b=`echo $b | tr -d \ `  # b=${b// }
read
d=0123456789
tr -t $b $d | sort -n | tr $d $b  # tr $b 0-9 | ...

提出した後、golfで1位の人のコードを参考に修正したらまったく同じコードになってしまった。コメントは修正後のそれ。

C - 高橋君、24歳

大苦戦。分かる気がしなかったので答を見ました。 解説を理解するのもコードを書くのもあまり素早くはなかった。入力のnを剰余取るの忘れててWAした。 勉強にはなりました。

解法としては、$N = K$の時の数を求めてそれを${}_NC_K$倍すればよかった。

全ての人の手紙が別の友達のポストに入っている時、つまり$N = K$のときの順列は、完全順列とか攪乱順列と呼んで、その総数はMontmort数と呼ぶらしい。不動点のない置換とも言えるようだ。

#include <iostream>
#include <vector>
#include <cassert>
#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 = 1777777777;
ll montmort(ll k) {
    assert (0 <= k);
    if (k == 0) return 1;
    if (k == 1) return 0;
    if (k == 2) return 1;
    ll i = 2;
    ll a = montmort(i-1);
    ll b = montmort(i);
    while (i < k) { // invariant: b == montmort(i)
        ll t = i * ((a + b) % p) % p;
        a = b; b = t; ++ i;
    }
    assert (i == k);
    return b;
}
ll inverse(ll x) {
    assert (x % p != 0);
    ll y = 1, e = x % p;
    for (int i = 0; (1ll << i) <= p; ++i) {
        if ((p - 2) & (1ll << i)) y = y * e % p;
        e = e * e % p;
    }
    return y;
}
ll combination(ll n, ll r) {
    ll z = 1;
    repeat (i,r) {
        z = z * ((n-i) % p) % p;
        z = z * inverse(i+1) % p;
    }
    return z;
}
int main() {
    ll n, k; cin >> n >> k;
    cout << montmort(k) * combination(n,k) % p << endl;
    return 0;
}