コンテストと問題
ユニークビジョンプログラミングコンテスト2022 冬、AtCoder Beginner Contest 283、A問題、パワー、問題文、整数A、Bが与えられます。
AのB上の値を出力してください。
このままですね、AとBをもらいます。
まず、マップ、イント、インプット、ドット、スプリット、で、プリント、A、アスタリスク、アスタリスク、B、提出、ACしました。
B問題、ファーストクエリープログラム、問題文、整数Nと長さNの数列Aが与えられます。
クエリが9個与えられるので、与えられた順番に処理してください。
クエリは次の2種類のいずれかです。
数字の1、small k、small x、AKの値をxに変更する。
数字の2、small k、AKの値を出力する。
クエリの数が10の5乗なので、4分で、あ、でもB問題だからそんなに考えないでいいかなと思うので、とりあえずコードテストで組んでいこうと思います。
整数Nと長さNの数列、その後9、クエリの数があって、9個入力が与えられると。
Nイコール、これはマップ、イント、インプット。
で、Aイコール、リストのマップのイント、インプット、.スプリット。
マップ、イントにする必要ないと思うんですけどね。
その値を変えるだけだから、足し引きをする必要がないので。
で、9イコール、イントのインプット。
4、はい、インレンジ、9、クエリの数だけもらいます。
小文字9イコール、インプット、.スプリット。
リストインプットスプリットにしとこうか。
リストインプット.スプリット。
で、if 9の0番目が、これ、K、9、K、1、X、全部数字か。
じゃあリストのマップのイントのインプット.スプリットしておきましょう。
イント、で、クエリの0番目がイコールイコール1だった場合、
AKの値はXに変更する。
Aの、いや、ちょっと待って。
小文字Kイコール9の1番目。
小文字Xイコール9の2番目にして、
Aの、あ、違うわ、マイナス1だ。
小文字Kを9の1番目マイナス1。
0インデックスなのでね。
Xはこのままですね。
AのK番目をXに変えます。
elseプリント、これもやっとくか。
Kイコール、Kはどっちのあれにも共通してるから
もうクエリを受け取った時点で変数に入れときましょうか。
4Iインレンジ9。
で、smallQリストマップイントインプットドットスプリット。
で、smallKに9の1番目マイナス1。
で、プリント。
2だった場合、数字が2だった場合は
AのK番目をプリント。
これでどうでしょうか。
35081。
35081OKですね。
入力例2は26。
2、16、00、16、100。
OK。入力例3。
4、7、8、3、1、7。
多分大丈夫そうですね。
提出します。
問題文自体は結構なんかややこしそうでしたが
やってみるとって感じですね。
ACしました。C問題いきます。
C問題。キャッシュレジスター。
問題文。高橋くんはレジ打ちの仕事をしています。
レジの機械には00、0、1、2、3、4、5、6、7、8、9の11個のボタンがあります。
レジの機械にははじめ0が表示されています。
ボタン00を押すと表示されている数が100倍されます。
それ以外のボタンを押すと表示されている数が10倍された後に
押されたボタンに書かれている数が加算されます。
高橋くんはレジに整数Sを表示させたいです。
レジにSが表示されている状態にするためには
少なくとも何回ボタンを押す必要があるか求めてください。
入力例1。4万4。
出力例は4。
例えば次のように操作することでボタンを4回押して
400、4004を出力させることができます。
はじめレジには0が表示されています。
ボタン4を押す。
レジに表示されている数は4となる。
ボタン00を押す。
400。
ボタン0を押す。
4000。
ボタン4を押す。
4万4ですね。
ボタン
これはDPかな?
Sは64ビット整数に収まらない場合があることに注意してください。
いや、待てよ。DPというか。
ボタン00を押すと
レジの機械には
00、01、02、03、04、05、06、07、08、09と
10倍してその数字を入力するんですよね。
じゃあ
あ、でも00があるかどうかを判定するので
これ何?10の?1、2
3、4、5、5乗かな?
制約が。
4分で回していると多分入力で3がすごい量になっているので
これは落ち着かない。
00の個数を求めて
その数分引いて
で、あとは文字数
でカウントしたらいいような気もする。
ので
一旦その方針でやってみましょうか。
Sイコール
インプット
00CNTカウント2
S.カウント
ダブルコーテーション00
プリント
連絵数
マイナス
にかける
ゼロカウント
で、一回
入力例1、4004
ちゃうわ、4004
ん?ちゃうわ、4004ですね。
3
そうかー
00の部分がダブっちゃってるんだなー多分。
プリント
ゼロカウント
あ、違う。かぶってない。
1個だ。
ってことは
マイナス1かけるゼロカウント
それだったらゼロカウントをマイナスさせるだけでいい。
4004
にさらに00を出してみましょうか。
5
プラス0したら6になるはず。
なってるねー。
これでいいのか?
入力例2は10
入力例3は27
これが特にオーバーしなければOKなんですが
27、出たねー。
提出してみましょうか。
入力例はクリアしたので。
いった。エンシーしまった。
ではD問題いきます。
キャッシュレジスター
D問題、スコープ。
問題文、A小文字
カッコからなる文字列のうち
以下の手順によって空文字列になるものを
E文字列と呼びます。
まずA小文字をすべて削除する。
次に連続するカッコが存在する限り
それを削除する。
例えば
まず大きいカッコがあって
その中にカッコがあって
スモールA
そのカッコから外れてBAでカッコ閉じる。
A小文字をすべて削除すると
二重カッコですね。
カッコの中にカッコがある。
となり二文字目と三文字目に連続するカッコを削除すると
一つのカッコとなり
最終的に空文字列にすることができるので
E文字列です。
これ音声だけだと何言ってるかわかんないですね。
E文字列Sが与えられます。
Sの合文字目をSIで表します。
各A小文字AからZに対して
その文字が書かれたボールが一つあります。
また空の箱があります。
高橋くんはIイコールFの文字列分
文字数分に対して
この順に気を失わない限り操作を行います。
SIがA小文字ならば
そのA小文字が書かれたボールを箱に入れる。
ただしそのボールがすでに箱に入っている場合
高橋くんは気を失う。
なんで?
なんで?
SIが左に膨らんでいる
はじまりの括弧ならば何もしない。
SIが右に膨らんでいる
終わりの括弧ならば
i未満の整数Jであって
SのJ番目からi番目までの文字からなる文字列が
E文字列となる最大の整数Jを取る。
このような整数Jは必ず存在することが証明できる。
J番目からi番目までの操作で
箱に入れたボールをすべて箱から取り出す。
高橋くんが気を失わずに
一連の操作を完了させられるか判定してください。
なんで気を失うの?
ちょっとそこに気を取られてしまって
全然問題が頭に入ってこないんですが。
制約はSの文字数ですね。
1以上を3×10の5乗以下。
高橋くんが気を失わずに
一連の操作を完了させられる場合はイエス。
そうでない場合はノー。
入力例1はイエス。
文字列を…
なんか声裏返ったな。
文字列を
順繰りに文字列というか
与えられたものを
1番目からチェックしていって
括弧であれば何もしない。
アルファベットがあったら
空の箱に登録していく。
で、もし
ん?
iイコール4の時4未満の整数Jであって
SのJ番目から4番目までの
文字からなる文字列が
E文字列となる最大の整数は2であると。
うん?
ちょっと気を失うが
ワード強すぎて入ってこないので
解説見ますね。
Dスコープ。
次のようなアルゴリズムを考えます。
整数CをCイコール0
集合X0からXのSの文字数分まで
を空集合で初期化する。
iイコールSの文字数分について
この順に以下の操作を行います。
SIイコール始まりの括弧の時
Cの値を1増やす。
SIイコール閉じ括弧の時
XCを空にしてCの値を1減らす。
SIがA小文字の時
XC
左矢印
XC
なんだっけこれ集合の記号
Uみたいなやつ。
で、えー
吹き出し括弧
SIとする。
ただしSI
これ記号読めないと
解説を音声でお届けするの無理ですね。
これなんだ
読めねー
これ名前ないの
Eみたいなやつ。
角っこが丸くなった
大文字のEみたいな
やつですね。
これならば高橋くんは気を失うと判定する。
以下このアルゴリズムの正当性を示します。
SIイコール閉じ括弧で
JがSのJ番目からI番目までの
文字からなる文字列が
E文字列となる最大の整数とします。
この時Iに関する操作は
CをIに関する操作を行う直前の値とし
これはJに関する操作を行った直後のCの値に等し
D大なりイコールCを満たす全てのDについて
XDを空にすることに当たりますが
実際にはD大なりCの時は
XDは空集合です。
何を言っているのかちょっと分かりませんので
実装例もC++なので
他のPythonユーザーの方の回答例を見て
勉強しておこうと思います。
ではまた次回お疲れ様です。