ferinの競プロ帳

競プロについてのメモ

ARC091 E - LISDL

競技プログラミング AtCoder

問題ページ
E: LISDL - AtCoder Regular Contest 091 | AtCoder

考えたこと

  • 構築ゲーなのでとりあえず試す
  • 昇順、降順で(3,4,5,2,1)みたいに並べてみると A+B=N+1 なら簡単に構成できそう
  • Aに合わせてB=N+1-Aの列をとりあえず作ってみる
  • N=8,A=3 なら (6,7,8,5,4,3,2,1) になる
  • ここから減少列の長さを減らしたい
  • 減少列の部分を並べ替えればよさそう
  • いろいろ試すと (6,7,8,5,4,3,2,1) → (6,7,8,4,5,3,2,1) → (6,7,8,3,4,5,2,1) → (6,7,8,3,4,5,1,2) みたいになる気がする
  • 減少列を限界まで減らすと長さAの増加列を繰り返すみたいな列になる気がする
  • これより減少列の長さを減らせる場合があるのか考えても見つけられない
  • これから考えると n/A <= B <= n+1-A なら構成が存在してこれ以外だと-1
  • コンテスト時間が全然残ってない && 区間がやたらあり実装がつらい
  • がんばってこれを実装する
  • コンテスト終了間際に何とかサンプルを通せたので出したら落ちた（完）
  • twitterを見てると方針は合ってるっぽい
  • 実装を見直すと境界が1ずれていた…
  • 直して出すと通った

方針は合ってたのに実装ミスで落とすのかなしい
区間の境界がごちゃごちゃしてるときはもっとちゃんと確認しろ

ソースコード

#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n, a, b;
  cin >> n >> a >> b;

  if(n < a+b-1 || n > a*b) {
    cout << -1 << endl;
    return 0;
  }

  VI v;
  // (n-a, n]
  for(int i=n-a+1; i<=n; ++i) v.PB(i);

  // diffの分減少列を減らす必要がある
  int diff = n+1-a-b;
  FOR(i, 1, n/a) {
    // (n-(i+1)*a, n-i*a]
    // 昇順にする
    if(diff >= a-1) {
      for(int j=n-(i+1)*a+1; j<=n-i*a; ++j) v.PB(j);
      diff -= a-1;
    }
    else if(diff) {
      // (n-(i+1)*a, n-i*a-diff) [n-i*a-diff, n-i*a]
      for(int j=n-i*a-diff; j<=n-i*a; ++j) v.PB(j);
      for(int j=n-i*a-diff-1; j>n-(i+1)*a; --j) v.PB(j);
      diff = 0;
    }
    // 降順
    else {
      for(int j=n-i*a; j>n-(i+1)*a; --j) v.PB(j);
    }
  }

  if(diff) {
    // (0, n%a-diff-1] [n%a-diff, n%a]
    for(int i=n%a-diff; i<=n%a; ++i) v.PB(i);
    for(int i=n%a-diff-1; i>0; --i) v.PB(i);
  } else {
    for(int i=n%a; i>0; --i) v.PB(i);
  }

  for(int i: v) cout << i << " ";
  cout << endl;

  return 0;
}

ARC091 D - Remainder Reminder

競技プログラミング AtCoder

問題ページ D: Remainder Reminder - AtCoder Regular Contest 091 | AtCoder

考えたこと

  • a<=k-1だと存在しない
  • bがaより大きければ剰余の結果がaそのままになるので条件を満たす
  • b<=aで条件を満たすのが何個あるかを高速に知りたい
  • とりあえず実験する
0 1 1 1 1 1 1 1 1 1
0 0 2 2 2 2 2 2 2 2
0 1 0 3 3 3 3 3 3 3
0 0 1 0 4 4 4 4 4 4
0 1 2 1 0 5 5 5 5 5
0 0 0 2 1 0 6 6 6 6
0 1 1 3 2 1 0 7 7 7
0 0 2 0 3 2 1 0 8 8
0 1 0 1 4 3 2 1 0 9
0 0 1 2 0 4 3 2 1 0
  • 何も規則が見えない
  • 約数列挙とかある数の倍数なら何かないかとか迷走する
  • 30分経っても解けなくて実験を眺めてたら縦に見ると周期性があることに気づく
  • 冷静に考えると割る数固定すれば剰余に周期があるのはそれはそう
  • O(N)で解ける

