トップ > AtCoder > AtCoder ABC196

AtCoder ABC196

AtCoder

ABC196参加しました。

atcoder.jp

 

A - Difference Max

区間[A,B]の中の値x, 区間[C,D]の中の値yで$x-y$の最大値を出す問題。 各区間の端っこ同士の値を使う。 途中で考えるのが面倒になって、結局

int ans = Max(ans, C-B);
ans = Max(ans, ...);
...

みたいに全探索してやった。 解説 - AtCoder Beginner Contest 196

B - Round Down

与えられた長～い数値は文字列として受け取り、小数点の位置を検索。 小数点位置があれば、文字列の頭からその位置までを切り取って出力します。 見つからないなら、そのまま出力します。

解説 - AtCoder Beginner Contest 194

C - Doubled

コツは、「後半の数字だけを決めて、前半にコピーする」ことで、これで必ず前半後半の桁が一致して、全体が偶数桁になります。 これだと後半の桁は最大でも 106 なので、十分全探索で間に合います。 以下のような感じ。

i = 1;//後半の数
while (i <= n)
{
    s = i.ToString() + i.ToString();//後半の数値を前半にコピーして、
    check = long.Parse(s);//チェックする数を決める
    if(check > n) { break; }//チェックする数がnより大きかったら、もう見ても意味がない
    ans++;//答えが一つ決まった
    ++i;//後半の数を一つ増加
}

解説 - AtCoder Beginner Contest 194

D - Hanjo

DFS問題だということに気がつけなかった。修行が足りない... 公式の動画解説がとてもわかりやすいです。

左上のマスから開始して、そのマスに対して、

  1. 半畳を置いたと仮定する
  2. 1畳横置きしたと仮定する
  3. 1畳縦置きしたと仮定する

として、次のマスを見ていきます。 全マスを見たら、畳の敷き詰めパターンが一つ確定します。 途中で残りの畳がなくなったら、そのパターンの敷き詰めはできません。 公式動画のコードをコメント付きで実装してみたら以下の様になりました。

//見たいマス(h,w), 残りの畳枚数(a,b)
public int dfs(int h, int w, int a, int b)
{
    int res = 0;//敷き詰めパターン数
    if(a < 0 || b < 0) { return 0; }//畳がない。。。このパターンの敷き詰め失敗
    if(w == W){//右端まで見たら、次の段に
        w = 0;  h = h + 1;
    }
    if(h == H) {//全マス見た
        return 1;//全マス埋める置き方が1パターン確定した
　 }
    if(Masu[h,w] == true){//もう置いてある
        //次のマスにいく
        return dfs(h, w + 1, a, b);
    }

    //とりあえず今見ているマスは畳をおく
    Masu[h, w] = true;
    //半畳
    res += dfs(h, w + 1, a, b - 1);//右隣の畳を探索していく
    //1畳を横に置く場合
    if(w + 1 < W && Masu[h,w+1] == false){
        Masu[h, w + 1] = true;//とりあえず横置きしてみて
        res += dfs(h, w + 1, a - 1, b);//次のマスへ
        //残りのマスの置き方はこのコードに来たときに確定しているので
        Masu[h, w + 1] = false;//未確定に戻す
    }
    //1畳を縦に置く場合
    {
        //横とほぼ同じなので省略
    }
    
    Masu[h, w] = false;//未確定に戻す
    return res;

DFSは慣れないと書きにくいですが、メインの処理(今回なら半畳を置くパートから)を書いて、例外処理やエラー処理、終了処理をメソッドの頭に後で置くとやりやすい気がします。

まとめ

DFSがさっと書けたら、多分もっとレート上がるはず。