夢追い人

"It takes a dreamer to make a dream come true."―Vincent Willem van Gogh

PCKもうひとつの本選4位www

プログラミング

若干予想してましたがまさか本当にこうなってしまうとは…

まぁというわけでTwitterで予告した通りの今回の敗因分析＆今回の問題についての解説的なにか、とかやっていこうと思います。

敗因

まず敗因ですね。今回自己分析した結果、自分にあるクセが存在すること、それが１つの原因となってしまっていることが判明しました。とりあえず列挙（といってもそんなにないけど…）

  • 競技中に順位表を見過ぎ
  • modだとlongじゃなくてintで充分という謎の論理を展開してしまう
  • 幾何はベクトルゲーだと何回も見ているのに必ず初等幾何で挑もうとしてしまう

この三点ですね。
まず最初のは、あとどれだけとけばと計算してしまう上集中力が切れているので本当に良くないですね。正直これが一番の敗因じゃないかなとか思ってます。特に今回。
次のは本当に悪い癖ですよね。もれるかわからなくても転ばぬ先の杖ってやつでlong long使えばいいのに…って今となっては思います。
そして最後は…まぁめんどくさがりなところから来てるのかな？とりあえず現実でもベクトルの勉強頑張らなきゃですね。


といった感じです。ではそれぞれの問題を見て行きましょう。

1

本物のやるだけです。たしかもうひとつの本選最速

#include <cstdio>
#include <iostream>
using namespace std;
/*
 * a 0
 * b 1
 * x 2
 * y 3
 * z 4
 * w 5
 * */
int mp[6][2] = {{2,3},{3,2},{-1,4},{2,-1},{5,1},{1,3}};
string str;
int main() {
    while (cin>>str) {
        if (str=="#") break;
        int np = 0;
        for (int i=0; i<str.length(); i++) {
            if (str[i]=='0') np = mp[np][0];
            else if (str[i]=='1') np = mp[np][1];
            if (np==-1) break;
        }
        if (np==1) puts("Yes");
        else puts("No");
    }
}

2

シュミレーションですね

#include <cstdio>
#include <cstring>
#define LIM 10000
int n, res, b[1000000], nb[1000000];
int main() {
    while (scanf("%d",&n)) {
        if (!n) break;
        for (int i=0; i<n; i++) scanf("%d",&b[i]);
        for (res=0; res<=LIM+1; res++) {
            bool flag=true;
            if (b[0]==1) {
                for (int i=1; i<n; i++) {
                    if (b[i]-b[i-1]!=1) {
                        flag=false;
                        break;
                    }
                }
            } else {
                flag=false;
            }
            if (flag) break;
            for (int i=0; i<n; i++) b[i]--;
            int x=0;
            for (int i=0; i<n; i++) {
                if (!b[i]) continue;
                nb[x++] = b[i];
            }
            nb[x++] = n;
            n = x;
            for (int i=0; i<n; i++) {
                b[i] = nb[i];
            }
        }
        if (res>LIM) puts("-1");
        else printf("%d\n",res);
    }
}

3

打ち込み＆出力ゲーです。
結局うまい出力みつからなくて全部場合わけしました。というかこれしか方法ないんでは？

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int q;
string str;
string b[16]={"0000","0001","0010","0011","0100","0101","0110","0111",
    "1000","1001","1010","1011","1100","1101","1110","1111"};
double inte[24];
double syo[7];
int main() {
    inte[0]=1; syo[0]=0.5;
    for (int i=1; i<24; i++) inte[i]=inte[i-1]*2;
    for (int i=1; i<7; i++) syo[i]=syo[i-1]*0.5;
    scanf("%d",&q);
    for (int x=0; x<q; x++) {
        cin>>str;
        string bit="";
        for (int i=0; i<str.length(); i++) {
            if ('0'<=str[i]&&str[i]<='9') {
                bit+=b[str[i]-'0'];
            } else if ('a'<=str[i]&&str[i]<='f') {
                bit+=b[str[i]-'a'+10];
            }
        }
        // cout<<bit<<endl;
        double res = 0.0;
        for (int i=1; i<25; i++) {
            if (bit[i]=='1') {
                res += inte[24-i];
            }
        }
        int kiri=0;
        for (int i=25; i<32; i++) {
            if (bit[i]=='1') {
                kiri=i-24;
                res += syo[i-25];
            }
        }
        if (bit[0]=='1') res *= (-1.0);
        if (kiri<2) printf("%.1f\n",res);
        else if (kiri==2) printf("%.2f\n",res);
        else if (kiri==3) printf("%.3f\n",res);
        else if (kiri==4) printf("%.4f\n",res);
        else if (kiri==5) printf("%.5f\n",res);
        else if (kiri==6) printf("%.6f\n",res);
        else if (kiri==7) printf("%.7f\n",res);
    }
}