存在しない規則をなぜかあると考えて無駄に時間を溶かした…
レートのためにもこれくらいはパッと通したい

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n, k;
  cin >> n >> k;

  if(k == 0) {
    cout << n*n << endl;
    return 0;
  }

  int ans = 0;
  FOR(i, 1, n+1) {
    if(i-1 >= k) {
      ans += n/i*(i-k);
      ans += max(0LL, (n%i) - k + 1);
    }
  }
  cout << ans << endl;
  return 0;
}

SRM693 div1 easy BiconnectedDiv1

競技プログラミング SRM

考えたこと

  • 二重連結グラフをよく知らなかったのでググる
  • 橋がないことと同値っぽい
  • 最小全域二重連結グラフみたいな問題
  • グラフの形がかなり特徴的
  • 頂点1,2が繋がるパスは 1-2,1-0-2,1-3-2 の3通りっぽい
  • どの頂点も次数が2以上あれば条件を満たしていそう
  • 頂点0と頂点n-1はそもそも次数2しかないので辺を削るのは不可能っぽい
  • 端から辺を削って行きたい
  • 1-2と1-3のどっちかを削ると頂点2,3に影響してみたいなことを考えると遷移がよくわからなくなる
  • 最小全域木っぽい解法がなにかないかと思う
  • 重いコストの辺から消せるなら消すみたいなのを書く
  • 何か手元で試してたらうまくいった
  • 他に何も思いつかないので投げたら落ちた
    -----解説を見た-----
  • dp[i] = (頂点iまでで消せる辺のコストの和の最大)
  • (i,i+1) を消すか (i,i+2) を消すか
  • (i,i+1) を消すなら 頂点i+1以降の辺で消せない辺みたいなのはなさそう
  • (i,i+2) を消すなら (i+1,i+2)(i+1,i+3) を消すのは不可能
  • O(1)で遷移ができる

遷移がわからなくて考察をやめた方針が正解っぽくてかなしい
ちょっと遷移が複雑になっただけで頭爆発するのやめたい
落ちた貪欲解は {0,6,3,7,0} {0,8,0,0} とかで落ちる

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

class BiconnectedDiv1 {
   public:
   int minimize(vector <int> w1, vector <int> w2)
  {
    int n = w1.size() + 1;
    ll sum = 0;
    REP(i, n-1) sum += w1[i];
    REP(i, n-2) sum += w2[i];

    ll dp[105] = {};
    FOR(i, 1, n-1) {
      chmax(dp[i+1], dp[i]+w1[i]);
      chmax(dp[i+2], dp[i]+w2[i]);
    }

    return sum - dp[n-2];
  }
};

codeforces #469 div2-C div1-A Zebras

競技プログラミング Codeforces

問題ページ
Problem - C - Codeforces

考えたこと

  • 0と1の数からつくる01列の数特定できない？みたいになるけどできない
  • 色々試してると前から貪欲に取ればいい気持ちになる
  • 前から貪欲するのになぜかO(n^2)の方法しか思いつかない
  • 括弧列みたいに+1/-1で累積和を取って途中でマイナスになったら0が足りないので不可能
  • 後ろの方の0が足りるかの判定がよくわからない
  • 判定できても構成がわからない
  • 1を元に010をつくって合成とか次の0,1の位置を覚えておくとか色々迷走する
  • 0,1が存在する位置をそれぞれsetでもっておくと次に取れる最も近い0,1の位置を二分探索でO(logN)で求められる
  • O(NlogN)で通せそうな気持ちになったので出すと通った

謎の迷走で遅解きになってしまってつらい
終了後にtwitterで0,1をそれぞれ上、下の矢印として考えて同じ高さのものをまとめて使うのを見た
とても頭がいいし括弧列の構成とかで割と汎用性がありそう

ソースコード

本番中に自分が出したO(NlogN)のコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

