第5回 ドワンゴからの挑戦状 予選 C - k-DMC

問題ページ

解法

• 3つ組のうちaとcを動かしていくことを考える
• aがcを追い抜かすことはない
• [a, c]についてs[a]=='D'であれば答えに sum(区間[l,i]のMの数) (a<=i<=c, s[i]=='C') を加算する
• 現在の区間についてMの数(=mnum)、Cの数(=cnum)、DMC(=now)の数を持って区間を1ずつ右にずらしていけばよさそう
• 区間をずらすことでどのように変化するのか考える
  • 区間をずらして区間に'M'が追加された場合 → mnum++
  • 区間に'C'が追加された場合 → now += mnum, cnum++
  • 区間から'M'が抜けた場合 → mnum--, now -= cnum
  • 区間から'C'が抜けた場合 → cnum--
• 以上のように遷移させつつ、s[a]=='D'であれば答えにnowを加算するとする
• 各クエリについてO(N)で全体でO(NQ)で解くことができる

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
// #define int ll
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()
 
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<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) { 
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }
 
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}
 
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const int MOD = 1000000007;

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

  ll n;
  string s;
  cin >> n >> s;
  ll q;
  cin >> q;
  vector<ll> k(q);
  REP(i, q) cin >> k[i];

  REP(i, q) {
    ll ret = 0;
    ll mnum = 0, cnum = 0, now = 0;
    REP(j, k[i]) {
      if(s[j] == 'M') mnum++;
      else if(s[j] == 'C') cnum++, now += mnum;
    }
    for(ll l=0, r=k[i]-1; l<n; ++l, ++r) {
      if(s[l]!='D') {
        if(s[l]=='M') mnum--, now -= cnum;
        else if(s[l]=='C') cnum--;
        if(r+1 < n) {
          if(s[r+1] == 'M') mnum++;
          else if(s[r+1] == 'C') cnum++, now += mnum;
        }
        continue;
      }

      ret += now;

      if(r+1 < n) {
        if(s[r+1] == 'M') mnum++;
        else if(s[r+1] == 'C') cnum++, now += mnum;
      }
    }
    
    cout << ret << endl;
  }

  return 0;
}

第5回 ドワンゴからの挑戦状 予選 B - Sum AND Subarrays

問題ページ

考えたこと

• 上のbitから順番に決めていく
• 2^i > 2^i-1 + … + 2^0 より上のbitから貪欲に決めてよいはず
• 2^i の位が1となっている区間がk個以上存在した場合、2^iを1とできる
• 一旦1と決めた位が合った場合、その下の位で使える区間が限定される
• iビット目までに取りうる最大値をmaskとすると mask | 1LL<<i と ANDを取っても変わらない区間の数を数えればよい
• 判定にO(N^2)でbitはO(logNA)桁あるのでO(N^2logNA)で解けた

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
// #define int ll
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()
 
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<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) { 
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }
 
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}
 
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const int MOD = 1000000007;

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

  ll n, k;
  cin >> n >> k;
  vector<ll> a(n);
  REP(i, n) cin >> a[i];

  vector<ll> b(a);
  FOR(i, 1, n) b[i] += b[i-1];

  vector<ll> v;
  REP(i, n) FOR(j, i, n) {
    v.push_back(b[j] - (i==0?0:b[i-1]));
  }
  ll m = v.size();

  ll mask = 0;
  for(ll i=40; i>=0; --i) {
    mask |= 1LL<<i;
    ll cnt = 0;
    REP(j, m) {
      if((v[j]&mask) == mask) cnt++;
    }
    if(cnt < k) mask ^= 1LL<<i;
  }
  cout << mask << endl;

  return 0;
}

ARC086 E - Smuggling Marbles

問題ページ

解法

木DPを行う。dp[i][j][k]=(j回動かしたときに頂点iにk個(=0,1か2個以上)ビー玉が存在するような初期配置の数) と定義してDPをする。頂点iの子をc_0とc_1とする。これらの子の情報dp[c_0]とdp[c_1]をマージする方法について考える。j=0~d(頂点iの高さ)について以下の計算を行う。これらが1回以上移動したときの組み合わせ数の計算結果となる。1回も動かさないときの組み合わせ数のdp[i][j][0]=dp[i][j][1]=1, dp[i][j][2]=0を先頭に挿入することで頂点iについての結果を得ることができる。

