ABC054 の問題を解いてみました

A問題

1 以外は 大きい方が勝利するので、 1 をどうにかしたいです。
1 を 14 にすることで、1 を最強にできます。
そして、大小を比較することで、この問題は解くことができます。

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

int main(void){
  int a, b;
  cin >> a >> b;
  if(a == 1) a = 14; // 1 を最強にする
  if(b == 1) b = 14; // 1 を最強にする
  
  if(a == b){
    cout << "Draw" << endl;
  }
  else if(a > b){
    cout << "Alice" << endl;
  }
  else{
    cout << "Bob" << endl;
  }
}

B問題

テンプレート画像B の左上 が 画像A のどこかだと仮定して、それが正しいかどうかを確かめるということを繰り返すことによって、解くことができます。

実装が少し難しいかもしれません。
(下のコードを参考にしてみてください)

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

int main(void){
  int n, m;
  cin >> n >> m;
  string a[n], b[m];
  for(int i = 0; i < n; i++) cin >> a[i];
  for(int i = 0; i < m; i++) cin >> b[i];
  
  for(int i = 0; i <= n - m; i++){
    for(int j = 0; j <= n - m; j++){
      //一致するか調べる
      bool ok = true;
      for(int k = 0; k < m; k++){  //縦の大きさ 回繰り返す
        if(a[i+k].substr(j, m) != b[k]){ //横が一致するか調べる
        //substr とは j文字目から、m文字 取り出す というもの
          ok = false;
        }
      }
      if(ok){ //一致したなら
        cout << "Yes" << endl;
        return 0;
      }
    }
  }
  cout << "No" << endl;
}

C問題

深さ優先探索で、頂点1 を始点として、全ての頂点に訪れられるパスの数を数えます。
制約はとても小さいので、 TLE せずに解くことができます。

入力例1 への処理を見てみましょう。

入力例1

3 3
1 2
1 3
2 3

（プログラム内では、頂点の番号が -1 されています。)

• 入力を受け取ります
• まず、dfs(0) を実行します
• for(int i = 0; i < 3; i++) というループが実行されます。
  • 頂点1は、すでに訪れているので、if文の中は実行されません。
  • 頂点1 と 頂点2 は結ばれているので、if文の中が実行されます。
    • visited[1] = true; になって、 dfs(1) が実行されます。
      • 頂点1は、すでに訪れているので、if文の中は実行されません。
      • 頂点2は、すでに訪れているので、if文の中は実行されません。
        • visited[2] = true; になって、 dfs(2) が実行されます。
        • すべての頂点に訪れたので、 dfs(2) は 1 を返します。
      • dfs(2) から 1 が返ってきたので、dfs(1) の ans は 1 になります。
      • dfs(1) の処理が終了して、 ans = 1 を返します。
  • dfs(1) から 1 が返ってきたので、dfs(0) の ans は 1 になります。
  • 頂点2 と 頂点3 は結ばれているので、if文の中が実行されます。
    • visited[2] = true; になって、 dfs(2) が実行されます。
      • 頂点1は、すでに訪れているので、if文の中は実行されません。
        • visited[1] = true; になって、 dfs(1) が実行されます。
        • すべての頂点に訪れたので、 dfs(1) は 1 を返します。
      • dfs(1) から 1 が返ってきたので、dfs(2) の ans は 1 になります。
      • 頂点3は、すでに訪れているので、if文の中は実行されません。
      • dfs(2) の処理が終了して、 ans = 1 を返します。
  • dfs(2) から 1 が返ってきたので、dfs(0) の ans は 2 になります。
  • dfs(0) の処理が終了して、 ans = 2 を返します。
• dfs(0) から返ってきた 2 が出力されます。

下のコードは上のように実行されます。

#include <bits/stdc++.h>
using namespace std;
//Created by karaju.
bool graph[10][10], visited[10];
int n, m;

int dfs(int now){
  bool ok = true;
  for(int i = 0; i < n; i++) if(!visited[i]) ok = false;
  
  if(ok) return 1;
  //もし、全てに訪れられたなら 1 を返す (1 通りあるよということ)
  
  int ans = 0;
  
  for(int i = 0; i < n; i++){ //すべての頂点に訪れようとする
    if(graph[now][i] && !visited[i]){ 
    //今いる頂点と次向かう頂点が結ばれている、かつ訪れたことがないなら
      visited[i] = true;
      //次向かう頂点に訪れる
      
      ans += dfs(i);
      //全てに訪れられる方法の数を受け取る
      
      visited[i] = false;
      //向かった頂点を未訪問にする(他の組み合わせも試す)
    }
  }
  
  return ans;
}

int main(void){
  cin >> n >> m;
  for(int i = 0; i < m; i++){
    int a, b;
    cin >> a >> b;
    a--; b--;
    graph[a][b] = graph[b][a] = true; //辺で結ばれていることを記録
  }
  visited[0] = true; //スタート地点に訪れる
  for(int i = 1; i < n; i++) visited[i] = false;
  
  cout << dfs(0) << endl;
}

D問題

この問題は、bit全探索は使用できなく、$a_i, b_i$ の制約がかなり小さいので、DPを使うと考えられます。

DPの解説記事

$dp[j][k] := タイプAの薬品をjグラム、タイプBの薬品をkグラム購入するときの最小金額$ と定義します。

$dp[0][0] = 0$ です。

dp[j + a[i]][k + b[i]] = min(dp[j + a[i]][k + b[i]], dp[j][k] + c[i])

で、i番目の薬品を購入し、もしそれが薬品Aを$j + a[i]$グラム,薬品Bを$k + b[i]$グラム購入できる最も安い方法なら、配列の要素を更新するという操作を行っています。

物質Cを生成できるには、(薬品Aの量をA, 薬品Bの量をBとします) $A : B = M_a : M_b$ つまりは、 $A \times M_b = B \times M_a$ が成り立つ必要があるので、その条件を満たす最小値を変数に記録します。($a : b = c : d なら、 ad = bc$)

最後に変数の値を出力することによって、この問題は解くことができます。

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

signed main(){
  int n, ma, mb;
  cin >> n >> ma >> mb;
  
  vector<int> a(n), b(n), c(n);
  for(int i = 0; i < n; i++){
    cin >> a[i] >> b[i] >> c[i];
  }
  
  vector<vector<int> > dp(320, vector<int>(320, 1e9));
  dp[0][0] = 0;
  
  int ans = 1e9;
  for(int i = 0; i < n; i++){
    
    for(int j = 300; 0 <= j; j--){
      for(int k = 300; 0 <= k; k--){
        if(dp[j][k] != 1e9){
          dp[j + a[i]][k + b[i]] = min(dp[j + a[i]][k + b[i]], dp[j][k] + c[i]);
        }
        if((k + b[i]) * ma == (j + a[i]) * mb){ //比を満たしているか判定する
            ans = min(ans, dp[j + a[i]][k + b[i]]);
            //条件を満たす最小コストを記録しておく
        }
      }
    }
  }
  if(ans == 1e9){
    cout << -1 << endl;
    return 0;
  }
  cout << ans << endl;
}