ABC-C第16弾

• バチャ16弾
• 全然書いてない（順次書き足します）

ABC076 「Dubious Document 2 」

考察

• 文字列SにTを当てはめたとき、辞書順で最小となる文字列を探す。条件に当てはまらなければUNRESTORABLEと出力。
• 文字列が当てはまるかを考える。これは簡単に判定できそうだが、問題なのはどこに当てはめるか。
• ここで、文字列が当てはまったと仮定して?をなにで埋めるか考える。辞書順最小なのでaを当てはめれば良さそう。
• 再び文字列Tをどこに当てはめれば良いか考える。これは、文字列Sのできるだけ後ろの方に当てはめた方がいい気がしてくる。abcaaaaよりもaaaaabcの方が辞書順で最小になるから。

解法

• 文字列Sを後ろの方から見ていき、文字列Tを当てはめられるならそこに当てはめる。
• 残った?はaに置き換える。
• 文字列Tが文字列Sに当てはまらないならUNRESTORABLEを出力する

嘘解法の可能性

• http://hamayanhamayan.hatenablog.jp/entry/2017/10/28/230027
• https://kimiyuki.net/blog/2017/12/08/abc-076-c/
• http://fal-rnd.hatenablog.jp/entry/2017/10/28/230300
• この辺のブログ見た感じ僕の解法嘘解法っぽい
• 余り詳しく見てないからよくわかんないけど。
• 後で見る！！！予定！！

コード

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

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

   // 文字列を後ろから見ていく
   for (int i = s.size()-1; i >= 0; i--) {
      // sからt.size()文字分抜き出す
      string p = s.substr(i, t.size());
      if (p.size() != t.size()) continue;

      // 置けるかどうかを判定
      bool ok = true;
      for (int j = 0; j < p.size(); j++) {
         if (p[j] == '?') continue;
         if (p[j] != t[j]) ok = false;
      }

      // 置けるならそこに置いて出力して終了
      if (ok) {
         int cnt = 0;
         for (int j = i; j < i+t.size(); j++) {
            s[j] = t[cnt];
            cnt++;
         }
         replace(s.begin(), s.end(), '?', 'a');
         cout << s << endl;
         return 0;
      }
   }

   // 最終的に置けないならこれを出力
   puts("UNRESTORABLE");

   return 0;
}

replace()関数

• 余り使わないので存在を忘れがち。めんどい処理を楽にかけるので結構強い。
• replace(first, last, 置換対象の文字, 置換後の文字)みたいに使う。
• 具体的にはreplace(str.begin(), str.end(), 'a', 'b')みたいに使う。
• 文字列じゃなくて配列でもできるっぽい。

感想

• 後ろから見ていくっていうのがなかなか思いつかない気がする。

ABC077 「Snuke Festival 」

• 上と真ん中、真ん中と下は独立して考えることができる点に注目。
• 愚直にやると$O(N^2)$だけどソートしてやればにぶたんで解けるので$O(NlogN)$になる

ABC078 「HSI」

• よくわからない。

ABC079 「Train Ticket 」

• 解けたからさいごに適当に書く。
• 文字列を計算して返してくれる関数欲しい。実装が割とだるい。

ABC080 「Shopping Street 」

考察と解法

• 問題文を要約すると上図のような感じ。
• 問題文が複雑なので少し整理する
  • 商店街には店が$N$個ある。
  • 各店の営業時間が与えられる。
  • 店$i$とjoisinoの店の両方が営業している時間帯の個数$c$としたとき、joisinoの店の利益に$P_{i,c}$がプラスされる。これをすべての店について行う。
  • 自分の店の10個の営業時間は自分で決める
  • このとき、利益の最小を求めたい。
• joisinoの利益を最大化したい。これは、joisinoがどの時間に営業するかを全列挙すれば求められそう。全列挙の組み合わせは$2^10=1024$通りとなる。ある組み合わせの時の利益を求めるのが最大で$10 \times 100=10^3$通りとなる。なので、全体の計算回数は大体$10^6$となり全列挙で間に合う

コード

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

using ll = long long;

int N; // 店の数
int F[111][11]; // 営業時間
int P[111][11]; // 利益

int main() {
   // 入力
   cin >> N;
   for (int i = 0; i < N; i++) {
      for (int j = 0; j < 10; j++) {
         cin >> F[i][j];
      }
   }
   for (int i = 0; i < N; i++) {
      for (int j = 0; j < 11; j++) { // 0個~10個なので1列の入力は11個ある
         cin >> P[i][j];
      }
   }

   ll ans = -1e15;
   for (int mask = 1; mask < (1<<10); mask++) {
      ll sum = 0;
      for (int i = 0; i < N; i++) {
         int cnt = 0;
         for (int j = 0; j < 10; j++) {
            if (((mask>>j)&1) && F[i][j]) cnt++;
         }
         sum += P[i][cnt];
      }
      ans = max(ans, sum);
   }
   cout << ans << endl;

   return 0;
}

感想

• まず問題文が難しい。実質読解力コンテスト
• なにに気がつくと良かったんだろう？なんか難しいよね。これ。
• 「入力とは別に、10個の営業時間を自分で決める」ことを頭に置いていたら解けたのかな...?
• 問題文が複雑だったら一度整理してみるというのが大事そう。早く解こうと焦ると、頭が爆発したり問題の本質を見失ったりしがち。自分が読んで複雑だと感じたら他の人も複雑と感じているはずなので、焦らずに頭を整理しつつ解きたい。