AtCoder Regular Contest 083 参加記

結果

 C問題とD問題の2完。C問題で4WA出しながら45分以上かかって無茶苦茶焦ったけれど、なんとか落ち着きを取り戻してD問題まで通せたのは良かった。

 Rating:1521→1535(+14)

f:id:tokumini:20170916235105p:plain

C問題

 最初は貪欲法とかでできるのかといろいろ考えていたけど、場合分けが難しすぎて断念。それぞれの入力値がそこまで大きくないので全探索で解けるだろうと判断したが、愚直な全探索ではまともに実行が終わらなかった。値を出力して観察すると、waterやsugarが同じものを何度も訪れているっぽいので訪問フラグを付けてみると高速になってACできた。

#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
using namespace std;

long long A, B, C, D, E, F;
long long ans_water = 0, ans_sugar = 0;

//0で初期化するとwater = 0がそのまま残り1つだけWAとなる
double max_percentage = -1;
bool visit[3001][3001];

void DFS(long long water, long long sugar) {
    //F以下でないとダメ
    if (water + sugar > F)
        return;

    //溶け残ったらダメ
    if (water / 100 * E < sugar)
        return;

    //訪問フラグを確認
    if (visit[water][sugar])
        return;

    //作った砂糖水の濃度
    if (water != 0) { //0除算を避ける
        double tmp = 100.0 * sugar / (100.0 * water + sugar);

        if (tmp > max_percentage) {
            max_percentage = tmp;
            ans_water = water;
            ans_sugar = sugar;
        }
    }
    visit[water][sugar] = true;

    //操作1
    DFS(water + 100 * A, sugar);
    //操作2
    DFS(water + 100 * B, sugar);
    //操作3
    DFS(water, sugar + C);
    //操作4
    DFS(water, sugar + D);
}

int main()
{
    cin >> A >> B >> C >> D >> E >> F;

    DFS(0, 0);

    cout << ans_water + ans_sugar << " " << ans_sugar << endl;
}

D問題

 問題の把握をしてNの大きさからいって3重ループは大丈夫だろうというところでワーシャルフロイド法が思い浮かんだ。

 まず最初に与えられた2次元配列Aの和を保持しておいて、そこから要らないものを削除していけばいいだろうと発想。

 元の2次元配列Aを3重ループで開始点、経由点、終端点と迂回する順と比較していって、より短いものがあったら最短としておかしいので-1を出力して終わり、等しかったら直接行く道は削除できるのでその分を和から引く、という方針でやったところ、半分くらいがACとなったので大まかな方針としてはあっているんじゃないかと思った。

 サンプルは全部通ってしまうので残りのWAを取るためには自分で間違っているケースを考える必要があったが、最初に正方形のように辺が張っている状態を考えて

f:id:tokumini:20170916235922p:plain

4
0 1 1 2
1 0 2 1
1 2 0 1
2 1 1 0
というのを試してみると答えが4になるべきところを0にしていて、まさにこれが残りの間違いだった。これはたとえば1から4へ行くルートは2を経由するのと3を経由するので2パターンあり、その2回の両方で直接ルート分を引いてしまっていたので答えがおかしくなっているということだった。よってあるノードからあるノードへの辺をすでに削除しているかを2次元配列で保持していくことでACとなった。

#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
using namespace std;

bool flag[301][301];

int main()
{
    int N;
    cin >> N;
    vector<vector<long long> > A(N, vector<long long>(N, 0));
    long long sum = 0;
    REP (i, N) {
        REP (j, N) {
            cin >> A[i][j];
            sum += A[i][j];
        }
    }
    //同じ辺を2回カウントしているので2で割る
    sum /= 2;

    REP (i, N) { //経由
        REP (j, N) { //開始
            for (int k = j + 1; k < N; ++k) { //終端
                if (i == j || i == k)
                    continue;
                if (A[j][i] + A[i][k] < A[j][k]) { //より短く行けたらおかしい
                    cout << -1 << endl;
                    return 0;
                }
                if (A[j][i] + A[i][k] == A[j][k]) { //同じコストでいけたら直接辺は削除できる
                    if (flag[j][k] == false) { //直接辺を削除するのは1回だけだからフラグを持つ
                        sum -= A[j][k];
                        flag[j][k] = true;
                    }
                }
            }
        }
    }
    cout << sum << endl;
}

E問題

 問題文を把握したくらいで時間切れ。700点問題とはいえちょっと解ける気はしなかった。

AtCoder Regular Contest 067 反省会