ll dp[200010];
signed main(void)
{
  string s;
  cin >> s;
  int n = s.size();

  if(s[0] == '1' || s.back() == '1') {
    cout << -1 << endl;
    return 0;
  }

  set<int> zero, one;
  dp[0] = 1;
  zero.insert(0);
  FOR(i, 1, n) {
    if(s[i] == '0') {
      dp[i] = dp[i-1] + 1;
      zero.insert(i);
    } else {
      dp[i] = dp[i-1] - 1;
      one.insert(i);
    }
    if(dp[i] < 0) {
      cout << -1 << endl;
      return 0;
    }
  }

  VVI ans;
  while(zero.size()) {
    bool turn = true;
    ll now = *zero.begin();
    zero.erase(zero.begin());
    VI tmp{now};
    while(true) {
      if(turn) {
        auto itr = one.upper_bound(now);
        if(itr == one.end()) break;
        tmp.PB(*itr);
        now = *itr;
        one.erase(itr);
      } else {
        auto itr = zero.upper_bound(now);
        if(itr == zero.end()) {
          cout << -1 << endl;
          return 0;
        }
        tmp.PB(*itr);
        now = *itr;
        zero.erase(itr);
      }
      turn = !turn;
    }
    ans.PB(tmp);
  }

  if(one.size()) {
    cout << -1 << endl;
    return 0;
  }

  cout << ans.size() << endl;
  REP(i, ans.size()) {
    cout << ans[i].size() << " ";
    REP(j, ans[i].size()) cout << ans[i][j]+1 << " ";
    cout << endl;
  }

  return 0;
}

O(N)の解法

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

VI dp[200010];
signed main(void)
{
  string s;
  cin >> s;
  int n = s.size();

  if(s[0]=='1' || s.back()=='1') {
    cout << -1 << endl;
    return 0;
  }

  ll now = 0;
  dp[now].PB(0);
  FOR(i, 1, n) {
    if(s[i]=='0') {
      if(s[i]==s[i-1]) now++;
    } else {
      if(s[i]==s[i-1]) now--;
    }
    if(now < 0) {
      cout << -1 << endl;
      return 0;
    }
    dp[now].PB(i);
  }

  int cnt = 0;
  REP(i, n) {
    if(dp[i].size() == 0) break;
    if(s[dp[i].back()] == '1') {
      cout << -1 << endl;
      return 0;
    }
    cnt++;
  }

  cout << cnt << endl;
  REP(i, cnt) {
    cout << dp[i].size() << " ";
    REP(j, dp[i].size()) cout << dp[i][j]+1 << " ";
    cout << endl;
  }

  return 0;
}

codeforces #469 div2-D div1-B A Leapfrog in the Array

競技プログラミング Codeforces

問題ページ
Problem - D - Codeforces

本番中は誤読で時間溶かして終了

解法

  • 操作を逆順にして考える
  • n=5のとき以下のようになる
15243
1 2435
1 2 354
1 2 3 45
1 2 3 4 5
  • もし最終状態で存在する位置から初期状態の位置を復元できれば答えが求められる
  • 移動元がどこか特定しそこに移動するのを繰り返したい
  • xが奇数ならそれ以上動きようがないので初期状態の位置のはず
  • xが偶数のときはどこが移動元か
  • 移動する距離に注目してみると4→2→1→0と半分ずつになっている
  • 実験すると移動する距離は半分ずつになっていきそうなことがわかる
  • 半分ずつになっていくので1クエリあたりO(logN)で求められそう
  • あとは最初の移動する距離がわかれば初期状態の位置を復元できそう
  • 最初の移動する距離は (nまでの距離) + (先に移動した数の分の距離) になる
  • これは (n-x) + x/2 で求められる

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n, q;
  cin >> n >> q;
  REP(i, q) {
    int x;
    cin >> x;
    int w = (n-x) + x/2;
    while(x%2==0) {
      x += w;
      w /= 2;
    }
    cout << (x+1)/2 << endl;
  }

  return 0;
}

SRM691 div1 easy Sunnygraphs

競技プログラミング SRM

