LoginSignup
2
0

More than 3 years have passed since last update.

@add_bakkers(加藤 響)

緑コーダーだけどなんとかSuperCon本選出場チームになれた話

Last updated at Posted at 2020-07-18

こんにちは、加藤響といいます。
普段はAtCoder というサイトで競技プログラミングをしています。
今回は、スーパーコンピューティングコンテストという大会で本選参加チームになることができたので、参戦記みたいなものを書いてみようと思います。

はじめに

スーパーコンピューティングコンテストについて説明しようと思います。
スーパーコンピューティングコンテスト(SuperCon)は、２〜３人でチームで一つの問題に取り組んで、最終的にソースコードを提出し、採点結果により本選参加チームが決まります。
いわゆるマラソン系の問題で、解が一意に定まるものではなく、なるべく良い答え（例えば、なるべく安いコストで課題を達成するなど）を出力するソースコードを書くと言うものです。
2020年度の予選問題

この記事の対象読者

  • 現在高校生で、プログラミングで活躍する場が欲しい人
  • SuperConに興味があるけど、ちょっと敷居が高く感じる人

チーム

僕のチームはAtCoderのレートで言うと緑（ぼく）、茶、灰の三人でした。
考察と実装は自分が担当し、チームメイトにはテストケースの作成と、出力が合っているかの検証を担当してもらいました。

弱くても努力次第で戦えるコンテストかもよって話

普段AtCoderのコンテストに参加されている人ならわかると思いますが、この世界にはどーやったって敵わないような強すぎる人たちがいます。コンテスト中2時間たっぷりかけてやっと解けるような問題を瞬殺してしまうような人たちです。
しかし、このコンテストには問題を与えられてから提出まで三週間弱あります。考察もじっくり出来るし、有用そうなアルゴリズムを片っ端から検索出来ます。なんならこの期間に新しいアルゴリズムやデータ構造を勉強しながらコーディングできます。
普段諦めるような問題も、三週間あればとりあえず提出するだけの物は作れそうな感じがしますよね？

提出したもの

内容について解説はしませんが、雰囲気だけ感じてください（？）
一応使ったアルゴリズムだけ列挙すると、
選択ソート
DP(個数制限なし部分和)
DPの復元
こんなもんです。検索して記事とか見ながら書きました。

#include <bits/stdc++.h>
using namespace std;
const int INF=101000;
/*
 * 出力の各行に対応する操作の情報を表す。
 * type = 1 のとき、代入を表す。
 * この時、 S は代入の情報を表す。
 * type = 2 のとき、入れ替えを表す。
 * この時、 i 番目の文字と j 番目の文字を入れ替えることを表す。
*/
struct producer{
    int type;
    char S[1100];
    int i, j;
};

int letter_count_s[26],letter_count_t[26];
string s,t;
int dp[27][27][100100];//DPテーブル
vector<int> point_vec[27];//それぞれの文字のオフセットを管理
vector<char> s_to_t;//置換済の文字列。これをソートしてtにする
vector<char> hukugen_char[26];
vector<producer> ans;
void hibiki_sort(){//ソート
    for (int i=0;i<27;i++){
        point_vec[i]={};
    }
   for (int i=0;i<s_to_t.size();i++){
       point_vec[s_to_t[i]-'a'].push_back(i);//文字列s_to_tの文字のオフセットを文字ごとのvectorに格納
   }
   int i=s_to_t.size()-1;
   for (int j=26;j>=0;j--){
       for (int k=0;k<point_vec[j].size();){
           int x=point_vec[j][k],y;
           char a=s_to_t[i];
           int A=a-'a';
           for (int l=0;l<point_vec[a-'a'].size();l++){
               if (point_vec[a-'a'][l]==i){
                   y=l;
                   break;
               }
           }
           if (i<x){
               k++;
               continue;
           }
           if (s_to_t[i]==s_to_t[x]){
               i--;
               continue;
           }
           s_to_t[i]=('a'+j);
           s_to_t[x]=a;
           point_vec[j][k]=i;
           point_vec[a-'a'][y]=x;
           producer irekae;
           irekae.type=2;
           irekae.i=min(i,x)+1;
           irekae.j=max(i,x)+1;
           ans.push_back(irekae);
           i--;
           k++;
       }
   }
}

void hukugen(int c,int j){
    for (int i=26;i>0;i--){
        int num_s=letter_count_s[i-1];
        while(j-num_s>=0){
            if (dp[c][i][j-num_s]){
                hukugen_char[c].push_back('a'+i-1);
                num_s+=letter_count_s[i-1];
            }else{
                break;
            }
        }
        j-=num_s;
        j+=letter_count_s[i-1];
    }
}

void output(int yn, int n) {
  if (!yn) {
    printf("NO\n");
  } else {
    printf("YES\n");
    printf("%d\n", n);
    int k;
    for (k = 0; k < n; k++) {
      if (ans[k].type == 1) {
        printf("%d %s\n", ans[k].type, ans[k].S);
      } else {
        printf("%d %d %d\n", ans[k].type, ans[k].i, ans[k].j);
      }
    }
  }
  fflush(stdout);
}