C,D問題を通しての2完で322位でした。 レートは1325から1308へ。完全に停滞している。

すっかり忘れててchokudaiさんのツイートを見てからの参加だったので11分遅れでのスタートでした。

C問題 『Factors of Factorial』

最初約数の個数を求めるのはN!じゃなくてNだと思い込んでしまったのでN \leq 1000だから素数は37まで容易すればいいかな〜と気軽に考えていたけど、サンプル合わないところでやっと気づいた。どうしようか悩んだけど、結局ググッて997までの素数をコピペしてきて凌ぐことに。その際にNが大きい素数になった時のこと考えてans \leq 1ではans = 2にするみたいな意味不明な処理を消し忘れていて1WA出してしまった。

#include <bits/stdc++.h>
using namespace std;
const int MOD = pow(10, 9) + 7;

int m[168] = {0};
int p[] = {2 ,3 ,5 ,7 ,11 ,13 ,17 ,19 ,23 ,29 ,31 ,37 ,41 ,43 ,47 ,53 ,59 ,61 ,67 ,71, 73 ,79 ,83 ,89 ,97 ,101 ,103 ,107 ,109 ,113 ,127 ,131 ,137 ,139 ,149 ,151 ,157 ,163 ,167 ,173, 179 ,181 ,191 ,193 ,197 ,199 ,211 ,223 ,227 ,229 ,233 ,239 ,241 ,251 ,257 ,263 ,269 ,271 ,277 ,281, 283 ,293 ,307 ,311 ,313 ,317 ,331 ,337 ,347 ,349 ,353 ,359 ,367 ,373 ,379 ,383 ,389 ,397 ,401 ,409, 419 ,421 ,431 ,433 ,439 ,443 ,449 ,457 ,461 ,463 ,467 ,479 ,487 ,491 ,499 ,503 ,509 ,521 ,523 ,541, 547 ,557 ,563 ,569 ,571 ,577 ,587 ,593 ,599 ,601 ,607 ,613 ,617 ,619 ,631 ,641 ,643 ,647 ,653 ,659, 661 ,673 ,677 ,683 ,691 ,701 ,709 ,719 ,727 ,733 ,739 ,743 ,751 ,757 ,761 ,769 ,773 ,787 ,797 ,809, 811 ,821 ,823 ,827 ,829 ,839 ,853 ,857 ,859 ,863 ,877 ,881 ,883 ,887 ,907 ,911 ,919 ,929 ,937 ,941, 947 ,953 ,967 ,971 ,977 ,983 ,991 ,997
};

int main()
{
    int N;
    scanf("%d", &N);
    for (int j = N; j >= 2; j--) {
        N = j;
        for (int i = 0; i < 168; i++) {
            while (N % p[i] == 0) {
                m[i]++;
                N /= p[i];
            }
        }
    }
    long long ans = 1;
    for (int i = 0; i < 168; i++) {
        ans *= m[i] + 1;
        ans %= MOD;
    }
    printf("%lld\n", ans);
}

D問題 『Walk and Teleport』

普通に貪欲やるだけでは? と思って提出したらWA。理由は10^{9}同士の掛け算によるオーバーフローなんだけど、このときには気づかず「一番大きいギャップにあたったら一度一番右までテレポートしなきゃいけないんだ」とかわけのわからない考察を始めてしまい、めちゃくちゃ時間かかってしまった&3WA。変数をとりあえずlong longで取る癖をつけておいた方が(競プロ的には)いいんだろうなぁ。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int N, A, B;
    vector<int> X;
    scanf("%d%d%d", &N, &A, &B);
    X.resize(N + 1);
    for (int i = 1; i <= N; i++) {
        scanf("%d", &X[i]);
    }
    long long ans = 0;
    for (int i = 1; i <= N - 1; i++) {
        ans += min((long long)A * (long long)(X[i + 1] - X[i]), (long long)B);
    }
    printf("%lld\n", ans);
}

E問題 『Grouping』

さっぱり方針がわからなかった。配点から見てそんなに難しくはないのかなと思ったけど、逆に典型題みたいな感じだと僕にはわからないと思ってほぼ諦めてしまった。

解説読んだら「DP[i][j] = i人以下のグループのみでj人使っている場合の数」というDPを考えるとのこと。DPで考えるなら最終的なDP[N[N]]などが答えになっているはずで、どういうものか全然思いつかなかったんだけど、なるほどこうするものか。2次元的なDPを解いた量が圧倒的に少なすぎて発想が出てこないな。Nの大きさ制限からなんとなく察し取れたりするものなんだろうか。

