やるだけPython競プロ日誌

競プロの解説をPythonでやっていきます。できるだけ初心者に分かりやすいように『やるだけ』とかは言わないようにします。コメントについては必ず読んでいます。どんなに細かいことでもいいのでコメントくださればうれしいです。

PythonでAtCoder Beginner Contest 078 ABC078

AtCoder Python ABC

AtCoder Beginner Contest 078 ABC078

 

2017/11/11 21:00 ～ 22:40の問題でした。

 

簡単に説明すると

 

A：文字同士の順序を求める

B：植木算（小学校でやるやつ）

C：回数としての期待値の算出

D：max計算でOK

 

となります。

 


A：HEX

問題文

プログラミングでは 16進数がよく使われます。
16進数では 0,1,...,9 の数字の他に A, B, C, D, E, F の 6 つのアルファベットを使い，それぞれ 10,11,12,13,14,15を表します。
この問題では 2つのアルファベット X,Y が与えられます。 X と Yはどちらも A, B, C, D, E, F のうちどれかです。
Xと Y を 16進数として見たとき，どちらのほうが大きいかを判定してください。

制約

  • X,Yは A, B, C, D, E, F のうちどれかである。

入力

入力は以下の形式で標準入力から与えられる。
X Y

出力

Xのほうが小さいならば <，Y のほうが小さいならば >，等しいならば = と出力してください。

一般的な（というより素直な）解でいうと

 

alpha = ("A", "B", "C", "D" ,"E", "F")  # 文字の順番を決める
a = input().split()  # 入力をリストにして受け取る
if a[0] == a[1]:  # 入力が二文字とも同じなら
　　　　print("=")  # "=" を出力
elif alpha.index(a[0]) < alpha.index(a[1]):  # 二文字目のほうが順番が後なら
　　　　print("<")  # "<" を出力
else:  #>>3 >>5　# どちらでもない（一文字目のほうが順番が後）なら
　　　　print(">")  # ">" を出力


 

となりますかね。

 

(リスト名).index(要素)　は要素の位置を返してくれます。

 

あるいは、文字にも順番がある（あります）ので、

 

a, b = input().split()  # 入力を受け取る
if a == b:  # 入力が二文字とも同じなら
　　　　print("=")  # "=" を出力
elif a < b:  # 二文字目のほうが順番が後なら
　　　　print("<")  #"<" を出力
else:  # >>2 >>4どちらでもない（一文字目のほうが順番が後）なら
　　　　print(">")  # ">" を出力


 

 

というように、文字そのもののサイズを比べることで順番を比べることになります。

 


B：ISU

問題文

幅 Xセンチメートルの椅子があります。 この椅子に座りたい人がたくさんおり，人は椅子に座ると必ず Yセンチメートルの幅を使って座ります。
出来る限りたくさんの人を椅子に座らせたいですが， 人はみなシャイなので，人と人の間，また椅子の端と人の間には， 少なくとも Zセンチメートル間を開ける必要があります。
最大で何人座ることができますか？

制約

  • 入力は全て整数
  • 1≤X,Y,Z≤105
  • Y+2Z≤X

入力

入力は以下の形式で標準入力から与えられる。
X Y Z

出力

求めた答えを出力してください。

植木算ですね。植木算。それです。小学校でやった。あれ。

 

