AtCoder Regular Contest #004 C: 平均値太郎の憂鬱

問題

ここ参照。

方針

本番中は二分探索をしていた。ほとんどのケースは通っていたのだけれど、いくつかのケースで落ちていた。分数が既約分数だと思い込んでいたけど、そうじゃない場合もあるようだ。おそらく落ちた原因はそれだと思う。
二分探索よりスマートでシンプルな解法があって、以下の2次不等式をiについて解けばよい。

平方根とか出てくるけど、マージンを取るような方向の近い整数に丸めるとよい。

ソースコード

using namespace std;

#define REP(i, n) for(int i=0; i<(int)(n); i++)
#define FOR(i, s, e) for (int i = (int)(s); i < (int)(e); i++)

long long gcd(long long a, long long b) {
    if (!b)
        return a;
    return gcd(b, a%b);
}


int main() {
    long long x, y;
    char c;

    cin >> x >> c >> y;
    long long g = gcd(x, y);
    x /= g;
    y /= g;
    
    bool res = false;
    for (long long i = (2*x-y)/y/y; i <= (2*x+y)/y/y+1; i++) {
        long long n = i*y;
        long long sum = n*(n+1)/2;
        long long m = sum - i*x;
        if (1 <= m && m <= n) {
            res = true;
            cout << n << " " << m << endl;
        }
    }

    if (!res)
        puts("Impossible");
    return 0;
}

AtCoder Regular Contest #003 B: さかさま辞書

調子に乗ってもう一問解きました。pythonっぽいことをいろいろやってみました。

1. リスト内包表記
2. 逆順リスト
3. key(ソート基準)を指定したソート

N = int(raw_input())
wd = [raw_input() for line in range(N)]
wd = sorted(wd, key = lambda x : x[::-1])
for w in wd:
    print w

AtCoder Regular Contest #003 A: GPA計算

AtCoderの問題を解きました。なかなかいいですね。AtCoder。日本語だし、日本人にやさしい時間に開催されるし、いろいろな言語が使えるし。

def f(x):
    if x == 'F':
        return 0
    return 4-ord(x)+ord('A')
 
N = int(raw_input())
str = raw_input()
p = map(lambda x : f(x), str)
p = 1.0 * reduce(lambda a, b : a+b, p) / N
print p