問題A: 16進数の大小判定
AtCoder Beginner Contest 78回目、A問題、HEX。問題文、プログラミングでは16進数がよく使われます。
16進数では、0、1、2、3、4、5、6、7、8、9の数字のほかにABCDEFの6つのアルファベットを使い、それぞれ10、11、12、13、14、15を表します。
この問題では2つのアルファベットXYが与えられます。 XとYはどちらもABCDEFのうちどれかです。
XとYを16進数として見たとき、どちらの方が大きいかを判定してください。
これは、16進数に置き換えなくとも、AよりB、BよりC、CよりD、DよりE、EよりFの方が大きいというのが真なので、
まあ、辞書順に並べるとかそういう感じでいいと思います。とりあえずXYでイコールインプットドットスプリット、あ、プリットになっちゃった。スプリット。
で、3種類、大なり小なりイコールの3種類があるので、たぶん1行でできない気がするので、
イフXイコールイコールYの場合、プリントイコール。ルイフXよりYの方が大きかったらプリント小なり。
で、エルスそうでなければ大なり。 これでいけるはずですけどね。1回ちょっと出してみましょうか、普通に。
アルファベットも大なり小なり使えたはずなので、はい、ACしました。B問題いきます。 B問題、ISU。問題文、幅Xセンチメートルの椅子があります。
この椅子に座りたい人がたくさんおり、人は椅子に座ると必ずYセンチメートルの幅を使って座ります。
できる限りたくさんの人を椅子に座らせたいですが、人はみなシャイなので、人と人の間、また椅子の端と人の間には少なくともZセンチメートル間を空ける必要があります。
最大で何人座ることができますか。 XYZが与えられます。入力例1はXが13、Yが3、Zが1。
出力例は3、3人。 数のように座ればぴったし3人座ることができます。ぴったし。
1、2、3、まずY、幅を椅子に座ると必ずとる幅Yセンチメートルが3だから
さざんが9。 で、その間にそれぞれ
Zと端っこにZがプラスされる。
ちょっとコードテストで組んでみましょうか。 XYZ
XYZイコールマップのイントインプット
ドットスプリット。 で、どう判定しようかな。
Xマイナスイコール 2かけるZ
がとりあえず入ります。 で、プリント
いや、どうしようかな。
4分でもいい気がするけどなぁ。 4分でやってみましょうか。4はイネンジ。1
で、Xまでにしとこう。
if
そうか。 1人だと
いらないか。 2からにしようかな。
if 2かけるY
違うわ。iかけるYプラス i-1かけるZ
が
Xより大きかったら、終わり。 ブレイクして
パーンスイコール1。 1人も座れないパターンある?
なさそうかなぁ。どうだろう。 1以上。XYZ1以上。
最大で何人に座ることができますか。 Yプラス2Z小なりイコールXだから
最低1人は座れるな、多分。 なので
4iインレンジ2からXまで
if iかけるYプラス i-1かけるZが Xより大きかったらブレイク。そうで
なければアンスイコール i
のプリントアンスで
どうでしょうか。多分もっと楽な出し方があると思いますが。 出力例は3、2は
2つ目は2、2
3つ目 4999
あんまり数字で書いたらちょっと不安になりますが
4999 出力例4つ目は110
110 最後出力例5は109
入力例はクリアしましたがあんまり数が大きすぎるとちょっと怖いですね。 提出していきます。
はい、ACしました。よかった。C問題いきます。 C問題HSI問題文
問題C: プログラムの実行時間の期待値
高橋くんはプログラミングコンテストに出ていますがすべて大文字のイエスかノーで答える問題でTLEしてしまいました。
時間制限オーバーですね。 提出の詳細を見るとテストケースはすべてでNケースあり
そのうちMケースでTLEしてしまいました。 していました。
そこで高橋くんはMケースではそれぞれ実行に1900MS
毎秒かなこれ。 1900MSかかって2分の1の確率で正解し
残りのN-Mケースではそれぞれ実行に100MSかかって必ず正解するプログラムへ書き換えました。
そして以下の操作を行います。 このプログラムを提出する。すべてのケースの実行が終わるまで待機する。
もしMケースのうちどれかで不正解だった場合もう一度プログラムを提出する。 これを一度ですべてのケースに正解するまで繰り返す。
この操作が終了するまでのプログラムの実行時間の相和の期待値をXMSとしたとき
Xを出力してください。なおXは整数で出力してください。 うん?
めちゃくちゃ数学小さいな。Nが1以上100以下。 でMが1以上
小さい方ですね。Nか5かの小さい方。 めちゃくちゃ数学小さいな。どういうこと?
入力例1。Nが1、Mが1。 テストケースはすべてで1ケースありそのうち1ケースでTLEしました。
出力例3800。 この入力だとケースは1ケースだけであり1900MSかかって1 2分の1で正解するプログラムを投げ続けます。
ん? 投げ続けます。
よって答えは1900×1 2分の1
プラス2×1900×1 4分の1
プラス3×1900×1 8分の1 プラス…
3800です。ん? 1回で正解する確率は2分の1、2回で正解する確率は4分の1、3回で正解する確率は8分の1です。
この計算を終える
タイミングはどこだ? 入力例2。10と2。
出力例2。18400。 2ケースで1900MSかかり10-2イコール8ケースで
100MSかかるプログラムを投げ続けます。 すべてのケースで正解する確率は2分の1×2分の1で4分の1です。
ちょっと点でわかんないですね。 解説見よう。C問題。
1回の実行にかかる時間をXMS。 すべてのケースに正解する確率をP。この問題の答えをYMSとします。
Xイコール1900Mプラス100N-M
Pイコール 2のM乗分の1です。
あー問題数。問題数上をしているのか。 2分の1を。
まず1回目の。ん?でも11だったもんな。 まず1回目の提出で必ずXMSはかかります。
その後は確率Pで終了します。 そして確率1-Pでその提出には失敗し、さらに提出を繰り返します。
確率1-Pで失敗した場合のその時点からかかる時間の期待値はYMSです。
よってYイコールXプラス1-PかけるYが成立し、これを解くとYイコールP分のXが得られます。
よって答えはP分のXイコール1900Mプラス100N-Mかける2のM乗です。
んー数学問題っぽいなぁ。
ユーザー解説も見ておきましょうか。 前提知識。確率についてのとある知識という
ジャンプ先があるのでちょっとこれも見ておきましょうか。 解法。有効なのが来るまでカードを引く期待値は有効なカードを引く確率の逆数になる。
これを知っているかどうかが問題である。 ACできる確率は2のM乗分の1であるため。
試行を行う期待値は2のM乗となる。 1回の試行で1900Mプラス100N-M
MSかかるので回数の期待値にこの時間をかければ答え。
あんまり納得いってないですが、とりあえず他の方のPythonの提出コードを見て確認しておこうと思います。
ではまた次回お疲れ様です。