ABC062 ARC074 の問題を解いてみました

A問題

グループに番号をつけて、数字を入力するとグループの番号が返ってくる関数を作成します。
$x$ と $y$ で同じ数が返ってきた場合、同じグループに属していると言えます。

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

int func(int a){ //グループ番号を返す関数
  if(a == 2){
    return 3;
  }
  else if(a == 4 || a == 6 || a == 9 || a == 11){
    return 2;
  }
  else{
    return 1;
  }
}

signed main(){
  int x, y;
  cin >> x >> y;
  
  if(func(x) == func(y)){ //同じ値を返すか判定する
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

B問題

頑張って実装しましょう。

回答例1

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

signed main(){
  int h, w;
  cin >> h >> w;
  
  cout << string(w + 2, '#') << endl;
  
  for(int i = 0; i < h; i++){
    string s;
    cin >> s;
    cout << "#" << s << "#" << endl;
  }
  
  cout << string(w + 2, '#') << endl;
}

回答例2

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

signed main(){
  int h, w;
  cin >> h >> w;
  
  vector<vector<char> > ans(h + 2, vector<char>(w + 2, '#'));
  
  for(int i = 1; i <= h; i++){
    string s;
    cin >> s;
    for(int j = 0; j < w; j++){
      ans[i][j + 1] = s[j];
    }
  }
  
  for(auto p : ans){
    for(auto q : p){
      cout << q;
    }
    cout << endl;
  }
}

C問題

まず、この問題では3つのピースをできるだけ均等に分ける必要があります。

しかし、3つではなく2つのピースに分ける場合はどうなるのかということを考えてみます。
縦のマス数・横のマス数のどちらかが偶数の場合は、完全に半分に分けることができます。

縦横どちらも奇数の場合は、$min(h, w) = S_{max} - S_{min}$ となります。

ここまで、2つのピースに分ける場合について考えてきました。
しかし、この問題では3つのピースに分ける必要があるので、ピースを $ 1:2$に分ける方法も考える必要があります。
($1:2$の$2$の方をさらに2つに分けることで、3つのピースに分けられる)

$1:2$に分けるときには、縦に分ける方法と横に分ける方法の２つがあり、制約が$2 \leq H,W \leq 10^5$ なので、これはどちら全探索できます。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//Created by karaju.

ll func(ll h, ll w){
  ll a, b, c; //3つのピースの面積の変数
  ll ans = 1e9;
  
  for(int i = 1; i < h; i++){ //縦iマスで分ける
    a = i * w;
    ll hh = h - i; //残りのピースの縦の長さ
    
    if(w % 2 == 0 || hh % 2 == 0){ //縦横最低1つが偶数の場合
      b = c = hh * w / 2;
    }
    else{ //両方奇数の場合
      if(hh > w){ //縦のほうが長い場合
        b = (hh / 2) * w;
        c = hh * w - b;
      }
      else{ //横のほうが長い場合
        b = (w / 2) * hh;
        c = hh * w - b;
      }
    }
    
    //S_max - S_min を求める
    ans = min(ans, max({a, b, c}) - min({a, b, c}));
  }
  return ans;
}

signed main(){
  ll H, W;
  cin >> H >> W;
  
  cout << min(func(H, W), func(W, H)) << endl;
}

D問題