2025-06-22

文字列swap系問題をグラフで解く

ABC264-D問題 "redocta".swap(i,i+1)

この問題は文字列の操作の問題なのにグラフの考え方を使うらしく，

よくわからなかったので思考整理も兼ねて記事を書きます．

問題文

atcoder の並べ替えである文字列 $S$ が与えられます。

この文字列 $S$ に対して以下の操作を $0$ 回以上行います。

・ $S$ 中の隣接する $2$ 文字を選び、入れ替える。

$S$ をatcoderにするために必要な最小の操作回数を求めてください。

制約

$S$ は atcoder の並べ替えである文字列

出典

atcoder.jp

考察

基本的なアイデアは， $S$ を最初にqueueに入れ， $S$ を基準として $i$ 文字目と $i+1$ 文字目( $1 \leq i \leq S$ の文字数-1)を入れ替えた文字列をqueueに入れ直します．

ただし，一度見た文字列をqueueに入れると無限ループするので，確認済みかどうかのフラグとしてmapを利用することにします．

なお，mapの値はコストとしたいため，未探索かどうかの判定は，値が1以上かどうかなどで判定するといいと思います．

例を挙げます．

$S=$ tcaの場合，上記アルゴリズムによるグラフの遷移は以下の図の通りです．

水色のノードは未探索の文字列でqueueに入れるもの，ノードの左の数字はコスト，

灰色のノードは探索済みのノードで，queueに入れる必要のない文字列です．

「tac」の場合は，コスト $3$ でもたどり着けますが，コスト $1$ の方が最適であることが分かります．

計算時間について，上記方法の場合， $7! = 5040$ 通りの探索が発生し，

実行時間制限も問題ないことが分かります．

以下，私の書いたコード(の一部)です．

string atcoder = "atcoder";

int main(){
  string S;
  cin >> S;
  //

  // 文字の置換パターンをキューで管理
  queue<string> q;
  // 文字の置換パターンに対するコストおよび
  // 探索済みフラグをマップで管理
  map<string, ll> m;

  // キューの初期値は入力値S
  q.push(S);

  // キューが空でない間ループ
  while(!q.empty()){
    // キューの先頭を保存してポップ
    string r = q.front();
    q.pop();

    // 
    for(int i = 0, i < atcoder.size() - 1; i++){
      string r2 = r;
      // 文字列rのi文字目とi+1文字目を入れ替え
      swap(r2[i], r2[i+1]);
      // 見探索であるかの確認
      if(!m.count(r2)){
        // プッシュ
        q.push(r2);
        // コストを計算してマップに代入
        m[r2] = m[r] + 1;
      }
    } // for
  } // while

  // 答え
  cout << m[atcoder] << endl;


  return 0;
}

2022-01-23

ABC236

結果

A $\ 01:26$

B $\ 04:46$

C $\ 07:21$

ノーペナ $3$ 完で，パフォは $994$ ，rating変動は $+16$ で $838 \to 854$ でした．

考察

A問題

私はtmpにb文字目を一時退避してa文字目と入れ替えましたが，stringの中でswapって使えるんですかね．

調べる時間の方が勿体なかったのでswapを実装しました．

B問題

$4N-1$ 枚のカード全てを見て，書かれている数字をカウントします．

$1$ ～ $N$ のうち，カウントされた回数が $3$ である数字が答えです．

(答え以外の数字は全部カウントが $4$ になります．)

C問題

setなどを使い，急行列車が止まる駅を全て覚えておきます．

各 $S [ i ]$ が，上で覚えておいた停車駅に含まれていればYes，含まれていなければNoです．

