A問題SEIM問題文
日本レジストリサービス）JPRS）プログラミングコンテスト2023）AtCoder Beginner Contest 324回目）A問題）SEIM問題文、N個の整数A1からANが与えられます。
これらの値がすべて等しいならばイエス、そうでなければノーと出力してください。
出力例3、3、2、4、出力はノー。出力例2、4、3、3、3、3、出力例はイエス。
Nイコールインプット、Lイコールセットのリストのインプットドットスプリット、これでWが消えるので、
プリント、イエス、イフレンレルがイコールイコール1だったらエルス、そうでなければノーを出せばいいはず。提出。
B問題3スムースナンバーズ問題文、正の整数Nが与えられます。Nイコール2のX乗×3のY乗を満たす整数XYが存在するならイエス、そうでなければノーと出力してください。
出力例1、3、2、4、出力はイエス。Xイコール2、Yイコール4とすると、2の2乗×3の4乗、4×81で324となるため条件を満たします。よってイエスと出力してください。
コードテストでやりましょうか。
X乗×3のY乗がNをオーバーしたらブレーク。
イコールイコールイエス、Nだったらエグジット、プリントイエス。
何にも引っかからなかったらプリント、ノー。
4XインレンジNのところに、F2のX乗がNをオーバーしたらもうその時点でアウトなので、エグジット、プリント、ノー。
エグジットが文字変わらない白文字なんですがこれ大丈夫かなコマンド。
入力例1はイエス、2はノー、5がノー、ノー。
入力例3、32はイエス、イエス。
入力例4、3、7、7、8、7、3、6はイエス。
コードテストはクリアしているので一応出してみます。
B問題なので、A、Bはやるだけなところがあるので大丈夫だと思うんですが。
ACしたのでC問題いきます。
C問題。エラーコレクション。問題文。
高橋くんはA小文字からなる文字列Tを青木くんに向けて送りました。
その結果、青木くんはA小文字からなる文字列T'を受信しました。
T'はTから一部が変更されてしまっている可能性があり、具体的には下記の4つのうちのちょうど1つが成り立つことがわかっています。
T'はTと等しい。
T'はTのいずれか1つの文字、1つの位置、先頭末尾も含む、にA小文字を1つ挿入して得られる文字列である。
T'はTからある1文字を削除して得られる文字列である。
T'はTのある1文字を別のA小文字に変更して得られる文字列である。
青木くんが受信した文字列T'とA小文字からなるN個の文字列S1からSNが入力として与えられるので、
S1からSNのうち高橋くんが送った文字列Tと等しい可能性があるものをすべて求めてください。
入力例1、5と元々のT'とSを与えられるので、Sのうち高橋くんが送った文字列Tと等しい可能性がある。
大元のTは公開されておらず、何らかの変更が加えられたかもしれないT'だけ受け取られて、
さらにそこに変更を加えたSの文字列が複数与えられて、
その変更されたT'と全く関係ないSから累推して、
オリジナルTに近しい可能性がある、同じ可能性があるSを出せってことですね。
ややこしいな、青木。
入力例1、出力例は4、1、2、3、4。
S1からS5のうちTと等しい可能性があるものはS1、2、3、4の4つであることが書きの通りわかります。
A、B、A、B、C、B、A、B、C、はいはいはいはい。
やらんとしていることはわかるが。
うーん。
1文字プラスされているか、1文字減っているか、1文字変わっているか、全く同じかのどれかですね。
どうしようかな。1回ちょっとやってみるか。やるだけやってみるか。
それだけやってみるか。
nとTイコールインプットドットスプリットを
IinRangeIntNでSイコールイントの、イントじゃないわ、インプットを
JinRangeどうしようかな。
うーん。
IF連S、ABS連S-連T、これがダイナリイコール2だったらコンティニュー。
2文字以上プラスされている、あるいは2文字以上削られているという時点でもうアウトなので、
それはもう調べる必要がない。
文字数が全く一緒か、1文字分違うかを判定すればいいのでOK。
で、他は何を精査すればいいんだ?
足してる?引いてる?
足してるかどうかは、IFTINSだったらプリント。
あ、そうか。問題の答えはどういう?
数字とインデックス数だから空のリストを作っておいて
L.Append i++とコンティニューですね。
そうじゃない場合、このIFTINSで同一またはプラス1が処理されるから
あとは文字を変えたパターンと文字を減らしたパターンがどうやってはめ込むかですね。
辞書を使うか?
いやでもそしたら場所が勝ち合わなくなっちゃうから。
どうしようかな。
4i in 連字。
minだなとりあえず。
minというか、
ん?この時点でsの方が短いのが残ってる。
sとtが同じ文字数か、sの方が短い文字数かっていうのだけが残っている。
どうしようかな。
bit全短冊とかでなんとかなりそうな気はするんですけどね。
使い方全然わかんないんだよな。
もし文字が削れているパターンだったとしても、文字が変わっているパターンだとしても
bit短冊だったら01で何文字目を使う使わないっていう選択ができるはずだから
そこでtとsが同じになったらもうyesでokなんですよ。
のはずなんですよね。たぶんね。理屈としては。
ただそれを使いこなせないので
連字連sでやっていくしかないか。
文字数が同じパターンとsの方が短いパターンで分けるか。
ちょっとブサイクになっちゃうけどコードが。
連s連tをどっかで変えとくか。
lsイコール連sっていうのを4文の最初につけとこう。
ltイコール連t。
4文の最初につけておこう。
4文の最初につけておこう。
4文の最初につけておこう。
4文の最初につけておこう。
4文の最初につけておこう。
ltイコール連t。
lsイコールイコールltの場合、
4はインレンジls。
if文のiflsイコールイコールltのとこに
cntをつけます。
イコールゼロで初期化して4jインレンジls。
ifsのj番目がnotイコールtのj番目だったら
cntプラスイコール1。
ifcntが1以上になったら
もうアウト関係ないので
ブレークしてもらって大丈夫です。
4文が全部終わって
ifcntイコールイコール1だったら
l.append iプラス1。
これが文字が変わっていたパターンの
あぶり出しで
文字が減っていたパターンが
ちょっとわかんないな。
イメージできないな。
ifls小なりltだったら
4jインレンジls
ifsのj番目イコールイコールtの
j番目だったら関係ない。
ifsのj番目がnotイコールtの
j番目だったら
スライスを使った文字列の処理
ド頭が変わっている場合があるんだよな。
いや、そうか。
スライスすればいいのか。
スライスってどうやるの?
めっちゃこれ処理時間長くなりそうだな。
4jインレンジltにして
ifsイコールイコールtの
tのj番目
tのjイコール番目
tのプラスだったら
l.append iプラス1
プリントlを押してみると
abs関数を消しちゃっているので
括弧をどっか抜いちゃってますね。
1と4が出力されました。
でも欲しいのは1234だね。
1234は
12323が入ってない。
あー、プラスしたパターンか。
そうか、プラスしたパターンって
先頭か末尾関係ねえんだ。
間に入っている場合もあるから。
その場合は
さっき書いた
lsとltを逆順というか
反対にすればいいのでは?
文字列の一致を判定するコード
4ls小なりlt
4jインレンジlt
で、if tの
if tイコールイコール
sのj番目まで
プラスsのj番目以降
1文字ずらし
あれこれs?
ls小なりlt
違う違う、逆だな。
ls大なりlt
で、4jインレンジls
どうだ?
うん。
あ、lsって書いちゃってる。
lsですね。
14
さあOK。
解説を見ます。
絶対もっと簡単なやり方があるんですよね。
公式解説。
syがtと等しい可能性があるか
つまりt
これ何?
トンボみたいなマーク
tコロンイコールかな?
syと置いたとき
仮定かな?
仮定でイコール
可能性があるイコールってことかな?
問題文中の4つの条件のいずれかを
満たすかを判定することを考えます。
本問題を解くには
各iについてこれを行えばよいです。
tがイコールの可能性である
syと置きます。
tとt'が先頭から見て
何文字目まで一致するかを調べ
一致する最大の長さをaと置きます。
同様に
tとt'が末尾から見たときに
一致する最大の長さをbと置きます。
例えばabcdとabcdacdは
先頭から見ると
abcの3文字までが一致し
末尾から見ると
abcの2文字までが一致します。
このとき問題文中の
4つの条件はそれぞれ
abおよびtとt'の長さ
連t'によって
書きの通りに言い換えられます。
t'は
tと等しい
つまりaイコールbイコール
tの長さイコールt'の長さ
t'は
tのいずれか1つの位置
先頭末尾も含む
2小文字を1つ挿入して得られる文字列
これは
a'b'イコール
tの文字列イコール
t'の文字列-1
t'はtからある1文字を
削除して得られる文字列である。
これは
a'b'イコール
tの文字列-1イコール
t'の文字列
t'はtからある1文字を別の英語文字に
変更して得られる文字列である。
これは
a'b'イコール
t'の文字列-1 よってabtの文字数 t'の文字数が上記の4つのいずれ
かの条件を満たすかを実際に判定 すればよいです 全く何言ってる
か分かんないな 別回があるので 見ますが Pythonがある 助かる
公式解説のように 文字列を両側 から操作することは必須ではありません
操作って 走るに検査の差なんですよ ね 探偵とかの操作じゃなくて 両側
から操作することは必須ではありません 以下のように ミスマッチを一度
だけ許容して 2つの文字列を先頭 から比較することもできます 文字
列上に差があれば挿入か削除があった こと 差がなければそれらがなかった
ことを前提とします Pythonで関数 使ってますね チェックst if連s代
なり連tの場合 returnチェックts if 連s小なり連t-1だったらreturnフォルス
ijミスをそれぞれ0を入れる while i小なり連sの間 if si==tjの場合
i-1j-1そうでなければミスプラス 1 ifミスが大なり11より多ければ
returnフォルス if連s==tの場合i-1j-1returntrue
ntでインプットスプリットして nでint nにしてアンスは空のリスト
for i in range n sを受け取るifチェック stがtrueだったらappend i-1プリント
連アンスで空白でジョインしてマップ のstrアンス 関数のとこをちゃんと
見ないと分かんないな チェック 関数stっていうのがsがちっちゃい
tがちっちゃいtが大きいですね 文字数的に なのでif一番初めのif
関数で連sが連tより大きかったら returnチェックtsってひっくり返して
るんですね なるほどねそういう切り替えの
仕方ができるのか でif連s小なり連t-1うんうんだから
差が2以上あったらそもそも成り立 ってないのでフォルスを返すと
でiとjとミスをそれぞれ0を入れて 定義してifiが連sより小さい間
続けますsiイコールイコールtjだったら iとjをプラス1していくもし一緒
じゃなければミスをプラス1する もしミスが2以上あったらそれ
もまた成り立たないのでフォルス を返すif連sイコールイコール連
tだったらiプラスイコール1これが どういうことだ連sイコールイコール
連tだったらiプラスイコール1はい 同じ文字数だったらそのミスの
部分はつまり文字を変更したパターン だからiを変えるとでこのifに引っ
かからない場合文字数が一緒じゃない 場合はiは変えずにjだけを変える
とはーなるほど理屈はちょっと わかったけれどこれを頭で組み
立てて実装ってなるとなかなか 思いつかんもんですね勉強になりました
では今回はここまでにしましょう また次回お疲れ様です