17日目 Beginner 34

17日目(2019/9/2)

AtCoder Beginner Contest 034

AとBがすごく簡単で、Cで突然難しくなる感じでした。
アルゴリズム思いつかなくてCは部分点狙いに行く作戦になりました。

解けた問題

A:テスト

if文で分岐しただけ！

B:ペア

if文で分岐しただけ！（2の剰余で分岐するだけ）

解けなかった問題

C:経路

アルゴリズムが思いつかなかったのでDFSで部分点を狙いに行くことにしました。 上下左右じゃなくて右か下にしか行かないので迷路を解くアルゴリズムよりはシンプルな実装になりました。 盤の外、もしくは目的地より外側にいるならたどり着けないのでreturn
50点分の得点はこれでもらえました。どうやって実装すればよかったんだろう…

int c;

using namespace std;

void DFS(int dist_x,int dist_y,int x,int y,bool board){
    //盤の外ならreturn
    if(x<0||x>dist_x||y<0||y>dist_y)
        return;
    if(x==dist_x && y==dist_y){
        c++;
        return;
    }
    DFS(dist_x,dist_y,x,y+1,board);
    DFS(dist_x,dist_y,x+1,y,board);
}

int main(void){
    int dist_x,dist_y;
    cin >> dist_x >> dist_y;
    bool** board = new bool*[dist_y];
    for(int i=0;i<dist_x;i++){
        board[i] = new bool[dist_x];
    }
    DFS(dist_x-1,dist_y-1,0,0,board);
    cout << c%1000000007 << endl;
}

解説を見てみる

C

追記： 動的計画法で実装してみた。これで100/101点でした。
__int64_t型の存在と初めてのvector2次元配列を知る。

vector<vector<T>> v_name(高さ、vector<T>(幅));

__int64_t型は組み込みの方で、環境によらず64bitの整数型を表すみたい。

// C++のテンプレート
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int main(void){
    __int64_t W,H;
    cin >> W >> H;
    vector<vector<__int64_t>> board(H,vector<__int64_t>(W));
    for(int i=0;i<W;i++){
        board[0][i] = 1;
    }
    for(int i=0;i<H;i++){
        board[i][0] = 1;
    }
    for(int i=1;i<H;i++){
        for(int j=1;j<W;j++){
            board[i][j] = board[i-1][j] + board[i][j-1];
            board[i][j] %= 1000000007;
        }
    }
    cout << board[H-1][W-1] << endl;
}

満点をとるためには数学的に計算する必要がある。 (H+W-2)回移動するからH-1回移動する方法を求めればいい。
ってことは で求まる。あれー考えたんだけどなぁ…（多分どこかで間違ってたのかな
(H+W-2)!/(H-1)!(W-1)!