Codeforces Round #85 Div. 2

Codeforces

ど う し て 通 ら な か っ た ！

  • A. Petya and Strings

大文字と小文字が混ざった文字列が与えられるので、辞書順比較せよ。

str_a = gets.chomp.downcase
str_b = gets.chomp.downcase

puts str_a <=> str_b
  • B. Petya and Square

マークをつけたマスの直ぐ側を切らずに、正方形を同じ形に切ることができるか。

n, x, y = *gets.chomp.split(" ").map{|s| s.to_i}
half = n / 2
nx = [x, n - (x - 1)].min
ny = [y, n - (y - 1)].min
#p half, nx, ny
if nx == half and ny == half
  puts "NO"
else
  puts "YES"
end
  • C. Petya and Inequiations

条件を満たす数列を見つけよ。
※※※以下、デバッグ中の撃墜コード※※※

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;

int test1(vector<int> v) {
    ll ans = 0;
    int n = v.size();
    for(int i = 0; i < n; i++) {
        ans += v[i] * v[i];
    }
    return ans;
}

int test2(vector<int> v) {
    ll ans = 0;
    int n = v.size();
    for(int i = 0; i < n; i++) {
        ans += v[i];
    }
    return ans;
}

void disp(vector<int> v) {
    int n = v.size();
    for(int i = 0; i < n; i++) {
        cout << v[i] << endl;
    }
}

int main() {
    ll n, x, y; cin >> n >> x >> y;
    vector<int> v(n);
    v[0] = y - (n - 1);
    for(int i = 1; i < n; i++) {
        v[i] = 1;
    }
    if(test1(v) >= x && test2(v) <= y)
        disp(v);
    else
        cout << -1 << endl;
    return 0;
}
  • D. Petya and Divisors

n個のクエリー(x[i], y[i])が与えられる。
x[i]の約数のうち、x[i - yi] 〜 x[i - 1]の約数を除いた個数を出力せよ。
ただし、y[i] == 0の時は、x[i]の約数の個数を出力せよ。

TLEに泣かされました。
※※※以下のコードはTLEします※※※

#include <cstdio>
#include <algorithm>
#include <set>
#include <vector>
#include <cmath>
using namespace std;

int main() {
    int n;
    scanf(" %d", &n);
    vector<int> qx(n);
    vector<int> qy(n);
    vector<vector<int> > div(n);
    for(int i = 0; i < n; i++) {
        scanf(" %d %d", &qx[i], &qy[i]);
    }

    for(int i = 0; i < n; i++) {
        for(int j = 1; j * j < qx[i]; j++) {
            if(qx[i] % j == 0) {
                div[i].push_back(j);
                div[i].push_back(qx[i] / j);
            }
        }
        if(ceil((double)sqrt(qx[i])) == floor((double)sqrt(qx[i]))) {
            div[i].push_back((int)sqrt(qx[i]));
        }
        sort(div[i].begin(), div[i].end());
    }

    for(int i = 0; i < n; i++) {
        if(qy[i] == 0) {
            printf("%d\n", div[i].size());
        }
        else {
            set<int> s;
            int in = div[i].size();
            for(int j = 0; j < in; j++) {
                s.insert(div[i][j]);
            }

            for(int k = i - qy[i]; k < i; k++) {
                in = div[k].size();
                for(int j = 0; j < in && !s.empty() && *s.rbegin() >= div[k][j]; j++) {
                    s.erase(div[k][j]);
                }
            }
#if 0
            cout << "---set---" << endl;
            for(auto it = s.begin(); it != s.end(); ++it) {
                cout << *it << endl;
            }
            cout << "---answer---" << endl;
#endif
            printf("%d\n", s.size());
        }
    }
    return 0;
}