考えたこと

  • 0,1につながってない頂点はどう選ぼうが全く影響しなさそうなので2^(この頂点数)を掛けるとよさそう
  • 実際は無向辺だけど有向辺として考えた方がよさそう
  • サイクルの部分はどう選択しようが必ず連結性が保たれているっぽい
  • 0と1が連結かどうかで場合分け出来る気持ちになる
  • 0と1が連結でなければ頂点Nを介してつなげるしかない
  • その頂点を選ぶと頂点0とつながるような頂点から最低1頂点は選ばないとだめそう
  • この頂点群は有向辺で考えたときに頂点0からたどり着けるような頂点になる
  • 頂点1についても同じ
  • つまり0と1が連結でないときは2^(頂点0からたどり着ける頂点数)*2^(頂点1からたどり着ける頂点数)でよさそう
  • 問題は0,1がそもそもつながっているとき
  • 頂点Nを介してつなげるとき(1)とそもそもつながってる経路でつなげるとき(2)で分ける
  • (2)のときはサイクルの部分と経路に関係ない部分を自由に選択できるみたいな気持ちになる
  • (2)でサイクルの部分を選んだら頂点Nを介してつながってるしだめでは？とか(1)のパターン考えてたら複雑すぎて頭が爆発する
  • (1)と(2)で重複して数え上げてるパターンがありそうな気持ちになったりとにかく複雑すぎる
  • もうちょっと簡略化して整理したい気持ちになるがよくわからない
    -----解説を見た-----
  • そもそも連結でない場合は合ってる
  • 連結なときは5パターンに分類されるのでそれぞれ数え上げる

数パターンに分類して算数をする系、分類するパートで複雑すぎて思考が止まってる気がしてきた
もうちょっと気をつけて整理しましょう

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

ll d[55][55];
class Sunnygraphs {
   public:
   long long count(vector <int> A)
  {
    int n = A.size();
    REP(i, n) REP(j, n) d[i][j] = i==j?0:INF;
    REP(i, n) d[i][A[i]] = 1;
    REP(k, n) REP(i, n) REP(j, n) chmin(d[i][j], d[i][k] + d[k][j]);

    // 0,1から到達不可能な頂点
    ll a = 0;
    REP(i, n) if(d[0][i] >= INF && d[1][i] >= INF) a++;
    // 0から到達可能
    ll b = 0;
    REP(i, n) if(d[0][i] < INF && d[1][i] >= INF) b++;
    // 1から到達可能
    ll c = 0;
    REP(i, n) if(d[0][i] >= INF && d[1][i] < INF) c++;
    // 両方から到達可能
    ll e = 0;
    REP(i, n) if(d[0][i] < INF && d[1][i] < INF) e++;

    // 0,1が非連結
    if(e == 0) return (1LL<<a)*((1LL<<b)-1)*((1LL<<c)-1);
    // 0,1が連結
    ll ret = 0;
    ret += ((1LL<<b)-1)*((1LL<<c)-1)*(1LL<<(a+e));
    ret += ((1LL<<b)-1)*((1LL<<e)-1)*(1LL<<a);
    ret += ((1LL<<c)-1)*((1LL<<e)-1)*(1LL<<a);
    ret += ((1LL<<e)-1)*(1LL<<a);
    ret += (1LL<<a);
    return ret;
  }
};

SRM689 div1 easy ColorfulGarden

競技プログラミング SRM

考えたこと

  • 互い違いにおいていくのが一色を多く置く方法っぽい
  • 一色でn個より多くあるのを条件を満たすようには置けない
  • 逆に全部n個以下なら適当に互い違いにおいていくだけで構成できる

割とすぐ思いつけた

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

ll cnt[30];
class ColorfulGarden {
   public:
   vector <string> rearrange(vector <string> g)
  {
    ll n = g[0].size();
    memset(cnt, 0, sizeof(cnt));
    REP(i, 2) REP(j, n) cnt[g[i][j]-'a']++;

    vector<PII> p;
    REP(i, 26) {
      if(cnt[i] > n) return {};
      p.PB({cnt[i], i});
    }
    sort(ALL(p), greater<PII>());

    vector<PII> v;
    int turn = 0;
    REP(i, n) {v.PB({turn, i}); turn = !turn;}
    turn = 1;
    REP(i, n) {v.PB({turn, i}); turn = !turn;}

    vector<string> ret(2, string(n, 'a'));
    int idx = 0;
    REP(i, 26) {
      while(p[i].first) {
        ret[v[idx].first][v[idx].second] = (char)(p[i].second+'a');
        p[i].first--; idx++;
      }
    }

    return ret;
  }
};