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

問題へのリンク

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

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

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

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

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

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

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

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

問題へのリンク

解説

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

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

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

文字コードとは

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

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

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

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

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

判定すること

$ord(S_i) > ord(T_i)$ の場合 について, 追加で説明を行います.
この場合, $S_i$ を1回 "a" に変換してから, 再度順番に変換を繰り返すことにより$T_i$にすることが可能です.
そのとき, 必要な変換の回数は, 26から2つの文字の文字コードの差を引いたものと等しくなるので, このような定義になるのです.

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

問題へのリンク

解説

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

制約より, $1 \leq N \leq 8 $であることから, この問題の解法は順列全探索であることがわかります. 従って, 順列全探索により以下の様な判定を行えばよいといえます. 問題文の条件をクリアした順列が$1$つでも存在すれば,`"a"`,そうでなければ `No`を出力する.

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

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