F問題 『Yakiniku Restaurants』

おそらく通すことはできないとわかってはいたけど、E問題よりもこっちのほうが考えてるふりができるので問題のページを開いて眺めていた。なにもわからなかった。

AtCoder Beginner Contest 038 反省会

 D問題が解けず300点の258位でした……。まだ解く速さを強く意識しようという段階でもない気はするので、点数を求めるという意味でせめてD問題の部分点は取りたかったですね。

以下各問感想

A問題『お茶』

消費時間 2分くらい  特になし

B問題『ディスプレイ』

消費時間 5分くらい+WA1回  両方のディスプレイを90度回転させたW1==W2の条件を落としていて一回WA出しました。なぜかどちらか1つだけ回すか、両方そのままかの3パターンしか考えていませんでした。残念。

C問題『単調増加』

消費時間 50分くらい+WA1回  そこから何個の単調増加数列が取れるかを後ろからメモしていけばいいんだろうなと考えました。ただちょっと問題なのは、計算量をとくに見積もったわけではなくたぶん大丈夫だろうみたいな感じで方針を立ててしまっているので、ちゃんとこれが{o(n)}になってることとか与えられる{n}の大きさがどうとか考えられるようにならなくてはいけませんね。WA出したのも、ansをlong longで宣言していなかったからで、そういった感覚の鈍さがそのまま現れています。
 解説動画だと尺取り法を使っていて、計算量の考え方がとてもわかりやすかったです。

#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
using namespace std;

int main()
{
    int n;
    long long int ans=0;
    scanf("%d",&n);
    vector<int> a(n),m(n);
    REP(i,n){
        scanf("%d",&a[i]);
        m[i]=1;
    }
    for(int i=n-1;i>=1;i--){
        if(a[i]>a[i-1]){
            m[i-1]+=m[i];
        }
        ans+=m[i];
    }
    ans+=m[0];
    printf("%lld\n",ans);
}

D問題『プレゼント』

 ある箱に何個の箱が入るかを上手くメモしていけば解けるんだろうと思いましたが、メモを更新していく順番が間違っているせいか更新の際の対象をうまく取れていないのか、部分点すら取れませんでした。サンプルは通るだけに原因がわかりにくくて直せませんでした。
 構造体のソートの仕方がちゃんとわかっておらず、まだおっかなびっくりで書いているので自在にやりたいことをコードに落とし込めません。というか整数2つの組ならpairとか使うべきなのか。慣れなきゃなぁ。

#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
using namespace std;

struct box{
    int h,w;
    bool operator<( const box& right) const {
        return h == right.h ? w < right.w : h < right.h;
    }
};

int main()
{
    int n;
    scanf("%d",&n);
    vector<box> b(n);
    vector<int> m(n);
    REP(i,n){
        int w,h;
        scanf("%d %d",&w, &h);
        b[i].w = w;
        b[i].h = h;
        m[i]=1;
    }
    sort(b.begin(),b.end());

    for(int i=n-2;i>=0;i--){
        int tmp=0;
        for(int j=0;j<n;j++){
            if(b[j].h>b[i].h && b[j].w>b[i].w){
                tmp=max(tmp,m[j]);
            }
        }
        m[i]+=tmp;
    }

    printf("%d\n",m[0]);
}

AtCoder Regular Contest 054 反省会

A,B問題を通して200点の158位でした。安定の100位台後半です。今回はC問題を通せると30位に入れるような難易度だったようで、現実的に100位以内を目指すにはA,B問題を素早く解けるかどうかという勝負になっていたようです。

以下各問振り返り

A問題『動く歩道

消費時間 9分55秒
 SからDへ時計回りで向かう時間(rightのイメージでransと置いた)と、反時計回りで向かう時間(leftからlans)の小さい方を取ればいいと考えました。SとDの大小関係で場合分けするのは綺麗な解法ではないのかもしれませんが、安全ではある気がします。
 サンプルを通してみたらYよりXが大きい場合を考えていなかったことに気づいたので、慌てて追加したせいでさらに汚い感じになっています。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int l,x,y,s,d;
    float ans,rans,lans;
    scanf("%d %d %d %d %d",&l,&x,&y,&s,&d);
    if(s<=d){
        rans=(float)(d-s)/(x+y);
        lans=(float)(l-d+s)/(y-x);
    }else{
        rans=(float)(l-s+d)/(x+y);
        lans=(float)(s-d)/(y-x);
    }
    if(y<x){
        ans=rans;
    }else{
        ans=min(rans,lans);
    }
    printf("%f\n",ans);
}

