Asa's Blog

AHC004

Tags: AtCoder  AHC  Competitive-Programming 

Published on 2021.06.26. Last Modified on 2021.06.26.

AHC004 の振り返りです。今回は全然思いつかなかったのでかなり悪いです。はい。

問題概要

A, B, …, H からなる $N \times N$ 行列の部分列が $M$ 個与えられるので、これらの部分列をなるべく多く含む、A, B, …, H, . からなる行列を求める。
ただし、. は空白を意味する。部分文字列の方向は、縦方向でも横方向でも可。また、左端と右端、上端と下端はそれぞれつながっている。

得点は、$c=(\text{部分列となっている個数})$とすると、$\mathrm{round}({c \over M} \times 10^8)$ 。($c = M$ の例外があるけど、それは出せなかったので。)

解く

まずは Text でお遊び

提出 #23743171 - AtCoder Heuristic Contest 004

$N=20$ と定まっていたので、全部空白を出力します。

....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................

はい、$c=0$ なので当然 0 点です。

入力順に出力する

提出 #23742286 - AtCoder Heuristic Contest 004

入力順に出力して、1 行の長さが 20 文字を超えそうなら . を残りの文字数分出力した後、出力前に改行します。合計行数が 20 行になったら終わりです。

#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define loop(i,n) for(int i=0;i<n;i++)

int main(){
  int n,m;
  cin >> n >> m;
  vector<string> a,b(m);
  loop(i,m){ cin >> b[i]; }
  string prev = "";
  loop(i,m){
    if(prev.size() + b[i].size() > n){
      int l = n-prev.size();
      loop(j,l){ prev += "."; }
      a.push_back(prev);
      prev = "";
    }
    prev += b[i];
  }
  loop(i,n){
    cout << a[i] << endl;
  }
  return 0;
}

2205949054 点です。得点率は 11%。

行末まで文字を埋める

提出 #23742672 - AtCoder Heuristic Contest 004

先ほどは、1 行が 20 文字を超えそうなら . を残り文字数分出力しました。 ここでは、空白ではなく残り文字数分の文字列を探し、出力します。
また、ソートすることで、文字数の多いものから出力するようにします(大は小を兼ねる的な)。

#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define loop(i,n) for(int i=0;i<n;i++)

int main(){
  int n,m;
  cin >> n >> m;
  vector<string> a,b(m);
  loop(i,m){ cin >> b[i]; }
  sort(all(b),[](string &x, string &y){ return x.size() > y.size(); });
  string prev = "";
  loop(i,b.size()){
    if(prev.size() + b[i].size() > n){
      int l = n-prev.size();
      auto itr = find_if(all(b),[l](string x){ return x.size() == l; });
      if(itr == b.end()){
        loop(j,l){ prev += "."; }
      }
      else{
        prev += *itr;
        b.erase(itr);
      }
      a.push_back(prev);
      prev = "";
    }
    prev += b[i];
  }
  loop(i,n){
    cout << a[i] << endl;
  }
  return 0;
}

2770894529 点です。

すでに「大は小を兼ね」ているものを除外する

提出 #23742989 - AtCoder Heuristic Contest 004

例えば、$s_1$: ABC は $s_2$: ABCDEF の部分文字列になっているので、$s_1$を削除します。

#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define loop(i,n) for(ull i=0;i<n;i++)

int main(){
  int n,m;
  cin >> n >> m;
  vector<string> a,b(m);
  loop(i,m){ cin >> b[i]; }
  sort(all(b),[](string &x, string &y){ return x.size() > y.size(); });
  loop(i,b.size()) for(int j=i+1;j<b.size();j++){
    if(b[i].find(b[j]) != string::npos){
      b.erase(b.begin()+j);
    }
  }
  string prev = "";
  loop(i,b.size()){
    if(prev.size() + b[i].size() > n){
      int l = n-prev.size();
      auto itr = find_if(all(b),[l](string x){ return x.size() == l; });
      if(itr == b.end()){
        loop(j,l){ prev += "."; }
      }
      else{
        prev += *itr;
        b.erase(itr);
      }
      a.push_back(prev);
      prev = "";
    }
    prev += b[i];
  }
  loop(i,n){
    cout << a[i] << endl;
  }
  return 0;
}

2759836466 点。2 千万点下がりました。(だって $s_2$ が出力されているとも限らないもん…)

JavaScript で同じ「ような」コードを試すと…

提出 #23749258 - AtCoder Heuristic Contest 004

;(function (_____) {
  const input = _____.split('\n')
  const [n, m] = input[0].split(' ').map((_) => Number(_))
  let a = [],
    b = input.slice(1)
  b = b.sort((x, y) => y.length - x.length)
  for (let i = 0; i < m; i++)
    for (let j = i + 1; j < m; j++) {
      if (b[i] && b[j]) {
        if (b[i].includes(b[j])) {
          b.splice(j, 1, '')
        }
      }
    }
  let prev = ''
  for (let i = 0; i < b.length; i++) {
    if (prev.length + b[i].length > n) {
      const l = n - prev.length
      const itr = b.filter((_) => _.length === l)[0]
      if (itr) {
        prev += itr
        b = b.filter((_) => _ !== itr)
      } else {
        prev += '.'.repeat(l)
      }
      a.push(prev)
      prev = ''
    }
    prev += b[i]
  }
  console.log(a.slice(0, 20).join('\n'))
})(require('fs').readFileSync('/dev/stdin', 'utf8'))

2781409412 点。なぜか上がった…(たぶん「削除」ではなく「空白で置き換え」をしたから…?)

はい、これで以上です。

結果

システムテストはないようで、上の最高得点(2,781,409,412 点)が順位にかかわるようです。順位は 359/604 位。

この記事を書いている途中に気づいた括弧書き、コンテスト中に気づけばもっといったのかも…?といった感じです。
ただ、最高点の人でも得点率 36%+ちょっとなので、4 割とるのも難しいっぽいです。

すべての提出 - AtCoder Heuristic Contest 004 で見れますが、終了後もいくつか試してみてます。
今後追記するかもしれません。

N=20は確定なのでnをinputする必要なかったかも?(特に意味はない)

keyboard_arrow_up