Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-07-11

Codeforces #76 Div. 2 C. Frames (Div1 A問題) 00:24 はてなブックマーク - Codeforces #76 Div. 2 C. Frames (Div1 A問題) - 練習帳

 問題文:http://www.codeforces.com/contest/94/problem/C

分析

 どのようにすれば全体を網羅できるのかが,掴めないのが難しいです.

まず,削除するディレクトリの終点が最後の場合(b==n),bを行の右端まで増やした場合と答えは同じになります.最初にその操作をしておきます.

 □を選択しないディレクトリ,■を選択するディレクトリとして現します.■の始点と終点の列(横方向)の位置で場合分けした上で,行方向に何行あるかで場合分けをします.

 下図では,上下方向は■の始点と終点の横方向の位置での場合分け,左右方向は行数で場合分けをし,それぞれの図の下の「>n」でその場合の答えがnである事を示しています.

(始点の列位置)< (終点の列位置)- 1,始点は左端でなく,終点は右端でない
□□□□□□□□□□□□□□ □□□□□□□□□□□□□□ □□□□□□□□□□□□□□
□□■■■■■■■■■■□□ □□■■■■■■■■■■■■ □□■■■■■■■■■■■■
□□□□□□□□□□□□□□ ■■■■■■■■■■■■□□ ■■■■■■■■■■■■■■
□□□□□□□□□□□□□□ □□□□□□□□□□□□□□ ■■■■■■■■■■■■■■
□□□□□□□□□□□□□□ □□□□□□□□□□□□□□ ■■■■■■■■■■■■□□
□□□□□□□□□□□□□□ □□□□□□□□□□□□□□ □□□□□□□□□□□□□□
>1                     >2                     >3

(始点の列位置)= (終点の列位置)- 1,始点は左端でなく,終点は右端でない
□□□□□□□□□□□□□□ □□□□□□□□□□□□□□ □□□□□□□□□□□□□□
□□□□□□□□□□□□□□ □□■■■■■■■■■■■■ □□■■■■■■■■■■■■
□□□□□□□□□□□□□□ ■■□□□□□□□□□□□□ ■■■■■■■■■■■■■■
□□□□□□□□□□□□□□ □□□□□□□□□□□□□□ ■■■■■■■■■■■■■■
□□□□□□□□□□□□□□ □□□□□□□□□□□□□□ ■■□□□□□□□□□□□□
□□□□□□□□□□□□□□ □□□□□□□□□□□□□□ □□□□□□□□□□□□□□
>なし                  >2                     >2

(始点の列位置)> (終点の列位置)- 1,始点は左端でなく,終点は右端でない
□□□□□□□□□□□□□□ □□□□□□□□□□□□□□ □□□□□□□□□□□□□□
□□□□□□□□□□□□□□ □□□□□□□□■■■■■■ □□□□□□□□■■■■■■
□□□□□□□□□□□□□□ ■■□□□□□□□□□□□□ ■■■■■■■■■■■■■■
□□□□□□□□□□□□□□ □□□□□□□□□□□□□□ ■■■■■■■■■■■■■■
□□□□□□□□□□□□□□ □□□□□□□□□□□□□□ ■■□□□□□□□□□□□□
□□□□□□□□□□□□□□ □□□□□□□□□□□□□□ □□□□□□□□□□□□□□
>なし                  >2                    >3

始点は左端で,終点は右端でない
□□□□□□□□□□□□□□ □□□□□□□□□□□□□□ □□□□□□□□□□□□□□
■■■■■■■■■■■■□□ ■■■■■■■■■■■■■■ ■■■■■■■■■■■■■■
□□□□□□□□□□□□□□ ■■■■■■■■■■■■□□ ■■■■■■■■■■■■■■
□□□□□□□□□□□□□□ □□□□□□□□□□□□□□ ■■■■■■■■■■■■■■
□□□□□□□□□□□□□□ □□□□□□□□□□□□□□ ■■■■■■■■■■■■□□
□□□□□□□□□□□□□□ □□□□□□□□□□□□□□ □□□□□□□□□□□□□□
>1                     >2                     >2

始点は左端でなく,終点は右端
□□□□□□□□□□□□□□ □□□□□□□□□□□□□□ □□□□□□□□□□□□□□
□□■■■■■■■■■■■■ □□■■■■■■■■■■■■ □□■■■■■■■■■■■■
□□□□□□□□□□□□□□ ■■■■■■■■■■■■■■ ■■■■■■■■■■■■■■
□□□□□□□□□□□□□□ □□□□□□□□□□□□□□ ■■■■■■■■■■■■■■
□□□□□□□□□□□□□□ □□□□□□□□□□□□□□ ■■■■■■■■■■■■■■
□□□□□□□□□□□□□□ □□□□□□□□□□□□□□ □□□□□□□□□□□□□□
>1                     >2                    >2

始点は左端で,終点も右端
□□□□□□□□□□□□□□ □□□□□□□□□□□□□□ □□□□□□□□□□□□□□
■■■■■■■■■■■■■■ ■■■■■■■■■■■■■■ ■■■■■■■■■■■■■■
□□□□□□□□□□□□□□ ■■■■■■■■■■■■■■ ■■■■■■■■■■■■■■
□□□□□□□□□□□□□□ □□□□□□□□□□□□□□ ■■■■■■■■■■■■■■
□□□□□□□□□□□□□□ □□□□□□□□□□□□□□ ■■■■■■■■■■■■■■
□□□□□□□□□□□□□□ □□□□□□□□□□□□□□ □□□□□□□□□□□□□□
>1                     >1                     >1

これをまとめると,

  • 始点と終点が同じ行にあれば必ず1
  • そうではない場合,
    • 始点と終点いずれかが端にある場合は3-(端の数)で計算され,
    • 両者がいずれも端にない場合には,
      • 「始点と終点の行の差が1」または「(始点の列位置)==(終点の列位置)- 1」なら2
      • それ以外の場合は3

となる.

コード例

 これがA問題なんてDiv.1恐ろしい.

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <cstring>

using namespace std;

int main(){
  int n, m, a, b;
  while(cin >> n >> m >> a >> b){
    if(n == b){
      b = b - ((b-1)%m) -1 + m;
    }
    bool flag = false;
    int count = 0;
    
    if((a-1)/m == (b-1)/m){
      cout << 1 << endl;			
      goto next;
    }

    if((a-1)%m == 0){
      flag = true;
      count++;
    }
    if(b%m == 0){
      flag = true;
      count++;
    }
    if(flag){
      cout << 3-count <<endl;
      goto next;
    }

    if((a-1)/m + 1 == (b-1)/m || (a-1)%m == (b-1)%m + 1){
      cout << 2 <<endl;
      goto next;
    }

    cout << 3 <<endl;

  next:;
  }
}