B問題『ムーアの法則

消費時間 53分40秒
 最初は紙の上で微分してしまってあっさり求めようとしましたが、指数関数の微分を思い出せず失敗。その流れで探索をしようという発想になったので、自然と微分した値(の正負だけを見た)での2分探索となりました。解説放送では元の関数での3分探索をしていたので、微分のステップで誤差が出るのが怖いことを考えるとそっちのほうが安全なのかもしれません。
 答えるべきなのはf(x)なのに最初xを求めていて「合わないな〜」とずっと悩んでしまいました。さらには最後答えは合っていたのに、悩んだ過程でprintfで確認していた部分をコメントアウトし忘れていて3回WA出してしまいました。これがなければ130位台くらいには入れていたみたいなので残念です。

#include <bits/stdc++.h>
using namespace std;

double p;

double f(double x){
    double ans = x + p/pow(2.0,x/1.5);
    //printf("f(%lf)=%lf\n",x,ans);
    return ans;
}

double d(double x){
    double h = 0.00001;
    double ans = f(x+h)-f(x);
    //printf("d(%lf)=%lf\n",x,ans);
    return ans;
}

double solve(){
    double minus = 0, plus = 99999999999, mid, di;
    for(int i=0; i<100000; i++){
        mid = (minus + plus) / 2;
        di = d(mid);
        if(di>0){
            plus = mid;
        }else if(di<0){
            minus = mid;
        }else{
            return f(mid);
        }
        //printf("i=%d,mid=%lf\n",i,mid);
    }
    return f(mid);
}


int main()
{
    scanf("%lf",&p);
    double ans = solve();
    printf("%.10lf\n",ans);
}

C問題『鯛焼き』

 さらっと見た感じ、全く解法が思い浮かばず、時間も残り20分くらいしかなかったのでD問題の部分点があればそっちを取りに行くほうがいいのではないかと考えてC問題を解ききるのは諦めました。

D問題『バブルソート

 部分点あって一瞬喜んだんですが、50点ということは簡単なやつではなさそうだということで解けないんだろうなという気はしました。そもそも圧縮した数列を戻す操作を理解するのに15分くらいかかって、そこで時間切れになりました。

AtCoder Regular Contest 053 反省会

 A問題とB問題だけ通せて200点の177位でした。今回を除いて直近2回のAtCoder主催コンテストで順位が189、158なので、まぁこれくらいの位置が今の実力なんだろうとわかってきました。まだ10回ちょっとしか参加してないし、根本的に経験が足りてないなぁと思う次第です。

以下各問振り返り

A問題『ドミノ色塗り』

消費時間 2分26秒 何故か最初にansを0で初期化し、別々に足すという無駄な工程を経ています。思考の順番がそのまま現れていますね。

#include <bits/stdc++.h>

int main()
{
    int h,w;
    scanf("%d %d",&h,&w);
    int ans=0;
    ans+=(w-1)*h;
    ans+=(h-1)*w;
    printf("%d\n",ans);
}

B問題『回文分割』

消費時間 24分33秒 回文に分けるときには中央に来る文字(center)とその両側に足していく文字(add)を分けて考えるべきだと気づくまでに結構時間がかかってしまいました。一度WA出してから修正したので、答える部分の場合分けがprintしてreturnだったりansに正答を代入だったりでぐちゃぐちゃになってしまいました。

#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
using namespace std;

int main()
{
    string s;
    cin>>s;
    int n=s.size();
    int center=0,add=0;
    int c[26]={0};
    REP(i,n){
        c[s[i]-'a']++;
    }
    REP(i,26){
        if(c[i]%2==0){
            add+=c[i]/2;
        }else{
            center++;
            c[i]--;
            add+=c[i]/2;
        }
    }


    //printf("add=%d center=%d\n",add,center);
    int ans;

    if(add==0){
        printf("1\n");
        return 0;
    }else if(center==0){
        printf("%d\n",n);
        return 0;
    }else{
        if(add/center==0) {
            ans=1;
        }else{
            ans=1+2*(add/center);
        }
    }
    printf("%d\n",ans);
}

C問題『魔法使い高橋君』

