読者です 読者をやめる 読者になる 読者になる

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);
}