00:04
AtCoder Beginner Contest 76回目。A問題。レーティングゴール。
問題文。高橋くんは、あるプログラミングコンテストが行われているサイトに参加しています。
ここでは、コンテストに出場した時に、この順位に応じてパフォーマンスというものが付き、それによってレーティング、整数とは限らないが、次のように変化します。
現在のレーティングをAとする。次のコンテストでパフォーマンスBを取ったとする。その時、レーティングはAとBの平均まで変化する。
例えば、レーティングは1の人が次のコンテストでパフォーマンス1000を取ったら、レーティングは1と1000の平均である500.5になります。
高橋くんは現在のレーティングがRで、次のコンテストでレーティングをちょうどGにしたいと思っています。
その時、高橋くんが取るべきパフォーマンスをまとめなさい。
A問題にしてはちょっと難しめなイメージですね。
出てくるレーティングを出しなさいならわかるんですが、
とりあえず入力を受け取りましょうか。RとGをそれぞれintのインプットで。
RイコールインとGイコールインとインプット。
入力例1は2002と2017。出力例は2032。高橋くんの今のレーティングは2002です。
次のコンテストでパフォーマンス2032を取ると、レーティングは2002と2032の平均である2017となり、目標を達成することができます。
入力例2、4500と0。出力例は-4500。現在のレーティングと目標のレーティングは0以上4500以下ですが、
0未満のパフォーマンスも取ることができます。 0未満のパフォーマンスを取ることもできます?
そいつは困りましたね。 シンプルに数学なんだろうけどちょっと想像つかんねえ。
えーっと
平均を取る。
パフォーマンス、えーと、現在のレーティングたすパフォーマンス割る2ですよね。
2分のレーティングプラスパフォーマンスが本来出るレーティング。
で、今はレーティングがわかってて、 2分のAプラスパフォーマンスがわかんない。
2分のAプラスハテナだね。 2分のAプラスハテナイコール
03:02
わかってるやつだから。 えーっと、つまり
2をかけて、 レーティングの方に2をかけて
パフォーマンスマイナスレーティングにしたらいいのか? 一回やってみようか。
g かけるイコール2 グリンと
g マイナス r 出力例1、2032が出たらオッケー。
2032 出力例2、マイナス4500が出たらオッケー。
4500、マイナス4500。 合ってるかなぁ。出してみましょうか。
なんか実行時間長いですね。ジャッジ待ち。 え、長っ。
再読み込みしてみますね。 あー、AC。よかった。
ではB問題いきます。 B問題。アディション&マルチプリケーション。
問題文。スクエア1001は電光掲示板に整数1が表示されているのを見ました。
彼は電光掲示板に対して以下の操作A、操作Bをすることができます。 操作Aは電光掲示板に表示する整数を今の電光掲示板の整数を2倍にしたものに変える。
操作Bは電光掲示板に表示する整数を今の電光掲示板の整数に k を足したものに変える。
スクエア1001は操作A、操作B合計でN回行わなければなりません。 その時、N回の操作後、電光掲示板に書かれている整数として考えられる最小の値を求めなさい。
06:05
4文でミントリ続けたらいいのかな、とりあえず。 ってパッと思ったので、とりあえずその方向で行ってみましょうか。
n イコールイントのインプット。多分もっと数学的なやり方があると思うんですが。 k イコールイントのインプット。
4i インレンジ n。
k イコールミン k かける2。
ん?違うわ。整数1か。 最初は整数1。で、k を足すか2倍するか。
k を足すか2倍するかなので
ans。アンサーイコール1。 で、4i インレンジ n。アンスイコールミン k かける2。違うわ。
アンサーかける2か、アンサープラス k か。 で、プリント。
アンス。 入力例1は4、3で10が出たらOK。
10。 入力例2は10、10で76が出たらOK。
76、OKですね。提出します。 なんかこれ今日調子悪いですね。再読み込みしたら多分
ACで出てると。うん、出ましたね。 ではC問題いきます。
C問題。デュビアスドキュメント2。 問題文。E869120は宝物が入ってそうの箱を見つけました。
しかしこれには鍵がかかっており、鍵を開けるためにはA小文字からなる文字列Sが必要です。
彼は文字列S'を見つけ、これは文字列Sの0個以上、Sの絶対値、個以内の文字がハテナに置き換わった文字列であることもわかりました。
ただし文字列Aに対してAを文字列Aの長さとします。 Aの横になんか線がピッピって入ってますね。
そこでE869120はヒントとなる紙を見つけました。 条件1、文字列Sの中に連続する部分文字列としてA小文字からなる文字列Tが含まれている。
条件2、Sは条件1を満たす文字列の中で辞書順最小の文字列である。 その時、鍵となる文字列Sを出力しなさい。
09:05
ただしそのような文字列Sが存在しない場合は代わりにunrestrableと出力しなさい。
存在しない場合があるパティーンですね。 ちょっと嫌だなぁ。
鍵となる文字列。 入力例1、ハテナ、TC、ハテナ、ハテナ、ハテナ、ハテナ、でCODERが部分文字列としてあると。
ということはATCODERが正解ですねーってやつですね。 入力例2、ハテナ、ハテナ、P、ハテナ、ハテナ、D、ハテナ、ハテナ、
で分かっている部分文字列がABCとありますが、 分かっている文字の中にABCがなく、ハテナも2つしか連続しているものがないのでこれは嘘。
出力例2はunrestrable。
解説見るか。ちょっとわかんないな。 C問題、C問題。
Sの文字数がTの文字数より小さい場合、明らかに部分文字列として含むことができないので、ここはSの文字列ダイナリーイコールTの文字列の数の場合について考えます。
まず文字列Sのどの連続したTの文字数が文字列Tと一致するかというのを見つけることを考えます。
だからさっきだとTがABC、分かっている連続文字列ABCの3文字がSのどこと一致するかってことですね。
文字列S'のある連続したT文字をX'とし、
XはX'に対応するSの区間とTを一致させることができるか、
すなわちS'のハテナの部分を適切に埋めることでTと一致させることができるかを判定することになります。
同じ長さの文字列AとB、長さをLとするが、一致するのは1以上L以下の整数i全てに対してAのi文字目イコールBのi文字目が成立すると同じであり、
つまり同じi文字目の文字の関係だけについて考えれば良さそうです。
つまりX'のi文字目とTのi文字目の関係が重要です。
それぞれの文字をX'Tと置くことにして次の3パターンに分けることができます。
Aのパターン、X'イコールTの時、これは明らかに一致します。
Bのパターン、X'がハテナではなくX'ノットイコールTの時、これは明らかに一致させることができません。
12:04
X'がハテナの時、ハテナの部分をTにすれば一致させることができます。
すなわちXをTと一致させることができるとは、全てのiに対してAまたはBの場面の関係が成り立っていることで、
もし一つでもBの関係が、ん?AまたはCですね。
ハテナか一致しているか。もし一つでもBの関係、ハテナではなく、かつ同じじゃない。
その場合、文字は一致することができない。 一致させることができる場合、
ハテナの部分を全部Aに変えることで選ぶ区間が確定しています。 辞書最小順なのでね。
選べる区間はSの文字数-Tの文字数プラス1個あるので、それらの区間すべてに対して選んだ区間が決定している状態での辞書順最小を求め、
その中での辞書順最小なものが全部の中の辞書順最小となります。
はいはい。 コード例はなさそうですね。
ゆわんとしていることはわかるんだけど、実装がちょっとわかんないんだよなぁ。
またちょっとPython、他のユーザーの方のを見ておこうと思います。 ではまた次回お疲れ様です。