消費時間 1時間3分1秒 最初は全探索→簡略化の流れでいくのかなと思っていろいろ考えていたのですが、そもそも全探索もn!とか大変なことになるのではと気づき、二分探索でできないかなと考えました。最大気温がX℃以下であるかどうかをうまく判定できていないのでその時点でどうしようもないですね。
結局、2つの要素を持つ配列を片方の要素について技術的にソートできないのが足を引っ張っています。と、思ったのですが、上手くベクトルに入れていけば良かったのですね。

#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
using namespace std;
int n;
long long int sum=0;
long long temp=0;
vector<int> a, b, c, flag;

long long int ok=1000000000,ng=-99999999999999,mid=0;

bool isOK(int x){
    if(sum>x) return false;
    
    int rest=n;
    int frest=n;
    int div=1;
    while(div){
        REP(i,n){
            if(flag[i]==1){
                continue;
            }else{
                if(c[i]<=0 && a[i]+temp<=x){
                    temp+=c[i];
                    flag[i]=1;
                    rest--;
                }
            }
        }
        if(rest==0) return true;
        div = frest - rest;
        frest = rest;
    }
    return false;
}

long long int solve(int x){
    while(ok-ng>1){
        printf("ok=%lld ng=%lld x=%d\n",ok,ng,x);
        printf("isOK=%d\n",isOK(x));
        if(isOK(x)){
            ok=x;
            mid=(ok+ng)/2;
        }else{
            ng=x;
            mid=(ok+ng)/2;
        }
    }
    return ok;
}

int main()
{
    scanf("%d",&n);
    REP(i,n){
        int ain,bin,cin;
        scanf("%d %d",&ain, &bin);
        a.push_back(ain);
        b.push_back(bin);
        c.push_back(ain-bin);
        sum+=c[i];
        flag.push_back(0);
    }
    printf("sum=%lld\n",sum);
    int ans=solve(mid);
    printf("%d\n",ans);

}

D問題『2つの山札』

問題文すら読んでませんし解説をみる感じだとまだ全然わかりそうにないです……。

AtCoder Beginner Contest 037

 今回は少し簡単だったような気もするのですが、D問題を通せず300点で189位でした。

A問題 饅頭

消費時間 2分6秒
微妙に問題文に惑わされたり。最近はcin、coutを使わないようにしています。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int a,b,c;
    scanf("%d %d %d",&a,&b,&c);
    printf("%d\n",c/min(a,b));
}

B問題 編集

消費時間 5分45秒
愚直にやってしまう。

#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
using namespace std;

int main()
{
    int n,q;
    scanf("%d %d",&n,&q);
    vector<int> a(n);
    REP(i,n){
        a[i]=0;
    }
    REP(i,q){
        int l,r,t;
        scanf("%d %d %d",&l,&r,&t);
        for(int j=l-1;j<=r-1;j++){
            a[j]=t;
        }
    }
    REP(i,n){
        printf("%d\n",a[i]);
    }
}

C問題 総和

消費時間 7分34秒
これ絶対なんか工夫しないとダメだと思ったのにとりあえずで2重ループ書いたら通って驚きました。
解説放送見た感じだと、しゃくとり法の簡単なやつとか、うまく足される回数を考えてまとめちゃうという方法があるのですね。
一応最初の方針でダメだったら上で挙げた後者の方法でやろうと思っていましたが、うまく考えられる気はしませんでした。
累積和というのすごい発想に思えるのですが、しゃくとり法が使えそうなときは同時に頭に浮かんでいいものなんでしょうね。

#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
using namespace std;

int main()
{
    int n,k;
    scanf("%d %d",&n,&k);
    vector<int> a(n);
    REP(i,n){
        scanf("%d",&a[i]);
    }

    long long int ans=0;
    REP(i,n-k+1){
        for(int j=i;j<i+k;j++){
            ans+=a[j];
        }
    }
    printf("%lld\n",ans);
}

D問題 経路

消費時間 1時間44分35秒
たぶん答えは合っているんじゃないかと思うんですが、TLEになります。
わざわざクラス定義しているの絶対に無駄だし、各マスごとに周り4マスを見て大きかったらそれをリストに入れておくというのもどう考えても遅いんでしょうが、他になにも浮かびませんでした。 まず再帰関数をまともに書けないのが論外だし、さらには単純に一度調べたものはメモして保持しておくという自然な発想が欲しかったですね。
方向を求める配列を用意して4回ループさせるとかそういう細かいテクニックもできたらよい(けどすぐには難しいかもしれない)。

#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
using namespace std;
const int mod = 1000000000+7;
int h,w;

class p{
    public:
    int x,y;
};

