Vercel LogoMagicode
0

ABC232 解説 (A問題~C問題)

6 min read

こんにちは, こんばんは. Ruteです.

当記事は, ABC232の解説記事となっております. A問題~C問題までの解説を行います.
動画による解説は私のYouTubeチャンネルの動画よりご確認下さい.

問題問題名Difficulty
AQQ solver9
BCaesar Cipher82
CGraph Isomorphism685
ABC232 A問題 QQ solver
問題へのリンク

この問題は, axbの形式によって成り立っている文字列SSが与えられるので,a×ba×bの値を出力する, という問題でした.

主に2つの解法がありますので, 順番に説明します.

解法1 S.split("x")を使う解法

python のメソッド 文字列A.split("文字列B")では, 文字列Aの文字列に対し, 文字列Bで区切った場合の分割を, リストにして取得することが可能です.

例: "3.14".split(".") = ['3', '14']

今回の問題ではまさにこの関数を利用することが出来ます.

S.input("x")を用いることにより, Sをxで区切った文字列のリストを取得出来ます.

あとは, この1番目の要素と2番目の要素の積を出力すれば良いのですが, リストでは各要素が文字列型となっているため, 整数型に直す必要があることに気をつけて下さい.

[ ]

解法2 S.split("x")を使わない解法

実は, SSの長さは必ず33であることから, 単純に文字列を受け取り1文字目と3文字目の積を計算して出力することでも同じ処理が可能です.

[ ]

この問題は, 文字列処理の基本的な問題で, 最近のABCでは易しめであると感じました. splitというメソッドは, 文字列を分解するときに利用するので, 覚えておきましょう.

ABC232 B問題 Caesar Cipher
問題へのリンク

解説

問題名の英訳「シーザー暗号」は有名な暗号形式の一種です.

さて, この問題の目的は
SSの各文字を非負整数回操作してTTに出来るかを判定できるようにする というものになります.

例えば, 英小文字が"a"から数えて何番目かは文字コードにより簡単に分かります.

文字コードとは

文字コードは, コンピュータ上で任意の文字列と対応させるための数値です.

一般的には, 英小文字の文字コードはこのようになっています.

abcde...z
979899100101...122

これにより,各文字が"a"から数えて何番目かは,
その文字の文字コード - 97 という計算によって求める事が可能です.

本題に戻りますが, この問題では, SSを構成する全ての文字に対して, 操作を行うことによってTTに出来るかの判定を行います.

よってこれは以下のことを判定することと同じになります.

判定すること

各 $i (1 \leq i \leq |S|)$ について,$X$が全て等しいか
ただし,$X$は以下の定義によって計算される.
$S$ の各文字を$S_i$, $T$ の各文字を$T_i$, $A$の文字コードをord($A$)と定義すると,
  • ord(Si)ord(Ti)ord(S_i) \leq ord(T_i) の場合 : ord(Ti)ord(Si)ord(T_i) - ord(S_i)
  • ord(Si)>ord(Ti)ord(S_i) > ord(T_i) の場合 : 26{ord(Si)ord(Ti)}26 - \lbrace ord(S_i) - ord(T_i) \rbrace
$ord(S_i) > ord(T_i)$ の場合 について, 追加で説明を行います.
この場合, $S_i$ を1回 "a" に変換してから, 再度順番に変換を繰り返すことにより$T_i$にすることが可能です.
そのとき, 必要な変換の回数は, 26から2つの文字の文字コードの差を引いたものと等しくなるので, このような定義になるのです.

以下に, 正解のソースコードの例を示します. 計算量はO(S)O(|S|)です.

[ ]
ABC232 C問題 Graph Isomorphism
問題へのリンク

解説

この問題は, かなり読解力によって差がついた問題だと思っています. まず, 条件を整理すると, 以下の様になります.

  • PP(1,,N)(1 , \dots , N) を並び替えて得られる
  • 任意の11以上NN以下の整数ii,jj,について次の条件が成り立つ.
高橋君のおもちゃにおいてボール$i$とボール$j$がひもで繋がっているとき,
青木君のおもちゃにおいてボール$P_i$と$P_j$が繋がっている.
制約より, $1 \leq N \leq 8 $であることから, この問題の解法は順列全探索であることがわかります. 従って, 順列全探索により以下の様な判定を行えばよいといえます.
  • 各順列PPに対して
  • 1 ~ N それぞれに対して (これを iiとする)
  • 高橋君のおもちゃにおいて, ボールiiと繋がっているボールの番号全てに対して (これをjjとする)
  • 青木君のおもちゃでボールPjP_jがボールPiP_iと繋がっているかを判断する
  • iiについて, 全ての条件が満たされていれば, この順列PPは問題文の条件をクリアする.
問題文の条件をクリアした順列が$1$つでも存在すれば,`"a"`,そうでなければ `No`を出力する.

計算量は, 高橋君のおもちゃにおいて,NN個全てのボールに対して,N1N-1個のボールが繋がっていた場合があてはまり, O(N!N2)O({N!} * N^{2})程度になるといえます.今回の制約では, 十分に高速です.

以下に, 正解のソースコードの例を示します.

[ ]

Discussion

コメントにはログインが必要です。