• dp[i][j][0] = dp[c_0][j][0] * dp[c_1][j][0]
• dp[i][j][1] = dp[c_0][j][1] * dp[c_1][j][0] + dp[c_0][j][0] * dp[c_0][j][1]
• dp[i][j][2] = dp[c_0][j][2] * (dp[c_1][j][0] + dp[c_1][j][1] + dp[c_1][j][0]) + dp[c_0][j][1] * (dp[c_1][j][1] + dp[c_1][j][2]) + dp[c_0][j][0] * dp[c_1][j][2]

移動した後に頂点に2個以上存在している場合はそのビー玉を取り除く。したがって上記の処理を行ったあとに dp[i][j][0] += dp[i][j][2], dp[i][j][2] = 0 とする。
このマージを普通に書くと遷移にO(N)かかり全体でO(N²)かかってTLEしてしまう。この高速化にデータ構造をマージする一般的テクを用いる。子c_0とc_1をマージするときにサイズが小さい方から大きい方へ向かってマージするように書くとマージテクの要領でO(NlogN)のように考えられる。公式解説にあるようにLCAを考えるとO(N)となっていることがわかる。実装上の注意点として2個以上存在しているビー玉を取り除く場所でループする範囲を必要最小限となるように取らないと、その部分で計算量が増えてTLEしてしまうので要注意。

2乗の木DPみたいな雰囲気を感じる
CSAにuniform treeという類題があります

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;
 
#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()
 
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<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) { 
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }
 
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}
 
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;

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

  ll n;
  cin >> n;
  ++n;
  vector<vector<ll>> g(n);
  REP(i, n-1) {
    ll p;
    cin >> p;
    g[p].push_back(i+1);
  }

  vector<ll> depth(n);
  function<void(ll,ll)> dep = [&](ll v, ll d) {
    depth[d]++;
    for(auto to: g[v]) {
      dep(to, d+1);
    }
  };

  struct node {
    // 頂点に0,1,2個ビー玉が存在するときについて
    ll x, y, z;
    node() {}
    node(ll x, ll y, ll z) : x(x), y(y), z(z) {}
    // dpの情報のマージ
    node plus(node n) {
      ll nx = x*n.x % MOD;
      ll ny = (y*n.x % MOD + x*n.y % MOD) % MOD;
      ll nz = (z*(n.x+n.y+n.z) % MOD + y*(n.y+n.z) % MOD + x*n.z % MOD) % MOD;
      return node(nx, ny, nz);
    }
  };

  function<deque<node>(ll)> dfs = [&](ll v) {
    // ret[i] = (頂点vでi回移動したときの情報)
    deque<node> ret;
    ll sz = 0;
    for(auto to: g[v]) {
      auto dq = dfs(to);
      if(ret.size() < dq.size()) swap(ret, dq);
      // dq -> retへマージ
      REP(i, dq.size()) ret[i] = ret[i].plus(dq[i]);
      chmax(sz, (ll)dq.size());
    }
    // ret.size()まで回すのではなくmax(dq.size())までに抑える
    REP(i, sz) {
      (ret[i].x += ret[i].z) %= MOD;
      ret[i].z = 0;
    }
    ret.push_front(node(1, 1, 0));
    return ret;
  };

  dep(0, 0);
  auto ret = dfs(0);

  vector<ll> pow2(n+1);
  pow2[0] = 1;
  FOR(i, 1, n+1) pow2[i] = pow2[i-1] * 2 % MOD;

  ll d = 0, ans = 0;
  for(auto i: ret) (ans += i.y * pow2[n - depth[d++]] % MOD) %= MOD;
  cout << ans << endl;

  return 0;
}

Mail.Ru Cup 2018 Round 2 C. Lucky Days

問題ページ

解法

g=gcd(ta,tb)とする。各区間についてgずらすことが可能である。la, lbを両方0に近づけるあたりに最適な区間がある。なので0に近づけた辺りをある程度探索すれば答えが求まる。