int get(vector<int> a,int x,int y){
    return a[y*(w+2)+x];
}

int main()
{
    scanf("%d %d",&h,&w);
    vector<int> a((h+2)*(w+2));
    REP(i,h+2){
        if(i==0||i==h+1){
            REP(j,w+2){
                a[i*(w+2)+j]=0;
            }
        }else{
            REP(j,w+2){
                if(j==0||j==w+1){
                    a[i*(w+2)+j]=0;
                }else{
                    scanf("%d",&a[i*(w+2)+j]);
                }
            }
        }
    }

    int ans=0;
    REP(i,h){
        REP(j,w){
            ans++;
            vector<p> list;
            p now;
            now.x=j+1; now.y=i+1;
            list.push_back(now);
            while(list.size()!=0){
                int s = list.size()-1;
                int x = list[s].x, y=list[s].y;
                int no = get(a,x,y);
                list.pop_back();
                if(get(a,x-1,y)>no){
                    p to;
                    to.x=x-1; to.y=y;
                    list.push_back(to);
                    ans++;
                }
                if(get(a,x+1,y)>no){
                    p to;
                    to.x=x+1; to.y=y;
                    list.push_back(to);
                    ans++;
                }
                if(get(a,x,y-1)>no){
                    p to;
                    to.x=x; to.y=y-1;
                    list.push_back(to);
                    ans++;
                }
                if(get(a,x,y+1)>no){
                    p to;
                    to.x=x; to.y=y+1;
                    list.push_back(to);
                    ans++;
                }
            }
        }
    }
    printf("%d\n",ans%mod);
}

第26回世界コンピュータ将棋選手権 雑感

今日はほぼ一日中えびふらいさんの放送を見ていました。

  • えびふらいさんのエンタメ化して人集めて計算代行してもらうってすごく面白い手法だしもっと打算的にやっていく人がいてもよさそう(でも狙われると逆に冷めるみたいな要素もあるんでしょうね) 善意で応援してる、協力してる感を演出するとは)
  • Aperyみたいな強力なライブラリが使えるの本当にすごいことだし強さの平均がめちゃ上がる。一方、ライブラリとして使うのと参考にして自分で書くの、開発者の心境としてどこに境目があるのだろうみたいなのが気になった。そういう意味ではQhapaqの澤井さん(澤田さんでしたっけ……?)がやってることが主流になったりならなかったりなのかもしれないなみたいな。
  • 1年あると環境激変するし、シードを多くすると結構力関係ひっくり返ってるとかありそう。でも多くの人に3日戦いぬけというのも厳しい話なのでしょうか(2次からの人も結局会場来てる人が多いみたいだけど)
  • というかやっぱり実力的にはもっと数多く戦わないと意味なさそうだしやはり交流会という感じ強い
  • 技術お披露目会でもあるらしいですね
  • 当たり前の話だけど開発者の皆さんとても優秀ですね。将棋ソフト作ってみたい気持ちもあるけどaperyとかやねうら王miniとかのソースコードをどういうところからなにをとっかかりに読んでいけばいいのかさっぱりわからず
  • そういう意味ではうさぴょんさんのページが一番素人の素人向けに書かれている感あるし、うさぴょんさん自信が2次予選に進めててすごいし、頑張って欲しい(そしてできれば超初心者向けに本を書いてほしい……っていうのは言いすぎですかね)
  • 大合神クジラちゃんのパワーで殴る感じ最高だったし、それを華麗に打ち破った技巧もすごく良い。
  • 僕も技術力ほしいしそれでいろいろ面白いことをしたいなという気持ちが更に強まりました

AtCoder Regular Contest 052

4月30日に行われたARC052に参加しました。
結果はA,B問題を通しての200点で順位は158位でした。D問題で10点部分点を取れれば100位以内に入れたのでなんとかしたかったですね。やはりコード書くのが遅すぎるのが問題だと感じます。
以下各問振り返り
(今回解説放送をほとんど真面目に聞いていなかったのであまりちゃんとした反省になっていません……)

A問題『何期生?』

受け取った文字列を頭から見ていって数字があったらひとつ次まで調べればいいのだろうと考えました。この程度のプログラムにも16分かかるのが今の実力という感じです。

int main(){
    string s;
    int ans=0;
    cin>>s;
    REP(i,s.size()){
        if('1'<=s[i]&&s[i]<='9'){
            if('0'<=s[i+1]&&s[i+1]<='9'){
                ans = (s[i] - '0')*10 + s[i+1] - '0';
                break;
            }else{
                ans = s[i] - '0';
                break;
            }
        }
    }
    cout<<ans<<endl;
}

