AtCoder 5 - 不定期プログラミング覚え書き

ω・｀)ﾉﾔｧ､ﾋｻｼﾌﾞﾘ

最近書いてなかったので思いついた時にこれまでのおさらいをしておく。
まずは6/30にあったAtCoder5。A,B,Cは順調に答えられたけれど、Dは全く方針が立たず。
AとBで凡ミスre-submitをかましたため、順位も悲惨だった三完する人の層が厚すぎるのかな。

Problem A 大好き高橋くん

問題

TAKAHASHIKUN、Takahashikun、takahashikun
と完全に一致する単語を数えるだけの簡単なお仕事。
ただし文末は"Takahashikun."となっているかも知れなくて、それを数えなきゃいけない事に注意が必要

考えたこと

やるだけ。

コード

   int n_case;
   cin >> n_case;
   int ans = 0;
   for( int i = 0 ; i < n_case; i++ ){
    string tmp;
    cin >> tmp;
    if( tmp[tmp.size()-1] == '\n' ) tmp = tmp.substr(tmp.size()-1);
    if( tmp == "TAKAHASHIKUN" ) ans++;
    if( tmp == "Takahashikun" ) ans++;
    if( tmp == "takahashikun" ) ans++;
    if( tmp == "TAKAHASHIKUN." ) ans++;
    if( tmp == "Takahashikun." ) ans++;
    if( tmp == "takahashikun." ) ans++;
   }
   cout << ans<<endl;
   return 0;

今更だけどこれなんで改行の処理とか入れたんだろう…無くても動くと思う。

problem B P-CASカードと高橋君

問題

与えられた盤面の、与えられた位置から、与えられた向きに（現在地含み）４マス進み、進んだ枡の値を答えよ。
ただし、盤面の境界に到達したら反射するような挙動を示すとする

考えたこと

やるだけ、方向の解釈を与えるのが面倒くさいです。でもやるだけです。

コード

   int x,y;
   string W;
   cin >> y>>x >> W;
   vector<string> table;
   if( W[W.size()-1]== '\n' ) W = W.substr(W.size()-1);
   string dir[]={"R","L","U","D","RU","RD","LU","LD"};
   int ind;
   for( ind = 0; ind < 8 ; ind++ ) if( W==dir[ind] ) break;
   int dys[]={1,-1,0,0,1,1,-1,-1};
   int dxs[]={0,0,-1,1,-1,1,-1,1};
   int dx = dxs[ind];
   int dy = dys[ind];
   for( int i = 0 ; i < 9 ; i++){
     string tmp;
     cin >>tmp;
     table.push_back(tmp);
   }
   cout << table[x-1][y-1];
   for( int i = 0 ; i < 3 ; i++ ){
      x += dx;
      y += dy;
      if( x == 0 || x == 10 ){
        x -= 2*dx;
        dx = -dx;
      }
      if( y == 0 || y == 10 ){
        y -= 2*dy;
        dy = -dy;
      }
   //cout << x-1 << "," << y-1 << endl;
      cout << table[x-1][y-1];
   }
   cout << endl;
   return 0;

Problem C 器物損壊！高橋君

問題

与えた盤面のスタート地点からゴール地点まで、塀を２回壊すことで行く事ができるか判定せよ

考えたこと

スタート地点から近い（塀を壊す回数が少ない）点を順に見ながら、
隣接点の、「スタートからゴールまで、塀を最小何回壊すだけで移動可能か」を更新するみたいな。
こうやって文章で書いてみるとダイクストラっぽいですね。

コード

   int H,W;
   cin >> H >> W;
   vector<string> map;
   int sx=0,sy=0;
   int gx=0,gy=0;
   for( int i = 0 ; i < H ; i++ ){
     string tmp;
     cin >> tmp;
     map.push_back(tmp);
     for( int j = 0 ; j < W ;j++ ){
      if( tmp[j] =='s' ){
        sx = i;
        sy = j;
      }
      if( tmp[j] == 'g' ){
        gx = i;
        gy = j;
      }
     }
   }
   bool arrived[501][501];
   int dxs[] = {1,-1,0,0};
   int dys[] = {0,0,1,-1};
   memset( arrived , false, sizeof(arrived) );
   int distance[501][501];
   memset(  distance, INT_MAX, sizeof(distance) );
   priority_queue< pair<int, pair<int,int> > > que;
   que.push( make_pair( 0, make_pair(sx,sy) ) );
   while( !que.empty() ){
    pair<int, pair<int,int> > p = que.top();
    que.pop();
    int dist = p.first;
    pair<int,int> p2 = p.second;
    int x = p2.first;
    int y = p2.second;
    //cout << x << "," << y << ": " << -dist << endl;
    if( arrived[x][y] ) continue;
    arrived[x][y] = true;
    distance[x][y] = -dist;
    if( x == gx && y == gy ) break;
    for( int i = 0 ; i < 4; i++ ){
      int dx = dxs[i];
      int dy = dys[i];
      int nx = x+dx;
      int ny = y+dy;
      if( nx < 0 || nx >= H || ny < 0 || ny >= W ) continue;
      int nextd = dist;
      if( map[nx][ny] == '#' )nextd--;
      que.push( make_pair(nextd, make_pair(nx,ny) ));
    }
   }
   if( distance[gx][gy] <= 2 ) cout << "YES" << endl;
   else cout << "NO" << endl;
   return 0;

盤面は最大で500*500だそうで、queueのサイズはたかだか4*500*500=1000000になる、よってまあなんとかなるだろう、と見積もった。

problem D 連射王高橋君

問題

0-9の中の幾つかの数字（ただし0,1は必ず含む）と、+と、=が使える電卓がある。
その電卓を用いて、与えられた数字を表現するための、最もキー入力数が少ない手順を答えよ。

考えたこと

( ﾟдﾟ)………ﾜｶﾝﾈ………