CODE FESTIVAL 2017 予選B 参加ログ

結果

 A,B問題2完の741位。うーむC問題が解けないのはちょっと苦しいところか。精進が足りない。レート1535→1516(-19)

A問題

 後ろから8文字を削除するだけ。

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    string S;
    cin >> S;
    cout << S.substr(0, S.size() - 8) << endl;
}

B問題

 mapで各難易度について必要数と作成済数を記録していけば解けると思ったんだけど、先に必要な数を引いていくとREが出てしまった。mapだからデフォルトは0で、引いたらなにかおかしいことがあるのかな? ちょっとよくわからなかったけど先に足すようにすれば通った。

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    int N;
    cin >> N;
    vector<int> D(N);
    map<int, int> mp;
    for (int i = 0; i < N; ++i) {
        cin >> D[i];
        mp[D[i]]++;
    }
    int M;
    cin >> M;
    vector<int> T(N);
    for (int i = 0; i < M; ++i) {
        cin >> T[i];
        if (mp[T[i]] == 0) {
            cout << "NO" << endl;
            return 0;
        }
        mp[T[i]]--;
    }
 
    cout << "YES" << endl;
}

C問題

 これが全然わからなかった。考察のとっかかりすらうまくつかめなくて、座っているだけの時間が多くなってしまった。明らかにN, Mが大きいので、まともな最短経路を求めてなんとかしていくわけではないだろうとは思った。そして、頂点の偶奇がちょっと怪しいかと思ってコードを投げてみたりもしたんだけど、片方だけ通すことすらできなかった。

 解説を読んだけど、まず2部グラフという用語の定義すらちゃんとわかってなかった。知識が圧倒的に足りない。

CODE FESTIVAL 2017 予選A 参加記

結果

A,B,C問題を解いて3完。C問題でかなり手間取ってしまったのが痛かった。時間があってもD問題を解けたがどうかはわからないが、しっかり考えてみたかった。

 一応CODE FESTIVALの方にエントリーはしてみているけど、まぁ無理だわな。

A問題

 substrで先頭4文字だけ取ってきて比較するだけ。今考えると4文字未満のときを考慮してなかったのでC++の仕様に救われたか。まぁ親切にも入力例3で3文字のケースがあるので、問題があってもWA出す前に気づけてはいたと思うけど。

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

int main()
{
    string S;
    cin >> S;
    if (S.substr(0, 4) == "YAKI")
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

B問題

 2回押すと元に戻るだけだから各ボタンについて押すか押さないかだけが重要。

 行ボタンのうちi個、列ボタンのうちj個を選ぶと  i \times M + (N - i) \times j - i \times j 個が黒くなるはずで、それで解ける。

 コードだと頭が悪くて列を先に押すのと行を先に押すので結果が変わると勘違いしている。何をやっているんだ。普通に二つとも同じ式じゃないか……。というか順番によって結果が変わると思ってしまうのがかなりセンス悪い気がする。頑張ろうな。

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

int main()
{
    int N, M, K;
    cin >> N >> M >> K;

    for (int i = 0; i <= N; ++i) {
        for (int j = 0; j <= M; ++j) {
            if (i * M + (N - i) * j  - i * j== K
                    || j * N + (M - j) * i - i * j== K) {
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
}

C問題

 最初は

  • HとWが両方奇数のとき、奇数個の文字が1個、それ以外の文字は偶数個
  • そうでないとき全部の文字が偶数個

で解けると勘違いしてコードを書き始めてしまったんだけど、入力例2で失敗してちょっと困る。ここで小手先の回避方法として

  • HとWが両方2以上の時は4回以上表れている文字が最低1個は必要

という条件を付け足して、とりあえずサンプルだけ通るようにして提出してしまい、当然WA。

 しばらく考えてから、4個必要になる領域は角だけじゃないことに気づいて、HとWの偶奇によって偶偶 or 奇奇 or 偶奇(奇偶)で場合分けして書き直したが、まだ1個だけWAが出るようになった。

 どうしてもわからなかったのでそれぞれの場合分けに一個ずつassert(false)を仕込んでみたところ、奇奇のところでWAがREになったので、ここで変なことが起きていると判断した。今回はペナルティがなしということだってのでこういう邪悪なハックをやることに対する抵抗がちょっと小さかった。

 で、何が間違っていたかというと、4個以上出てくる文字が奇数になっている場合というのを考慮していなかった。たとえばaが5個出てきて、1個を中央に使って4個を対象的に使うとか、そういうことがありえるんだ。気づいたらすぐ直せてAC。結構大変だった。

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

int main()
{
    int H, W;
    cin >> H >> W;
    vector<string> a(H);
    vector<int> num(26, 0);
    for (int i = 0; i < H; ++i) {
        cin >> a[i];
        for (char c : a[i]) {
            num[c - 'a']++;
        }
    }
    int odd_num = 0;
    int num4 = 0;
    for (int i = 0; i < 26; ++i) {
        num4 += num[i] / 4;
        if (num[i] % 2 == 1) {
            odd_num++;
        }
    }

    if (H % 2 == 0 && W % 2 == 0) {
        if (odd_num == 0 && H * W / 4 <= num4)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    } else if (H % 2 == 1 && W % 2 == 1) {
        if (odd_num == 1 && (H - 1) * (W - 1) <= num4 * 4)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    } else {
        //必ずHが奇数ということにする
        if (H % 2 == 0)
            swap(H, W);

        if (odd_num == 0 && (H - 1) * W / 4 <= num4)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
}

 場合分けが美しくないと思ったのでちょっと書き直してみた。まぁ本番でこれを書きにいくことはしないかなぁ。でもこれの方が解法をちゃんと理解した上でのコードっぽい気はする。

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

int main()
{
    int H, W;
    cin >> H >> W;
    vector<string> a(H);
    vector<int> num(26, 0);
    for (int i = 0; i < H; ++i) {
        cin >> a[i];
        for (char c : a[i]) {
            num[c - 'a']++;
        }
    }
    int odd_num = 0, num4 = 0;
    for (int i = 0; i < 26; ++i) {
        num4 += num[i] / 4;
        if (num[i] % 2 == 1) {
            odd_num++;
        }
    }

    //4個使う領域(たとえば右上)を求めるときの長さ
    int h = (H % 2 == 0 ? H / 2 : (H - 1) / 2);
    int w = (W % 2 == 0 ? W / 2 : (W - 1) / 2);

    if (odd_num == (H % 2 == 1 && W % 2 == 1)
            && h * w <= num4)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}

D問題

 時間もなかったので、単純にRYGBの順で塗れるだけ塗ってみるとか、できるだけバランスよく塗ってみるとか、簡単な方法で貪欲にやっていくのを試してみたけどWA。間違ってるパターンをいろいろ出してみて眺めているうちに時間切れ。

 ある場所に対して同じ色を塗れない位置が角の利きに似ているので一瞬Rotated Bitboardみたいな考え方が頭をよぎったんだど、それを推し進めることができなかった。マンハッタン距離は45度回転させてみるというの、ちょっと気に留めておいていいパターンだと思う。

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点分は取れました)
マクロ使うのが悪いわけではないと思うのですが、こういうミスをしてしまうとちょっと考えてしまいますね。