B問題『円錐』

各円錐について、{a\leq x\leq b}の領域に一部分でもあるかを判定して、あったら計算すればいいのだろうと。nが小さいからたぶんこういう愚直なやりかたでいけるんだろうなぁと思いました。
piを整数で宣言してしまったり、返り値で整数を宣言していたりで計算が合わず四苦八苦してしまいました。なにも考えずint書くのほんとダメ。ここの実装でものすごく時間使ってしまったのが反省点です(今提出時刻確認したら1時間以上も使ってしまったいた……)。
でも近くの順位の人を見るとだいたいそんな感じなのでこれはそういう問題なのでしょうね。 [a,b]内にある部分の体積計算は同じようなコード書きまくってるし、もっとうまくやれそうな気もしますが、具体的にどうというのは思い浮かびませんね。

const double pi = 3.1415926535;

class cone{
    public:
        double x,r,h;
        bool isIn(double a,double b){
            if(x<=a&&a<=x+h||a<=x&&x<=b){
                return true;
            }else{
                return false;
            }
        }
        double V(){
            return pi*r*r*h/3.0;
        }
        double Vab(double a,double b){
            if(x<=a&&x+h<=b){
                cone small;
                small.h=x+h-a;
                small.r=r*small.h/h;
                return small.V();
            }else if(x<=a&&b<x+h){
                cone small,large;
                small.h=x+h-b;
                small.r=r*small.h/h;
                large.h=x+h-a;
                large.r=r*large.h/h;
                return large.V()-small.V();
            }else if(a<=x&&b<x+h){
                cone small;
                small.h=x+h-b;
                small.r=r*small.h/h;
                return V()-small.V();
            }else{
                return V();
            }
        }
};

int main()
{
    int n,q;
    cin>>n>>q;
    vector<cone> c(n);
    double a,b;
    REP(i,n){
        cin >> c[i].x >> c[i].r >> c[i].h;
    }
    REP(i,q){
        cin>>a>>b;
        double sum=0;
        REP(j,n){
            if(c[j].isIn(a,b)){
                sum+=c[j].Vab(a,b);
            }
        }
        printf("%4f\n",sum);
    }
}

C問題『高橋くんと不思議な道』

問題文を見た瞬間、これはできないやつだと悟りました(時間も少なかったし)。ノードとエッジが出てくる経路系の問題に慣れていなさすぎてちょっと苦手意識を持っているのはよくないですね。DPも含めて意識的に訓練しないとできるようにならなさそうな分野だと思っています。

D問題『9』

問題文開いた時点で残り10分くらいしか時間がなく、部分点だけを狙いにいきましたが失敗。 以下がその時書いたコード

#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
using namespace std;
int main()
{
    long long int k,m;
    cin>>k>>m;
    int c=0;
    REP(i,m){
        int isum=0;
        int j=i;
        while(1){
            isum+=j%10;
            j/=10;
            if(j==0)break;
        }
        if(i%k==isum%k)c++;
    }
    printf("%d\n",c);
}

これREPで書いてしまっているので0スタートになってて間違いだったようです。(forで書いたら10点分は取れました)
マクロ使うのが悪いわけではないと思うのですが、こういうミスをしてしまうとちょっと考えてしまいますね。