a, b, c = list(map(int, input().split()))  # 入力の受け取り
print( (a - c) // (b + c) )  # 計算


 

あまり植木算の説明というのはやりたくないんですが・・・・一応やります。

 

入力例１でいえば、椅子の幅が13、一人3マス、脇に1マス必要ということですので

 

◆◆◆◆◆◆◆◆◆◆◆◆◆　　横13マス

＃人人人＃人人人＃人人人＃

 

ということですよね。分けて考えてみると

 

『＃人人人』　×　３　＋　『＃』

 

っていう見方もできます。

 

 

なので、

 

 

(a - c) // (b + c)   ==  (　椅子の長さ　－　右端の『＃』)　÷　（『＃人人人』の長さ）

 

 

となります。

 
 

C:HSI

問題文

高橋くんはプログラミングコンテストに出ていますが， YES か NO で答える問題でTLEしてしまいました。
提出の詳細を見ると，テストケースは全てで Nケースあり，そのうち MケースでTLEしていました。
そこで高橋くんは, Mケースではそれぞれ実行に 1900 ms かかって 1/2 の確率で正解し， 残りの N−M ケースではそれぞれ実行に 100ms かかって必ず正解するプログラムへ書き換えました。
そして，以下の操作を行います。

  • このプログラムを提出する。
  • 全てのケースの実行が終わるまで待機する。
  • もし Mケースのうちどれかで不正解だった場合，もう一度プログラムを提出する。

これを，一度で全てのケースに正解するまで繰り返す。
この操作が終了するまでの，プログラムの実行時間の総和の期待値を Xmsとした時，Xを出力してください。
なお，Xは整数で出力してください。

制約

  • 入力は全て整数
  • 1≤N≤100
  • 1≤M≤min(N,5)

入力

入力は以下の形式で標準入力から与えられる。
N M

出力

実行時間の総和の期待値 Xを整数で出力してください。 なお，X はこの問題の制約下で，109 以下の整数となることが証明できます。

 
これには少し悩みました。
 
Σ計算とか使うのかな・・・なんて悩んでいましたが、大切なことを思い出しました。
 
期待値は、確率の逆数です。なので
 

a, b = list(map(int, input().split()))  # 入力の受け取り
print( (b * 1900 + (a - b) * 100) * 2 ** a)  # 計算


 

となります。

 

 
ええ、この二行だけです。
 
解説をしますね。
 
 
これは、二つの部分に分けて考えるとわかりやすいと思います。
 
(b * 1900 + (a - b) * 100) 
と
(上式)* 2 ** a
 
です。
 
まずは上段。
 
これは、一回あたりの計算時間です。そのままですね。
 
次の下段ですが、そのまえに考えてほしい問題があります。
 

裏と表、それぞれ出る確率が同様に確からしいコインがn枚あったとし、
このコインのすべてが表が出るまで同時に投げ続けたとする。
投げる回数の期待値はいくらか？

 
答えは、2^n となります。
 
コインが1つなら2回、2つなら4回、3つなら8回といった具合です。
 
これを変形し、
 

裏と表、それぞれ出る確率が同様に確からしく、なおかつ1枚投げるのに1900ms掛かるコインがn枚あったとし、必ず表が出て、かつ1枚投げるのに100ms掛かるコインがm枚あったとする。
このコインのすべてが表が出るまで1枚ずつ投げ続けたとする。
かかる時間のの期待値はいくらか？
※ただしコインを投げている途中に裏が出ても最後まで投げつづけるものとする。

 
これの答えを言うと
 
(1900 × n + 100 × m) × 2 ^ n
 
です。
 
一回の試行時間　×　回数の期待値です。
 
これを今回のC問題に合わせてみると
 
(b * 1900 + (a - b) * 100) * 2 ** a
 
となりますよね。これが答えです。

 


D:ABS

問題文

N枚のカードからなる山札があります。カードにはそれぞれ数が書かれており， 上から i 枚目には aiが書かれています。
この山札を使い，X さんと Y さんが 2人でゲームをします。 X, Y さんは最初，Z,Wが書かれたカードを持っています。 そして X さんから交互に以下を行います。

  • 山札から何枚かカードを引く。そして今持っているカードを捨て，最後に引いたカードを代わりに持つ。ただし，必ず 1
  • 枚は引かなくてはならない。

山札がなくなるとゲームは終了で，2人の持っているカードに書かれた数の差の絶対値がこのゲームのスコアになります。
X さんはスコアを最大化するように，Y さんはスコアを最小化するようにゲームをプレイした時， スコアはいくつになるでしょうか？

制約

  • 入力は全て整数
  • 1≤N≤2000
  • 1≤Z,W,ai≤109

入力

入力は以下の形式で標準入力から与えられる。
N Z W
a1 a2 ... aN

出力

求めたスコアを出力してください。

D問題にしては簡単でした。

 

コードはこちらになります

 

a = list(map(int, input().split()))  # 入力をリストにして受け付け
b = list(map(int, input().split()))
try:
    print(max(abs(a[2] - b[-1]), abs(b[-1] - b[-2]))) # xさんが最後から二番目の数か最後の数どちらを取ればよいかを判断
except:  # 与えられる数が一つの場合
    print(abs(a[2] - b[0]))


 

です。

 

なぜこれだけでよいのか？というのは、思考力の問題になります。地頭の範疇です。

 

xさんがどれだけ頑張っても、最後から3番目以前の数を取ってしまえば、yさんができるだけ小さい数を取らせようとしてきます。

 

つまり、yさんに選択の余地を与えてはいけないのです。となると

  1. yさんの取れるカードを1つだけにする(xさんが最後から2枚目までを取る)
  2. そもそもyさんに取らせない

のどちらかですね。

 

4行目のコードで、1と2を試し、どちらのほうが絶対値が大きいかを試しています。

 

5‐6行目のコードですが、4行目のコードでは、もしカードが一枚しか与えられなかった場合(b[-2])がリストの範囲を超えますのでエラーが出ます。

 

そのエラーが出た場合、無条件でその唯一のカードとyのカードの差の絶対値をprintする。となっています。

 

 

今回のABCは比較的簡単だったと感じています。

皆様の中にも、いつもよりいけた。だとか、いけそうだった！という方が大勢いらっしゃると思います。

 

このまま努力を続け、Pythonistaの皆様、良いPythonLifeをお送りください！