98. 今日解いた問題（2022.04.08）

今日も仕事が忙しかったので軽いものを2つ。

ARC だからか、Diff にしてはやや難しい印象。どちらも発想問題でした。

問題一覧

• A - Permutation Grid (Diff: 350)
• B - Shift and Reverse (Diff: 753)

自分の解法など

A - Permutation Grid

問題文を読むと、どうも作れる盤面は 1 通りに定まるようです。どのようにして決定できるのか考えてみます。

例 1 を見て、自分でマス目を書いてどのように塗っていくか考えます。まず、 に対応する行・列は全て黒です。次に、 に対応する行・列は先ほどの操作で黒が 1 つ存在するので、残りのマス目は白で確定します。すると、 に対応する行・列は白が 1 つ存在するので、残りのマス目を黒く塗ればよいことがわかります。

…と、 のような順で塗っていけば確定できることがわかりました。

ただし、これを愚直に書くと なので間に合いません。そこで、マス目に何らかの法則性がないか考えます。操作がシステマチックなので、何らか見いだせそうです。よく見ると、 であるようなマス目 は黒であることが分かります。よって、わざわざ盤面を再現せずともこれだけ見ればよいことがわかりました。

計算量は です。

 B - Shift and Reverse 

ゴールから考えてみます。

たとえば、長さ の数列 を考えて、この 1 つ前の状態を考えます。それは の 2 つです。さらにもう 1 つ状態を戻すと、既に出てきたものは除いて です。さらに戻すと、 です。これ以上戻しても同じ状態しか出ないので、長さ 4 の数列で入力として与えられるのはこれらに限られます。

数列をじっくり観察しましょう。

• 0手
  • 
• 1手
  • 
  • 
• 2手
  • 
  • 
  • 
• 3手
  • 
  • 

観察の結果、以下のようなことに気付きます。

• 数列を前から順に見ていくと、 ずつ増える・減るのが基本で、どこかで から 、あるいは から へと循環する。
• 循環を考慮して、数列は昇順または降順になる。

…というわけで、 の場所と昇順・降順のパターンを考慮すると、実は状態数は しかないです。そのため、枝刈り BFS で解ける問題です…が、そこまで気付いておきながら何故か違う方法で解きました。

目標は が先頭にあり、かつ、昇順になっている状態です。そこで、以下のような戦略が有効そうだと分かります。

• なる を考えて、 であれば Reverse する

つまり、 を早く先頭に持ってきたいので、真ん中より右にいるならひっくり返した方が早いということです。

ただしこの考察は十分ではなく、元々の数列が昇順だった場合に Reverse 戦略を取ると、 まで を Shift させるだけではなく、もう一度 Shift した後さらに Reverse する必要があるため、元々降順だった場合と比べて 2 手多くかかります。よって、条件式も と変わります。

さらに、実はこれでも不十分で、長さ 5 の数列で考えれば分かるのですが、 かつ降順だった場合、Reverse から始めた方が手数が少なくなります。なぜなら、降順のまま Shift させると を末尾まで持っていく分 1 手余分にかかるからです。

結局、以下のようなコードで答えを出せました。 の場所を見つける必要があるため、計算量は です。

// idx は 1 の場所(1-indexed)
// isReverse は元の数列が降順なら true
int ans = 0;
int revIdx = n - idx + 1 + (isReverse ? 0 : 2);
if (idx > revIdx || (idx == revIdx && isReverse))
{
    ans = 1;
    idx = n - idx + 1;
    isReverse = !isReverse;
}

if (isReverse) ans += idx;
else ans += idx - 1;

if (isReverse) ans++;