Codeforces Round #136 (Div. 2) (No. 221)

CodeForces 本番 C++

http://codeforces.com/contest/221

本番

A

やるだけ。
少し試せば法則性が分かる。
最初、関数の値を返す問題と思い込んで、その値を求めて1WAしてしまった。

B

やるだけ。
約数を試すだけ。
なんかi*iがオーバーフローするとか勘違いしてResubmitしてしまった。本当は問題ないのに！

C

初め、入力はpermutationだと思い込んで、それはdfsで閉路を数えればいいのはわかってたのでそうしてしまった。そのまま気づかずに1WA。
結局気づいたあともその方向性ではできず、結局時間がかかってしまった。
極めて単純なコードだけど、合ってるかはわからない

D

初め、平方分割とかしてみた。でもマージするのに、その集合の要素の数がかかってて、当然全然遅すぎる。
マージは要素それぞれ覚えとく必要があるからできないかなーとか考えてた。
最終的に求めるのはそれぞれの要素関係ない訳だから、うまくできるのだろうか？
それとも別の方法か？
結局できなかった

Challenge

Room見たらなんかBをHackされてる人がたくさんいて、あーもったいなかった、と思った。
そのあと、Cを見たら、
O(N^2)やってる人がいたのでHack、
バブルソートやってる人がいて、バブルソートは最悪O(N^2)だっけ？と思って調べたら平均もN^2だったので、ランダムケース投げてHack
あと、もう一人O(N^2)やってる人を見つけたが、時間切れ

System Testing

C落ちるなよーと思いながら。
でも同じようなコードで通ってる人いたので大丈夫かなー
はい通った

結果

A: +438
B: +890
C: +976
Challenge: +200
Rank: 289/1410 (Div. 2)
Rating: 1646→1605

コメント

C遅すぎる。やはり間違った勘違いと、その方向に行ってしまう事は絶対駄目だ。
意外とTLEが多いんだなあと。Div.2の場合だが。Pretestでは大きいケースは試されない傾向にあるのかな。
Hackは場合によっては+500〜とか十分ありえるから、注意だなー
レート落ちちゃったなー。なかなかまだまだ自分のレベルが低いんだなあ。うーん練習
Dの解法分からない…なんか問題誤読してるか？そうかもしれない

コード

共通テンプレートは略す

A
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#ifdef __GNUC__
#define aut(v, x) __typeof(x) v = (x)
#else
#define aut(v, x) auto v = (x)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
using namespace std;
typedef long long ll; typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pii> vpii;
const int INF = 0x3f3f3f3f; const ll INFL = 0x3f3f3f3f3f3f3f3fLL;

int main() {
    int n;
    scanf("%d",&n);
    printf("%d ", n);
    rer(i, 1, n-1) printf("%d ", i);
    puts("");
    return 0;
}
B
int main() {
    ll n;
    scanf("%I64d",&n);
    int a[10] = {};
    for(ll x = n; x > 0; x /= 10) a[x%10] ++;
    int r = 0;
    for(ll i = 1; i*i <= n; i ++) if(n%i==0){
        for(ll x = i; x > 0; x /= 10) if(a[x%10]) goto ok;
        continue;
ok:;
        r++;
    }
    for(ll i = 1; i*i <= n; i ++) if(n%i==0&&n/i!=i){
        for(ll x = n/i; x > 0; x /= 10) if(a[x%10]) goto ok2;
        continue;
ok2:;
        r++;
    }
    printf("%d\n",r);
    return 0;
}
C
int n;
int a[100100];
pair<int,int> c[100100];
int main() {
    scanf("%d",&n);
    rep(i,n){
        scanf("%d",&a[i]);
        a[i]--;
        c[i]=mp(a[i],i);
    }
    sort(c,c+n);
    int r = 0;
    rep(i,n) {
        if(a[i]!=c[i].first)r++;
    }
    if(r == 0 || r == 2) {
        puts("YES");
    }else {
        puts("NO");
    }
    return 0;
}