Atcoder Biginner Contest 184 (ABC184)振り返り

 Atcoder Biginner Contest 184に参加しました。
atcoder.jp

A問題

A - Determinant
　a×d-b×cを計算して出力。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int a, b, c,d;
  cin >> a >> b >> c >> d;
  cout << a*d-c*b << endl;
}

B問題

B - Quizzes

　oならば持ち点を1増やし、そうでなければ1減らす。
持ち点が0より大きいときのみ減らせること注意して実装すればよい。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N, X;
  string S;
  cin >> N >> X >> S;
  for(int i=0; i<N; i++){
    if(S.at(i)=='o')X++;
    else if(X>0)X--;
  }
  
  cout << X << endl;
}

C問題

C - Super Ryuma

　斜めに1つ移動するときマスの座標の偶奇が変わる。よって斜め移動を行うときには、現在いるマスに応じて
・A: (偶, 偶)→(奇, 奇)→(偶, 偶)→(奇, 奇)→……
・B: (偶, 奇)→(偶, 奇)→(偶, 奇)→(偶, 奇)→……
のAまたはBのどちらかのパターンで移動することになる。別の言い方をすれば、斜め移動では偶奇性(パリティ)の等しいマスにのみ移動できるということである。

　上の図のマスAからマスBへの移動は同じパリティ間の移動なので2手で移動できる。パリティの異なるマスAからマスCの移動では高々3手で移動できるため、どのマスに移動する場合でも0~3手で移動できる。
　・0手
　　移動前後が同じマスかを調べればよい。
　・1手
　　問題文中に与えられた3条件のいずれかを満たせばよい。
　・2手
　　1. パリティが等しい。
　　2. |r1-r2|+|c1-c2|≦6
　　　移動できる距離が6になったので、3番目の条件式を6に変える。
　　3.斜め移動と3マス以下の移動の組み合わせ。1番目、2番目の条件と3番目の条件を組み合わせればよい。
　　高校数学で言うところの領域をイメージしてもらえると助かる。|y-x|=0 (またはy=|x|)と|y-x|≦3とか。

　・3手
　　上記以外すべて。
　以上の場合分けを行えば終了。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int r1, c1, r2, c2, ans;
  cin >> r1 >> c1 >> r2 >>c2;
  if(r1==r2&&c1==c2)ans=0;
  else if((r1+c1==r2+c2)||(r1-c1==r2-c2)||(abs(r1-r2)+abs(c1-c2)<=3))ans=1;
  else{
    if((r1+c1)%2==(r2+c2)%2)ans=2;
    else if(abs(r1-r2)+abs(c1-c2)<=6)ans=2;
    else if(abs(r1+c1-r2-c2)<=3)ans=2;
    else if(abs(r1-c1-r2+c2)<=3)ans=2;
    else ans=3;
  }
  
  cout << ans << endl;
}

D問題

D - increment of coins
　動的計画法(DP)を用いた期待値の計算を行う、という方向性はわかった。DPの実装方法も何を持っていればよいかもわからなかったため手が出せず。勉強と経験不足。

E問題

E - Third Avenue
　幅優先探索(BFS)で解けばよい、という方向性はわかった。BFPの実装方法をネットで調べながらコードを書いていたが間に合わず。勉強と経験不足。

F問題

　そもそも問題を見てない()。

感想

　DE問題の難易度が高い(体感)。いえ、基礎的なアルゴリズムの実装力不足なのはわかってます。連休はDP, BFS, DFSあたりの勉強かな。