6

とりあえず4もやりますが修正がめんどくさいので先にこちらをやらせてください。
これはまずシュミレーションで問題となる文字列を抽出したのち、手でやるときはある程度書き出しながらやるような組み合わせの数を求める問題でした。
これで一番のポイントとなるのは、それまでにそこの文字よりも辞書順で前になる文字を何回使ったかを調べる方法です。
まぁ大体これに気づいただけですぐわかると思いますがBITを使います。
そしてBIT使うためにも文字は数字で管理しておいたほうがいいですね。というわけで以下が正解コードです。

本番のときのコードをlong longにしただけですが解き方はあってるので多分これでACすると思います。まだ確かめようがないので断言はできませんが・・・

#include <cstdio>
#include <cstring>
#include <algorithm>
#define mod 1000000007
using namespace std;
typedef long long ll;
int n,r;
int moji[100000];
ll kai[100001];
int bit[100001];
int sum(int i) {
    int s = 0;
    while (i>0) {
        s+=bit[i];
        i -= i & -i;
    }
    return s;
}
void add(int i, int x) {
    while (i<=n) {
        bit[i]+=x;
        i += i & -i;
    }
}
int main() {
    kai[0]=1;
    for (int i=1; i<=100000; i++) {
        kai[i]=(kai[i-1]*i)%mod;
    }
    while (scanf("%d",&n)) {
        if (!n) break;
        memset(bit, 0, sizeof(bit));
        scanf("%d",&r);
        for (int i=0; i<n; i++) moji[i]=i;
        for (int i=0; i<r; i++) {
            int s,t; scanf("%d%d",&s,&t);
            swap(moji[s-1],moji[t-1]);
        }
        ll res=0;
        for (int i=0; i<n; i++) {
            int x=kai[n-i-1];
            int bef=moji[i]-sum(moji[i]);
            if (bef<0) bef=0;
            add(moji[i]+1,1);
            res=(res+(bef*x)%mod)%mod;
        }
        printf("%d\n",res);
    }
}

4

さてこれは気づけば簡単な幾何問。
ポイントとなるのは扇形にその点が含まれるかの判定です。

終了まぎわに思いついて正解っぽい判定方法を紹介してそれにもとづいた正解（だと思われる）コードを載せることにしましょう。

  • まず扇形の半径以上中心から離れていればそれは確実に入っていない。
  • 原点からその点へのベクトルを考えた時これが扇形の一つの辺のみと交わっていれば中に、二つの辺と交わっていれば外にある。
  • ただし扇形の直線上のものは範囲なので例外としてのぞく

直線の交差判定などは蟻本にまんまの問題が載っているので蟻本さえ持っていれば実装は楽です。

それでは正解と思われるコード