int main(){
   bool flag=true;
   for (int i=0;i<26;i++){
       for (int j=0;j<26;j++){
           fill(dp[i][j],dp[i][j]+100100,0);//DPテーブルの初期化（未探索は0）
       }
       dp[i][0][0]=1;//初期値1
   }
   cin >> s >> t;
   fill(letter_count_s,letter_count_s+26,0);
   fill(letter_count_t,letter_count_t+26,0);
   //SとTの文字数を数える
   for (int i=0;i<s.size();i++){
       letter_count_s[s[i]-'a']=letter_count_s[s[i]-'a']+1;
   }
   for (int i=0;i<t.size();i++){
       letter_count_t[t[i]-'a']=letter_count_t[t[i]-'a']+1;
   }
   for (int i=0;i<26;i++){
       if (letter_count_s[i])continue;
       letter_count_s[i]=INF;
   }
   //DP
   for (int i=0;i<26;i++){
       for (int j=0;j<26;j++){
           for (int num_t=0;num_t<=letter_count_t[i];num_t++){
               dp[i][j+1][num_t]+=dp[i][j][num_t];
               int num_s=letter_count_s[j];
               while(num_t+num_s<=letter_count_t[i]){
                   dp[i][j+1][num_t+num_s]+=dp[i][j][num_t];
                   num_s+=letter_count_s[j];
               }
           }
       }
   }
    //YESNOの判定の判定。sに含まれている文字列をどう置換するかがvectorに格納されていない場合は、tが達成できないということ。
   for (int i=0;i<26;i++){
       if (letter_count_t[i]){
           if (dp[i][26][letter_count_t[i]]==0){
               flag=false;
           }
       }
   }
   if (!flag){
       output(0,0);//プログラム終了
       return 0;
   }
   //DPの復元
   for (int i=0;i<26;i++){
       hukugen(i,letter_count_t[i]);
   }
   for (int i=0;i<s.size();i++){
       s_to_t.push_back(s[i]);
   }
   hibiki_sort();
   for (int i=0;i<s.size();i++){
       s[i]=s_to_t[i];
   }
   s_to_t={};
   for (int i=25;i>=0;i--){
       int count=1,chikan_count[26];
       fill(chikan_count,chikan_count+26,0);
       for (int j=0;j<hukugen_char[i].size();j++){
           if (j==hukugen_char[i].size()-1){
               chikan_count[hukugen_char[i][j]-'a']=count;
               while(count>0){
                   producer dainyuu;
                   dainyuu.type=1;
                   dainyuu.S[0]=hukugen_char[i][j];
                   dainyuu.S[1]=hukugen_char[i][j];
                   for (int k=0;k<min(count,1000);k++){
                       dainyuu.S[k+2]=(char)('A'+i);
                   }
                   dainyuu.S[min(count+2,1002)]='\0';
                   ans.push_back(dainyuu);
                   count-=1000;
               }
           }else if (hukugen_char[i][j]==hukugen_char[i][j+1]){
               count++;
           }else{
               chikan_count[hukugen_char[i][j]-'a']=count;
               while(count>0){
                   producer dainyuu;
                   dainyuu.type=1;
                   dainyuu.S[0]=hukugen_char[i][j];
                   dainyuu.S[1]=hukugen_char[i][j];
                   for (int k=0;k<min(count,1000);k++){
                       dainyuu.S[k+2]=(char)('A'+i);
                   }
                   dainyuu.S[min(count+2,1002)]='\0';
                   ans.push_back(dainyuu);
                   count-=1000;
               }
               count=1;
           }
       }
       for (int j=0;j<s.size();j++){
           count=chikan_count[s[j]-'a'];
           if (count==0){
               s_to_t.push_back(s[j]);
           }
           while(count>0){
               s_to_t.push_back(s[j]);
               for (int k=0;k<min(count,1000);k++){
                   s_to_t.push_back((char)('a'+26));
               }
               count-=1000;
           }
       }
       hibiki_sort();
       s_to_t={};
   }
   for (int i=0;i<26;i++){//小文字の残骸を消去
       if (letter_count_s[i]!=INF){
           producer dainyuu;
           dainyuu.type=1;
           dainyuu.S[0]=(char)('a'+i);
           dainyuu.S[1]='\0';
           ans.push_back(dainyuu);
       }
   }
   for (int i=0;i<26;i++){
       if (letter_count_t[i]){
           producer dainyuu;
           dainyuu.type=1;
           dainyuu.S[0]=(char)('A'+i);
           dainyuu.S[1]=(char)('a'+i);
           dainyuu.S[2]='\0';
           ans.push_back(dainyuu);
       }
   }
   //答えの出力
   output(1,ans.size());
   return 0;
}

こんな感じです。234行。

本戦中止！wwww

「本選出場チーム選出と本選中止のお知らせ」っていうメールが来ました。あはは......

『新型コロナウイルス感染拡大に伴なう高等学校、高等専門学校、大学をとりまく状況や参加する生徒の皆様のリスクを踏まえ、本選開催の可能性を模索してまりましたが、大変残念ではございますが、SuperCon 2020本選は中止することとなりました。

貴チームはSuperCon2020本選出場チームのとして選出されたにも関わらず、本選が中止となり、大変残念でございます。』

とのことです。まあしょうがないかな。

終わりに

本選が中止となり、なんとなくモヤモヤしていたので、この記事を書いてすっきりすることにします。読んで下さった高校生/高専生の方は、是非SuperConに挑戦してみてください。

2
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
0