要素数 $N$ のsetから要素を見つける最悪計算量は $O(logN$ なので間に合います．(調べて知りました．)

感想

Highest更新しましたー！

C問題までは簡単だったので，罠に引っかかってないか用心深く提出しましたが，普通に簡単だっただけでしたね．

D問題はqueueを使ってDFSっぽいことをしましたが，サンプルまでしか通らずACには至りませんでした．

2022-01-08

ABC234

結果

A $01 \ : 54$

B $05 \ : 23$

C $35 \ : 03$

D $82 \ : 29$

1WAの4完で，パフォは $746$ ，rating変動は $-10$ で $848 \to 838$ でした．

考察

A問題

関数を宣言して問題に忠実に出力計算式を書けばACです．

見間違えに気を付ける．

B問題

$i$ 個目の点( $1 \leq i \leq N$ )と $j$ 個目の点( $1 \leq j \leq N$ )で全探索をして，最大値を更新していきます．

このやり方だと，自分自身との距離とか，同じ点同士の距離計算を2回したりとか無駄が多いですが，面倒だし計算量的には変わらないのでこれでOK．

C問題

$K$ を2進数で表し， $1$ を $2$ で置き換えればACです．

0と2のみで構成される数字を小さい方から並べていくと，2進数で1ずつ加算していく計算をすることとほぼ同じことに気づけば簡単です．(私はすぐに気付きませんでしたが)

D問題

登場した数列を連想配列で保持しておきます．(大小関係を高速に保持したいため)

$P$ の先頭 $i$ 項のうち， $K$ 番目に大きい連想配列の場所をitとします(iteratorの意味)．初めに先頭 $K$ 項を連想配列に突っ込んでおくと，itの初期値は連想配列の先頭です．

順列の $K+1$ 番目以降はまずは連想配列に入れますが，それがitの値より大きければ $K$ 番目に大きい値は1つずれるので，itを1つ先に送ります．itの値より小さければ $K$ 番目に大きい値はそのままです．

感想

C問題で2ベキが絡みそうなことはすぐ気づけましたが，ACまではかなり時間がかかってしまったのが悔しいです．

D問題は凡ミスで20分無駄にしたのでもっと日々コードを書けという気持ちになりました....はい，書きます．

2021-12-19

ABC232

結果

A $\ 02 : 46$

B $\ 26 : 07$

C $\ 65 : 59$

D $\ 91 : 19$

$4$ WAの $4$ 完で，パフォは $840$ ，rating変動は $\pm 0$ で $848 \to 848$ でした．

考察

A問題

1, 3文字目をintに変換して普通にかけ算します．

久しぶりだったので，「intに直す関数なんだっけ」ってなったり，

「いや，-'0'でいいのか．あれ，+'0'だっけどっち？」

みたいな初心者みたいなことをしていて3分ぐらいかかりました．

B問題

~~これはなんでACしたかよくわからん．~~

とりあえずよくわからん解法を載せます．ACしていない人は読まないでください．

初期で一致していないindexのところだけ行き先を記憶しておきます．行き先が2つ以上あったらNoです．(pp→abみたいに)

あとは，行き先の行き先が自分自身だったらNoです．(ab→baだと，aの行き先はbで，bの行き先はaなのでNo)

~~これでなぜかACしたけど妥当性は完全に不明．~~

2021/12/20追記

問題をすごく読み違えていたことに気づきました．

ACしたのが奇跡です．

C問題

順列全探索です．

$0$ ～ $N-1$ までの数列 $P$ を，全ての順列で回しながら以下を行います．

1.青木くんのおもちゃの繋がり方をグラフとして表現

2.全てのひも $i$ に対して，青木くんのボール $P_{A_{i} }$ と繋がっているボールの中に青木くんのボール $P_{B_{i}}$ は存在するかを確認する．

全てのひもで2.が成り立っていれば，その数列 $P$ が答えです．

ちなみに，頂点を0-indexedしていなかったので2WAしました．

D問題

グリッドのBFSです．

各地点までの距離をINFとかで初期化して，BFSをするだけです．

私はDPっぽい条件式で距離を更新しようとしていましたが，最短経路が常に出るので全く意味のない事をしていました．

vectorとかqueueってどうやって使うんだっけとなりました．

感想

1か月ほぼ全く競プロを触っていなかったので，色々忘れていてかなり焦っておりました．振り返ってみると，全体的に意味不明なコードを書いていたような気がします()

実は，B問題が終わった時点で下位5%ぐらいにいたので辞めちゃおうかと思いましたが，最後までやってよかったです．久しぶりのABC，楽しかった．

そういえば，rating変動0って初めてかも

2021-11-13

ABC227

結果

A $\ 11 : 37$

B $\ 15 : 54$

C $\ 50 : 20$

ノーペナ $3$ 完で，パフォは $1052$ ，rating変動は $+25$ で $823 \to 848$ でした．

考察

A問題

人 $A$ から $K$ 枚配った先，つまり $K+A$ を考えます．

これが $N$ で割り切れれば $K+A$ を出力し，割り切れなければ $(K+A) \% N$ を出力してAC．

( $X \% Y$ は， $X$ を $Y$ で割った剰余)

色々パニックになっていたのでコードはもっと汚いですし，10分もかかりました．

B問題

全探索します．以上．

変数は全て正の整数で， $4ab$ があるので $1 \leq a \leq 300$ ， $1 \leq b \leq 300$ で全探索しました．

まぁ多い分には適当でもいいので...

C問題

$A \leq B \leq C$ なので， $A$ の範囲は $1 \leq A \leq \sqrt[3]{N}$ でOKです．

(言い換えると， $A^{3} \leq N$ となる $1$ 以上の整数)

さらに， $B$ の範囲は $A$ から始めて， $AB^{2} \leq N$ が成り立つ間です．

計算量評価はかなーりざっくりですが， $A$ のループは $\sqrt[3]{N}$ なので最悪 $10^{3}$ から $10^{4}$ ぐらいで， $B$ のループも(多分)同様に $10^{3}$ から $10^{4}$ ぐらいです．

まぁ $B$ のループの方が $A$ のループより若干少ないのかなーって気持ちはあります．

どっちにしろ最悪の場合でも $10^{8}$ の処理で，中での処理は軽いので間に合うかなーってかんじで提出したらACしました．

$C$ の計算ですが， $(N/AB) - (B-1)$ で個数が出てきます．

$B \leq C$ なので， $B-1$ を引いておく必要があります．

感想

コンテスト自体は少しずつ参加していましたが，~~めんどくさくて~~時間がなくて記事は書いていませんでした．

highest更新できてやったー！

2021-09-23

共通テストの問題を深さ優先探索してみた

競プロとは直接関係ありませんが，競プロで得た知識のDFS(深さ優先探索)を使って問題を解きました．

本記事では言語はC++を使っていますが，一応他の言語を使った人でも読めるように解説したつもりです．

ちなみに，初めて紙面上で解いた時はDFSではなくBFS(幅優先探索)で私は解きました．

手作業ならDFSは大変なので...

BFSの実装は綺麗なステップ数の保持の仕方がよくわかりませんでした(おい)

BFSで実装した人はぜひ議論しましょう．

問題設定

以下，共通テストの数学IA，題4問より抜粋です．

第4問

円周上に15個の点 $P_0, P_1, \cdots , P_{14}$ が反時計回りに順に並んでいる．

最初，点 $P_0$ に石がある．

さいころを投げて偶数の目が出たら石を反時計回りに5個先の点に移動させ，奇数の目が出たら時計回りに3個先の点に移動させる．

この操作を繰り返す．

例えば，石が点 $P_5$ にあるとき，さいころを投げて6の目が出たら石を点 $P_{10}$ に移動させる．

次に，5の目が出たら石を点 $P_7$ に移動させる．

<中略>

(4)点 $P_1, P_2, \cdots, P_{14}$ の中から点を1つ選び，点 $P_0$ にある石をさいころを何回か投げてその点に移動させる．

そのために必要となる，さいころを投げる最小回数を考える．

例えば，さいころを1回だけ投げて点 $P_0$ にある石を点 $P_2$ に移動させることはできないが，さいころを2回投げて偶数の目と奇数の目が1回ずつ出れば，点 $P_0$ にある石を点 $P_2$ へ移動させることができる．

したがって，点 $P_2$ を選んだときには，この最小回数は2回である．

点 $P_1, P_2, \cdots, P_{14}$ のうち，この最小回数が最も大きいのは，点シであり，その最小回数はスである．

(出典：独立行政法人大学入試センター共通テスト数学IAより)

考察

以下，反時計回りの $n$ 個先への移動を $+n$ ，時計回りの $n$ 個先への移動を $-n$ で表します．

まず，点 $P_0$ から一手で行ける点は， $+5$ の移動による $P_5$ と， $-3$ の移動による $P_{12}$ の2つです．

さらに，点 $P_5, P_{12}$ からそれぞれ $+5$ の移動と $-3$ の移動を考えることで，点 $P_0$ から二手で行ける点がわかります．

点 $P_5$ からは点 $P_{10}, P_2$ に，点 $P_{12}$ からは点 $P_2, P_9$ に一手で行けるので，点 $P_0$ から二手で行ける点は点 $P_2, P_9, P_{10}$ の3つです．

これを繰り返すことで点 $P_0$ からの最小移動ステップ数が求まります．

私はこれをDFS(幅優先探索)で実装しました．

イメージ図は下のようになります．

f:id:chankilu23:20210125132731j:plain

左に伸びる辺は $+5$ の移動を，右に伸びる辺は $-3$ の移動を表しています．

色の説明をします．

青の点は，その点から $+5$ の移動と $-3$ の移動をするために再帰的に操作をする点です．

赤の点は，現在のステップ数よりも最適なステップ数が既に見つかっているため，再帰をせず次の点の探索に移るという点です．

緑の点は，再帰呼び出しをしますが，後の方でより最適なステップ数が見つかるので図では省略しているという点です．(なので，実際の図はもっと大きくなります)

これをコードで書いていきます．

変数として以下を宣言します．

vector<int> step(15, 20);

記法の意味ですが，step[15]というint型の配列の要素を全て20で初期化する，と捉えてください．

vectorという型で宣言していますが，普通の配列だと思ってもらってもこの記事では差し支えありません．

step $[ i$ ]には，点 $P_0$ から点 $P_i$ に移動する最小ステップ数を更新しながら格納していきます．

それではDFSの中身を見ていきます．

void dfs(int current_point, int height){
  int next_point1 = (current_point + 5)%15;
  int next_point2 = (current_point - 3 + 15)%15;

  if(height < step[next_point1]){
    step[next_point1] = height;
    dfs(next_point1, height+1);
  }
  if(height < step[next_point2]){
    step[next_point2] = height;
    dfs(next_point2, height+1);
  }
}

引数は，現在見ている点current_point，現在の点のステップ数に+1をした値のheight，の2つです．

1行目と2行目で次に訪れる点を計算します．15個の点は円上に並んでおり，点 $P_0$ と点 $P_{14}$ は互いに移り合うので，15で割った余りの考え方で計算できます．

負数になることも考慮して， $-3$ の移動では15を足してからmod 15をします．

その下の2つのif文は同じことをしているので1つ目だけ説明します．

移動が $+5, -3$ の先の点で同じことをするので再帰をするのですが，再帰をする条件としては，現在のステップ数heightが，移動先の点のその時点での最適ステップ数より小さいことです．

再帰をするとステップ数は1増えるので，移動先の点のその時点での最適ステップ数がheightより小さければ再帰をする意味がないです．

それでは最後に実行結果を以下に示します．

これを見ると，点 $P_0$ からの最小ステップ数は点 $P_{13}$ が一番大きいことがわかります．