ABC-C第9弾

• バチャ9弾
• 急いで書いたのでちょっと雑になってしまった。後で修正。

ABC041 「背の順」

解法

• vector < pair<背の高さ, 番号> >で管理する。
• 入力をソートして出力するだけ

コード

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

using pii = pair<int, int>; 

int N;

int main() {
   cin >> N;
   vector<pii> a;
   for (int i = 0; i < N; i++) {
      int x;
      cin >> x;
      a.push_back({x, i + 1});
   }
   sort(a.begin(), a.end(), greater<pii>());
   for (int i = 0; i < N; i++) {
      cout << a[i].second << endl;
   }

   return 0;
}

ABC042 「こだわり者いろはちゃん / Iroha's Obsession」

解法

• ${D1,D2,...,DK}≠{1,2,3,4,5,6,7,8,9}$という条件により、0を除く使うことのできる数字が少なくとも1種類あることが分かる。
• 嫌いな数字が含まれないような数を作るためには、計算量はそんなに多くならないことが分かる。
  • 使える数字が1種類しかない時でも、$N$より1桁大きい数を作れば良いことが分かる。
  • 例えば、数字の$2$しか使えない状況で$N=9999$が与えられたときは、$N$より1桁大きい値$22222$が答えになることが分かる。
• よって、愚直に計算すればACできる。

コード

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

using ll = long long;

int N, K;
int D[11];

int main() {
   cin >> N >> K;
   for (int i = 0; i < K; i++) {
      cin >> D[i];
   }

   ll num = N;
   while (1) {
      string s = to_string(num); // 数字を文字列にする

      bool ok = true; // 嫌いな数字が存在しないならtrue
      // 嫌いな数字の有無を判定
      for (int i = 0; i < K; i++) {
         if (count(s.begin(), s.end(), D[i]+'0')) {
            ok = false;
            num++;
            break;
         }
      }

      // 嫌いな数字が無ければnumを出力して終了
      if (ok) {
         cout << num << endl;
         return 0;
      }
   }

   return 0;
}

ABC043 「いっしょ / Be Together」

解法

• 入力される数値の範囲が小さいので、どの数字に書き換えるかを全探索すればよい。
• $−100≦x≦100$の範囲をすべて試せばよいが、僕は心配なので大きめの範囲を探索した。

コード

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

using ll = long long;

int N;
int a[111];

int main() {
   cin >> N;
   for (int i = 0; i < N; i++) cin >> a[i];

   ll cost = 1e15;
   for (int i = -1000; i <= 1000; i++) {
      ll sum = 0;
      for (int j = 0; j < N; j++) {
         ll x = (i - a[j]);
         sum += x * x;
      }
      cost = min(cost, sum);
   }
   cout << cost << endl;

   return 0;
}

ABC044 「高橋君とカード / Tak and Cards」

考察

• $k$枚選んだときの平均を考えるのはちょっと複雑なきがするので、もっと単純に考えたい。
• そこで、「$k$枚選んだときの和が$kA$になっていれば、平均が$A$となる。」のように問題文を読み替える。
• つまり、$k$選んだときの和のみに注目すれば良いことになる。
• 数列の中から幾つか選んでその合計を$A$にできるかを判定する問題は、部分和問題と呼ばれている。これはDPで解くことができる。
• DPで解くなら、下図みたいな感じで、$i$個目までの中でいくつか選んだときに得点の合計が$j$になる組み合わせは？って感じで管理したい。これだと2次元のDPテーブルで管理できる。

• でも、今回は何個選んだかという情報も必要なため、DPテーブルに1つ次元を付け足す。付け足すのは、何個選んだかという情報である。
• つまり、「$i$個目までの中で$j$個選んだときの得点の合計は$k$」といった3次元のDPテーブルになる。
• 次に、遷移を考える。DPの基本的な問題であるナップサック問題の遷移を頭に思い浮かべながら考える（僕が知ってるDPがこれくらいしかない）。
• 遷移は、部分和数え上げ問題のコードを参考にして考える。参考にするコードはリンク先に載っている。
• すると、漸化式をなんとなく立てることができる。（この辺は僕も手探りでやったのでどうやってコードを書いたのかは説明できない。。。）

コード

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

using ll = long long;

int N, A;
int x[111];
ll dp[111][111][5555];

int main() {
   cin >> N >> A;
   for (int i = 0; i < N; i++) cin >> x[i];

   dp[0][0][0] = 1;
   for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
         for (int k = 0; k <= 5000; k++) {
            // 選ばない
            dp[i+1][j][k] += dp[i][j][k];
            // 選ぶ
            if (k >= x[i]) {
               dp[i+1][j+1][k] += dp[i][j][k-x[i]];
            }
         }
      }
   }

   ll ans = 0;
   for (int j = 1; j <= N; j++) {
      ans += dp[N][j][j*A];
   }
   cout << ans << endl;

   return 0;
}

感想

• むずい！！！けど、数ヶ月前は1ミリも理解できなかったのに比べたらマシになったと思う。
• 「$k$枚選んだときの平均を考える」問題から、「$k$枚選んだときの和が$kA$になっている部分を考える」問題へ読み替えるのがなかなかできそうにない。。。
• こういった問題文の読み替え、すごく大事なんだけどいつもできない。
• あと、DP書くのも難しかった。。。部分和問題を知らないとこの問題解けない気がするんだが。センスのいい人は普通に思いついたりするのか？
• この問題で重要だったのは、「問題文を簡単なものに読み替える」、「部分和問題の応用を考える」、「DPするための情報が足りなかったら次元を一つ足す」というものだったと思う
• 後ろの2つはけんちょんさんのDP記事に載っていた考え方。
• この問題、なんとなく理解できたけど類題を自分で解けるかてなると微妙なのでなんとなくもやもやが残る。。。

ABC045 「たくさんの数式 / Many Formulas」

解法

• 文字列の長さは最大10文字である。よって、+を入れる箇所は9個ある。
• この9か所について+を入れる、入れないを試す。計算量は$O(2^{|S|})$なので愚直に計算しても間に合う。

コード(あとで修正)

• ちょっとこのコード汚いので、あとで修正する
• 上位陣はもっときれいに実装していた。

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

using ll = long long;

ll f(string &s) {
   string a = "";
   ll sum = 0;
   int n = s.size();
   for (int i = 0; i < n; i++) {
      if (s[i] == '+') {
         sum += stoll(a);
         a = "";
      } else {
         a += s[i];
      }
   }
   sum += stoll(a);
   return sum;
}

int main() {
   string s;
   cin >> s;

   int n = s.size();
   ll sum = 0;
   for (int mask = 0; mask < (1<<(n-1)); mask++) {
      string t;
      t += s[0];
      for (int i = 0; i < n-1; i++) {
         if ((mask >> i)&1) {
            t += '+';
         }
         t += s[i+1];
      }
      sum += f(t);
   }
   cout << sum << endl;

   return 0;
}