#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#define pi 3.1415926535
#define eps 1e-9
using namespace std;
int h,r,hx[100],hy[100],w,a;
int u,m,s,du,dm,ds;
int ux[10],uy[10],mx[10],my[10],sx[10],sy[10];
int ch[100];
double add(double a, double b) {
    if (abs(a+b)<eps*(abs(a)+abs(b))) return 0;
    return a+b;
}
struct P {
    double x,y;
    P(){}
    P(double x, double y) : x(x),y(y) {}
    P operator + (P p) {
        return P(add(x,p.x),add(y,p.y));
    }
    P operator - (P p) {
        return P(add(x,-p.x), add(y, p.y));
    }
    P operator * (double d) {
        return P(x*d,y*d);
    }
    double dot(P p) {
        return add(x*p.x,y*p.y);
    }
    double det(P p) {
        return add(x*p.y,-y*p.x);
    }
};
bool on_seg(P p1, P p2, P q) {
    return (p1-q).det(p2-q)==0&&(p1-q).dot(p2-q)<=0;
}
P intersection(P p1, P p2, P q1, P q2) {
    return p1+(p2-p1)*((q2-q1).det(q1-p1)/(q2-q1).det(p2-p1));
}
bool isin(int x1, int y1, int x2, int y2, int d, int win, int ac) {
    double dist=sqrt((double)(x1-x2)*(x1-x2)+(double)(y1-y2)*(y1-y2));
    if (dist>(double)ac+eps) return false;
    double rad1=(win-(double)d/2)/360.0*pi, rad2=(win+(double)d/2)/360.0*pi;
    P p0 = P(0.0,0.0);
    P p1 = P((double)x1,(double)y1);  // house
    P p2 = P((double)x2,(double)y2);  // flower
    P p3 = P(x2+ac*cos(rad1), y2+ac*sin(rad1));
    P p4 = P(x4=x2+ac*cos(rad2), y2+ac*sin(rad2));
    if (on_seg(p2,p3,p1)||on_seg(p2,p4,p1)) return true;
    P r1 = intersection(p2,p3,p0,p1), r2 = intersection(p2, p4, p0, p1);
    if ((on_seg(p2,p3,r1)&&on_seg(p0,p1,r1))&&(on_seg(p2,p4,r2)&&on_seg(p0,p1,r2))) return false;
    if ((on_seg(p2,p3,r1)&&on_seg(p0,p1,r1))||(on_seg(p2,p4,r2)&&on_seg(p0,p1,r2))) return true;
    return false;
}
int main() {
    while (scanf("%d%d",&h,&r)) {
        if (!h&&!r) break;
        vector<int> res;
        memset(ch, 0, sizeof(ch));

        for (int i=0; i<h; i++) scanf("%d%d",&hx[i],&hy[i]);
        scanf("%d%d%d%d%d%d",&u,&m,&s,&du,&dm,&ds);
        for (int i=0; i<u; i++) scanf("%d%d",&ux[i],&uy[i]);
        for (int i=0; i<m; i++) scanf("%d%d",&mx[i],&my[i]);
        for (int i=0; i<s; i++) scanf("%d%d",&sx[i],&sy[i]);
        for (int ix=0; ix<r; ix++) {
            scanf("%d%d",&w,&a);
            for (int i=0; i<h; i++) {
                bool flag=false;
                for (int j=0; j<u; j++) {
                    if (isin(hx[i],hy[i],ux[j],uy[j],du,w,a)) {
                        flag=true;
                    }
                }
                for (int j=0; j<m; j++) {
                    if (isin(hx[i],hy[i],mx[j],my[j],dm,w,a)) {
                        flag=true;
                    }
                }
                for (int j=0; j<s; j++) {
                    if (isin(hx[i],hy[i],sx[j],sy[j],ds,w,a)) {
                        flag=true;
                    }
                }
                if (flag) ch[i]++;
            }
        }
        int minr=1000;
        for (int i=0; i<h; i++) minr=min(minr,ch[i]);
        if (minr==r) puts("NA");
        else {
            bool first=false;
            for (int i=0; i<h; i++) {
                if (ch[i]==minr) {
                    if (first) {
                        printf(" ");
                    }
                    printf("%d",i+1);
                    first=true;
                }
            }
            puts("");
        }
    }
}

実装重すぎｗｗあってると思うんだけどなーこれで
まぁそれは同時に５完できたんだよなー
ってことなんですけどね(；・∀・)

5とか7とか

これはまだ良くわかってないけどまぁってやつ
5番はどうやら余りで数列を分割するとオーダー間に合うらしいですね。クエリをうまくすると…みたいに考えてどつぼにはまってました。
7番はよくわからない。貪欲にしか見えないんだけどWAして…DPなのかな？

まとめ

まぁ解けたという意味では（コンテストは４位だったけど）相方がいないわりに頑張ったんじゃないかなとおもいます。
来年は高校生最強の先輩たちがいなくなり、ようやく会津大学に行けるチャンスが生まれるので本選でできるだけ先輩たちの後を継げるようにがんばりたいですね。

とりあえず図書券4000円は一人でいただきます。