[la, ra] と [lb, rb] の共通部分はmax(0, min(ra,rb)-max(la,lb) + 1) と簡潔に書けるので知っておくと便利
la, raをlb, rbに合わせてあとはgずらしていくみたいなのを書いたらバグらせた

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
#define int ll
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()
 
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<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) { 
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const int MOD = 1000000007;

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

  ll la, ra, ta, lb, rb, tb;
  cin >> la >> ra >> ta;
  cin >> lb >> rb >> tb;

  ll g = __gcd(ta, tb);
  ra -= la / g * g;
  la -= la / g * g;
  rb -= lb / g * g;
  lb -= lb / g * g;

  ll ret = 0;
  for(ll i=-1000; i<=1000; ++i) for(ll j=-1000; j<=1000; ++j) {
    ll x = max(la+i*g, lb+j*g);
    ll y = min(ra+i*g, rb+j*g);
    chmax(ret, max(0LL,y-x+1));
  }
  cout << ret << endl;

  return 0;
}

Codeforces Round #523 (Div. 2)

問題ページ

考えたこと

• 区間スケジューリングっぽい
• DPができる気がしないので貪欲を考える
• 区間スケジューリングでは最後に仕事をした時刻を1つ持てばいいが今回は複数ある
• あるTV番組[l,r]があったとき、前に見たTV番組のうち終端がl未満で最大の区間につなげるのが最も得をする
• 終端をsetで管理しておいて、区間の始点について昇順で区間を見ていきつなげるのが得をするか判定する
• つなげるべきであればsetの中身を書き換え、つなげない方が得であればsetに追加するという処理を繰り返す
• 通らなくて悩んでいたが冷静に考えてsetじゃなくてmultisetじゃないとだめ
• multisetにすると通った

終点ソートを書いたあとに始点ソートに書き換えたので実装が冗長になっている

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
#define int ll
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()
 
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<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) { 
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const int MOD = 1000000007;

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

  ll n, x, y;
  cin >> n >> x >> y;
  vector<PII> v(n);
  REP(i, n) cin >> v[i].second >> v[i].first;

  sort(ALL(v), [](PII l, PII r){
    if(l.second == r.second) return l.first < r.first;
    return l.second < r.second;
  });
  ll ret = 0;
  multiset<ll> last;
  REP(i, n) {
    // v[i].second 未満で最大のlast
    auto itr = last.lower_bound(v[i].second);
    if(itr == last.begin()) {
      last.insert(v[i].first);
      ret += x + y * (v[i].first - v[i].second);
      ret %= MOD;
      continue;
    }
    itr--;
    ll p = *itr;
    if(x + (v[i].first - v[i].second)*y < y * (v[i].first - p)) {
      ret += x + (v[i].first - v[i].second)*y;
      ret %= MOD;
      last.insert(v[i].first);
    } else {
      ret += (v[i].first - p)*y;
      ret %= MOD;
      last.erase(itr);
      last.insert(v[i].first);
    }
  }

  cout << ret << endl;

  return 0;
}

Codeforces Round #520 (Div. 2) D. Fun with Integers

問題ページ

問題概要

次の条件を満たすとき整数aから整数b(2<=|a|,|b|<=n)に変換することができる。
(条件) |x| > 1 となる整数xについてax = b もしくは bx = a を満たすものが存在する。a->b、b->aの変換を以前に行っていない。
この変換をすると|x|点の得点をもらうことができる。任意の整数から変換をはじめることができるとする。得点の合計を最大化しろ。

考えたこと

