えびまのお誕生日コンテスト 2021 Day 1の感想

えびまさんのお誕生日コンテストに参加しました。問題はこちらから。

Tasks - evima's Birthday Contest 2021 Day 1

結果はAEの2完でした。

正規のコンテストではないので、気楽に楽しめました。いつものABCと問題の毛色が違いすぎてびっくりしましたが、頑張れたんじゃないかと思います。レートがなくてあんまり語ることもないので感想いきます。

A問題

俗にいう「つるかめ算」ですね。この問題は部分点があるので、まずは計算量を考えずに、解いてみました。

どうやら蟹の種類は2種類あるようですので、蟹Aの数aと蟹Bの数bを持ったdfsを考えました。

判定式は

(n - 8*a - 10 * b) % 26 == 0

で再帰部分は

return min(dfs(a+1,b),dfs(a,b+1));

こんな感じです。こうすれば、aとbを１つずつ増やしながら探索が可能です。

ひとまず、これで提出。部分点は獲得したものの、TLEとREでした。

26の余りに注目すると、その数は高々26種類しかありません。ということで、aとbが26を超えたらdfsを打ち切りました。

これで提出。こんどはTLE。

結局、8も10も26も全部偶数なので、余りは26種類の半分しかありませんね。ということで、13で打ち切ったら無事AC。

ここまで、3WAを出しました。

よくよく考えると、各状態が2つに分かれるので、2^13ぐらいはかかりそうです。2^26だと少し厳しかったですね。

#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define reps(i,s,n) for(int i=s;i<n;++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

ll n;
ll dfs(ll a,ll b)
{
   ll num = n-10*a-8*b;
   if(num < 0||a>13||b>13) return (ll)1e18;
   if((num%26 == 0))
   {
       return a+b;
   }
   return min(dfs(a+1,b),dfs(a,b+1));
}
int main()
{
   cin >> n;
   cout << dfs(0,0) << endl;
   return 0;
}

E問題

いろいろ飛ばしてE問題を解きました。

提出数こそ少なかったものの、正答率が高かったので選びました。

数列を昇順に並べる時のコストを最小化します。ここで大事なのは移動回数ではなくコストです。

まず、本当に愚直に1を1番目、2を２番目とやりました。が全然ダメそう。なにがダメかというと、一気に動かすのと一個一個動かすのはコストは同じなので、他の数字も動かした方がお得な点です。一気に動かすと最適ではないです。

ということで、１個１個動かしました。このとき、入れ替える相手の数字が正しい位置よりも遠くなってしまう場合には困ってしまうので、その場合にはその次と入れ替えるようにしました（その次もダメな時はまたその次）。これを1、n、2、n-1、3, ...と左右交互に数字を動かすようにしました。

なんかこれが良さそう。これを実装したらACでした。

解答見たら、交互にやる必要はなさそう。

#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define reps(i,s,n) for(int i=s;i<n;++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main()
{
   int n;
   cin >> n;
   vector<int> p(n);
   rep(i,n) cin >> p[i];
   rep(i,n) --p[i];
   bool small = true;
   vector<P> ans;
   
   rep(i,n)
   {
       int m = i/2;
       if(!small) m = n-i/2-1;
       int idx = -1;
       rep(i,n)
       {
           if(p[i]==m) 
           {
               idx = i;
               break;
           }
       } 

       
       int bidx = idx;
       while(idx != m)
       {
           if(small)
           {
               --idx;
               if(p[idx]>=bidx)
               { 
                   swap(p[idx],p[bidx]);
                   ans.emplace_back(idx,bidx);
                   bidx = idx;
               }
           }
           else 
           {
               ++idx;
               if(p[idx]<=bidx) 
               {
                   swap(p[idx],p[bidx]);
                   ans.emplace_back(bidx,idx);
                   bidx = idx;
               }
           }
       }
       
       small = !small;
   }
   cout << ans.size() << endl;
   for(auto[a,b]:ans)cout << a+1 << " " << b+1<< endl;
   
   return 0;
}

あとがき

思ったよりも難しかったです。A問題でも苦戦しました。また、今回はA->Fの順番で難しいということもなかったので、「どの問題を解くべきか判断する」という楽しさを味わうことができました。こういうお楽しみコンテストいいですね。また、unratedのコンテストにも参加してみることとします。