ニコニコ超会議の将棋企画

 今日はニコニコ超会議なるものの将棋放送を観ました。斎藤慎太郎六段とAperyがタッグを組んでponanza、nozomi、大樹の枝連合軍と指すという企画から見始めましたが、多数決による合議制がponanza単体よりも強いのかというのは微妙な感じでしたね。興行としては強そうに見せながらほどほどの強さに抑えることができるのでうまい手法なんだろうなと思いました。そうは言っても尋常じゃない強さであろう将棋ソフト連合軍を打ち負かした斎藤六段はやはりプロ棋士、異次元の強さを誇るのだということを改めて感じました。僕自身の棋力は将棋ウォーズでも初段になれないくらいのものなのですが、将棋ソフトが好きなせいでどうしてもプロ棋士の強さを過小評価してしまいがちであるようです。プロ棋士の方々というのは将棋が強いという一点で飯を食っていける恐ろしい人たちなわけで、わざわざ「プロ棋士へのリスペクトを忘れてはならない」と戒めるまでもなく本来ならばその強さを見ただけで自然と尊敬してしまうべきなのでしょう。僕がそうならないのは棋力が低すぎてプロ棋士たちの力を適切に理解できていないからなのだろうなと思います。勝負事が嫌いなので対人戦はあまりしないのですが、プロの凄さをより理解できるようになるという意味で棋力を高めたいですね。

 午前中には飛車と角はどちらが強いのかという企画を行っていたと後になってから知り、悔しさを感じながら番組のページを開いてみたら一般会員で予約してなくてもタイムシフトが見れるらしく、夜も遅くなってから見始めました。もともとはプロパンゴリラさんという人がニコニコ動画に投稿した動画がきっかけとなっていて、僕も氏の動画はほとんどすべて見たことがあるものですから、とうとう竜王と共演するまでになったかと驚きました。(芸のある)一般人が有名な人と同じステージに立てるというのは何かしら素敵なことであるように思います。夢がある時代だと思いますし、それをうまく活かせていない自分がちょっと嫌になったりします。ニコニコ及びニコニコ超会議が良いことばかりとは思いませんが、利用できるものは利用するのが正しいあり方なんでしょうね。企画内容そのものはやはり飛車が自由に動けるのが大きくて、駒組が制限されてしまう角側に対して縦歩取りを見せる急戦、堅く囲える持久戦のどちらでも飛車側が有利なのでしょう。竜王の切れ味鋭い発言が効いていて良い番組でした。

AtCoder Regular Contest 050に参加しました

昨日行われたAtCoder Regular Contest 050に参加しました。
結果はA問題しか解けず、100点の259位でした。200点取れると順位がふた桁以内になるようなので頑張りたいところですね。
以下各問感想

A問題 大文字と小文字

最初A-Zとa-zは数字が続いているものと思っていたので入力をAとaで受け取ったとすると A - a == 26 とすれば判定できるのではないかとか考えていました。やってみると全然違う数字が出てきてしまったので、しばらく悩んだあと諦めて小文字の方にtoupper()を適用して比較しました。解説放送であったとおり A - 'A' == a - 'a' と比較すればスマートにやれたのですね。解説放送のコメントでXORを使うとかもありましたが、よくわからないですしまだそんなことを気にするレベルではないかなという感じもします。

B問題 花束

入力が{R,B,x,y}とあって、{(x,1)}の束をa個、(1,y)の束をb個作るとすると、できる花束の総数M M = a + b 個となるのでこのMを最大化すれば解けるのではないかと考えました。このとき、赤い花による条件は ax+b \leq R , 青い花による条件は a + by \leq B となり、b = M - a からbを消去すれば
{\displaystyle
M \leq R - a (x-1)
}
{\displaystyle
M \leq \frac{B - a}{y} + a
}
という不等式を両方満たせば良いことになるので、つまりaが定まったとき {\displaystyle
M = \min(R - a (x-1),\frac{B - a}{y} + a )
}
ということになります。  a = 0 から  a = \frac{R}{x} まで変化させたときの M の最大値を返せばいいのではないかと考えましたが、最大とする a を三分探索で求めようと実装していたところで時間が尽きました。この方針でいけるのかわかりませんが実装を速くしないと試せるアイデアが少なくてもどかしいですね。 解説では花束の数を与えれば二分探索で解けるとのこと。二分探索は数式に使える条件が増やせるし関数の返り値はbool型で良いしで、ぜひとも適用できるかどうかを見極める力を身につけたいテクニックですね。

C問題 LCM 111

愚直に処理をプログラム化しただけでは絶対通らないんだろうと思いつつも、ユークリッドの互除法の実装をしたことがなかったのでその練習も兼ねてということで小さいサンプルだけ通るようなものを書いて提出もせずに終了。ユークリッドの互除法は引数の2整数の大小関係を気にしない書き方ができるらしいのですが、いちいち大小関係見てスワップさせながらみたいな実装をしました。こういうところもなんとかしたいですね。書いたコードを他のコンテストで再利用するってどういう方法が最適なのかわからず、とりあえず今は手を動かすことを再優先にやっています。 解説を聞いたあとでも、多分うまく大きい数を関数でバラしていくあたりが実装できないんだろうなと思いました。まぁ慣れればなんとかできるんじゃないかと思いますが。

D問題 Suffix Concat

コンテスト中は問題文を読みすらしてなかったのですが、解説を聞く限りとても難しそうでまだ手の届くものではなさそうだなという感じです。

A問題のタイムアタックみたいな状況からは一歩抜け出したいですね。