• とりあえずサンプルを見てどのように変換するのか考える
• sample1から互いに素でない2数(x,y)があると x -> y -> -x -> -y -> x と4回変換できることがわかる
• sample2のn=6のときに互いに素でない2数は(2,4)(2,6)(3,6)の3つ
• これら全てについて4回変換つなげないと28点にはならない
• 全てに共通する数がないので単純に3つつなげることはできない
• 単純につなげるのではなく途中に挿入すると考える
• 2 → 6 → -2 → -6 → 2 と 6 → 3 → -6 → -3 → 6 とあったときに最初の変換に現れた6を置き換える
• 2 → 6 → 3 → -6 → -3 → 6 → -2 → -6 → 2 とできる
• 4回の変換では元の数に戻ってくるのでこの置き換えを繰り返せば全部繋げられそう
• 互いに素な組として (2, 4)(2, 6)…(2, n) が存在しているはずなので2数のどちらかに偶数がでてくれば必ず繋げられる
• 両方奇数の2数があったとしても (3,6)(3,9) のように前に偶数を含む2数の組がでてきているので片方の3を置き換えれば繋げられる
• 2数の片側をiで固定したとき、もう片方の数はn/i-1通り
• n/i-1通り4i点 の得点が入る
• 各iについて計算するとO(N)で求まる

サンプルがとても優しい

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;
 
#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()
 
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<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) { 
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }
 
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}
 
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const int MOD = 998244353;

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

  ll n;
  cin >> n;

  ll ret = 0;
  FOR(i, 2, n) {
    ll tmp = n/i - 1;
    ret += tmp * 4 * i;
  }
  cout << ret << endl;

  return 0;
}

Technocup 2019 - Elimination Round 2 D. Minimum path

問題ページ

考えたこと

• 辞書順最小なので前から貪欲に取ることを考える
• 文字列の最初の方で交換可能でaでないものがあったらaに変えたほうが確実に良い
• 答えの文字列はaa…aabcdaefのように接頭辞にaが連続している
• 接頭辞のaが何個か考える
• 二次元グリッド上を左上からたどったときにa以外を通った回数がK回以下のマスを求める
• これはdijkstra等でできる
• 条件を満たしているマス(y,x)のうちmax(y+x+1)が接頭辞のaの個数になる
• 残りのマスは辞書順で小さいものに貪欲に遷移していけばよい
• 辞書順で最小のマスは複数存在する可能性があるのでsetを使って辿りうるマスの集合を持ち探索する
• 交換回数が0回のとき、接頭辞にaが来ないときがあるのに注意

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
// #define int ll
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()
 
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<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) { 
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }
 
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}
 
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const int MOD = 1000000007;

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

  ll n, k;
  cin >> n >> k;
  vector<string> v(n);
  REP(i, n) cin >> v[i];

  // 左上から辿るのにa以外のマスを通る回数
  auto d = make_v<ll>(n,n);
  fill_v(d, INF);
  d[0][0] = (v[0][0]=='a'?0:1);
  REP(i, n) REP(j, n) {
    REP(k, 2) {
      ll nx = j + dx[k], ny = i + dy[k];
      if(!IN(0LL,n,nx) || !IN(0LL,n,ny)) continue;
      chmin(d[ny][nx], d[i][j] + (v[ny][nx]=='a'?0:1));
    }
  }
  // 接頭辞に何個aが来るか
  ll ma = -1;
  set<PII> cur, nxt;
  REP(i, n) REP(j, n) {
    if(d[i][j]<=k) {
      if(i+j > ma) {
        ma = i+j;
        cur.clear();
        cur.insert({j, i});
      } else if(i+j == ma) {
        cur.insert({j, i});
      }
    }
  }
  string ans(ma+1, 'a');
  if(ma==-1) {
    ans = v[0][0];
    cur.insert({0, 0});
  }
  // 貪欲に遷移
  while(1) {
    char mi = 'z'+1;
    for(auto i: cur) {
      REP(j, 2) {
        ll nx = i.first + dx[j], ny = i.second + dy[j];
        if(!IN(0LL, n, nx) || !IN(0LL, n, ny)) continue;
        if(v[ny][nx] < mi) {
          mi = v[ny][nx];
          nxt.clear();
          nxt.insert({nx, ny});
        } else if(v[ny][nx] == mi) {
          nxt.insert({nx, ny});
        }
      }
    }
    if(nxt.size() == 0) break;
    ans += v[(*nxt.begin()).second][(*nxt.begin()).first];
    swap(cur, nxt);
    nxt.clear();
  }

  cout << ans << endl;

  return 0;
}