AtCoder Beginner Contest(ABC) 279 - Pythonでのリアルタイム参加結果と内容整理

1. 前書き

AtCoderBeginnerContest(ABC)の参加結果と内容の整理、および外部の解説記事を参考にした上で、自分なりに解法を整理していきます。
使用言語はPythonで行きます。本業ではJavaかRubyonRailsユーザーですが、計算速度の問題であったり、トレンドに乗っておくという意味でも（こちらが大きい）、Pythonに慣れていきたいと思います。

2. コンテスト内容

• コンテスト名
  • AtCoder Beginner Contest 279
• 開催日時
  • 2022/11/26(土) 21:00 - 22:40
• 実施区分
  • リアルタイムRated参加

3. 結果

区分	結果	所要時間	実行時間
A問題	AC	7:14	24ms
B問題	AC	10:59	24ms
C問題	TLE	-	2208ms
D問題	RE	-	24ms

4. 解説

4-1. A問題

4-1-1. 問題文

v と w のみからなる文字列 S が与えられます。
S の中に、下に尖っている部分が何箇所あるかを出力してください（入出力例にある図もご参照ください）。

4-1-2. 入力形式

S

4-1-3. 解説

文字列オブジェクトにindexを与えることで、部分文字列を取得できます。使用例は以下です。

str = 'abcd'
print(str[0]) -> 'a'
print(str[2]) -> 'c'

入力文字列に対してループを作り、文字が「v」なら答えに1を足し、「w」なら答えに2を足していけば良いです。

4-1-4. ソースコード

s = input()
ans = 0
for i in range(len(s)):
  if s[i] == 'v':
    ans += 1
  elif s[i] == 'w':
    ans += 2
 
print(ans)

4-1-5. python文法の整理

文字列オブジェクトをfor文にかける
公式解説を読むと、入力文字列をそのままfor文にかけることができ、もっと単純にできるようでした。

#使用法
for [ローカル変数] in [文字列オブジェクト]:
  ...

#使用例
str = 'abcd'
for char in str:
  print(char)
-> a
-> b
-> c
-> d

4-2. B問題

4-2-1. 問題文

英小文字からなる文字列 S,T が与えられるので、 T が S の(連続する)部分文字列かどうか判定してください。
なお、文字列 X に以下の操作を 0 回以上施して文字列 Y が得られる時、またその時に限り Y は X の(連続する)部分文字列であると言います。
以下の 2 つの操作から 1 つを選択して、その操作を行う。
X の先頭の 1 文字を削除する。
X の末尾の 1 文字を削除する。
例えば tag は voltage の(連続する)部分文字列ですが、 ace は atcoder の(連続する)部分文字列ではありません。

4-2-2. 入力形式

S
T

4-2-3. 解説

findメソッドを使って部分文字列のインデックスを取得します。
結果が「-1」であれば、存在しないので「No」
「0以上」であれば、存在するので「Yes」を出力すれば良いです。

4-2-4. ソースコード

s = input()
t = input()
 
if s.find(t) < 0:
  print('No')
else:
  print('Yes')

4-2-5. python文法の整理

文字列内の部分文字列有無を判定 in演算子
公式解説では、in演算子で部分文字列の有無をTrue/Falseで判定していました。
こちらの方が直感的ですね。

#使用法
[部分文字列オブジェクト] in [文字列オブジェクト]

#使用例
print('abc' in 'abcd') -> True
print('dc' in 'abcd') -> False

4-3. C問題

4-3-1. 問題文

「#」 と 「.」 からなる H 行 W 列の図形 S,T が与えられます。
図形 S は H 個の文字列として与えられ、 S_iの j 文字目は S の i 行 j 列にある要素を表します。 T についても同様です。
S の列を並べ替えて T と等しくできるか判定してください。
但し、図形 X の列を並べ替えるとは、以下の操作を言います。
・(1,2,…,W) の順列 P=(P₁,P₂,…,P_W) をひとつ選択する。
・その後、全ての 1≤i≤H を満たす整数 i について、以下の操作を同時に行う。
　- 1≤j≤W を満たす全ての整数 j について同時に、 X の i 行 j 列にある要素を i 行 P_j列にある要素に置き換える。

4-3-2. 入力形式

H W
S1
S2
...
SH
T1
T2
...
TH

4-3-3. 解説

問題文では、数式を使って複雑に条件を説明していますが、要するに
「図形Sの列を好きに入れ替えて、図形Tと同じものが作れるか？」
ということが問われています。

[筆者の考え]
実装するにあたって、以下の方針で検討しました。

1. 図形S,Tの列数(W)分だけ配列を用意
2. 図形の1行を読み込み、各要素を1.で準備した配列に、一つずつ格納
   -> [[１列目], [2列目], ...,[W列目]]の形式で情報を整理できる
3. 2.の形式で整理したSに対して、1列目/2列目/.../W列目を要素elemとしてループ処理
   ・全要素に対して、「要素elemがSに含まれる個数 = 要素elemがTに含まれる個数」であれば、条件を満たすと判定
   ・どれか1要素でも、「要素elemがSに含まれる個数 ≠ 要素elemがTに含まれる個数」となれば、条件を満たさないと判定

実装は以下の通りにしました。

h,w = map(int,input().split())
s = [[] for _ in range(w)]
t = [[] for _ in range(w)]

for i in range(h):
  row = list(input())
  for j in range(w):
    s[j].append(row[j])

for i in range(h):
  row = list(input())
  for j in range(w):
    t[j].append(row[j])

flg = True
for elem in s:
  if s.count(elem) != t.count(elem):
    print('No')
    flg = False
    break

if flg == True:
  print('Yes')

ロジックはおそらく問題無いと思いますが、結果 「TLE」 となってしまいました。
問題の制約として、H × W ≦ 4 × 10⁵ですので、

• 5行目(図形Sの入力）：H,Wの二重ループなので、Ｏ ≦ 4 × 10⁵
• 10行目(図形Tの入力）：H,Wの二重ループなので、Ｏ ≦ 4 × 10⁵
• 16行目（図形Sの要素に対してカウント）：列数Wでループ、かつ内側の処理で、SとTのcountで全探索しています。問題文の制約からオーダーを出すことはできませんが、結構なオーダーになりそうです。

[解説を踏まえて]
「図形S,Tの列要素を同様のルールでソートして、同じ結果になれば良い」ということでした。
発想として思いつくかどうかの問題なので、今後同じような問題が出たときに、しっかり活用したいところです。

4-3-4. ソースコード

h,w = map(int,input().split())
s = [[] for _ in range(w)]
t = [[] for _ in range(w)]
 
for i in range(h):
  row = list(input())
  for j in range(w):
    s[j].append(row[j])

for i in range(h):
  row = list(input())
  for j in range(w):
    t[j].append(row[j])

s_new = sorted(s)
t_new = sorted(t)
if s_new == t_new:
  print('Yes')
else:
  print('No')

4-4. D問題

4-4-1. 問題文

スーパーマンである高橋くんは、地上で困っている人を助けるため、あるビルの屋上から飛び降りようとしています。 高橋くんがいる星には重力の大きさを表す g という値が定まっており、 高橋くんが落下を開始してから地面に到達するまでにかかる時間はA / √gです。
現在の時刻は 0 であり、g=1 が成り立ちます。 高橋くんは、今から次の操作を好きな回数（0 回でもよい）行います。
　・超能力により g の値を 1 増やす。時間が B 経過する。
その後、高橋くんはビルから飛び降ります。落下を開始した後は g の値を変えることはできません。 また、操作によって経過する時間と落下にかかる時間以外は考えないものとします。
高橋くんが地面に到達できる最も早い時刻を求めてください。

4-4-2. 入力形式

A B

4-4-3. 解説

[筆者の考え]
超能力を使う回数をxとすると、求める時間tは以下の数式で表現することができます。
t = Bx + A/√(1+x)

このグラフがどのような形状か、googleで検索すると表示してくれます。
※google様凄すぎ。。。
検索するとき、AとBは定数部分なので省略して、下記のように検索すると良いです。

このグラフを見ると、明らかに下に凸の関数となっていて、どこかのxで最小値を取ることがわかります。
よって、tの微分のt'=0となるxを求めて、その時のtを出力する問題と捉えることができます。
t' = B - A/2(1+x)^(-3/2)

ただし、xが整数という条件があるので、求めたxに対して小数点を切り上げたものと、切り捨てたもののうち、よりtが小さくなる方を回答とすれば良いと考えました。

例
x = 1.4
・切り捨て：x = 1
・切り上げ：x = 2

上記を実装したものが以下になります。こちらで提出しましたが、結果は 「RE」 でした。
しかも、テストケース全45ケース中、35ケースが 「AC」 で、10ケースのみ 「RE」 。
基本的な考え方は合っているはずで、特殊なケースの検討漏れと想定されましたが、時間が迫っていたため解決に至らず。。。

import math

a,b = map(int,input().split())

ans = b - a
i = 0
if ans > 0:
  print(a)
else:
  i = math.pow(a * a / (4 * b * b), 1/3) - 1
  print(min(b * math.floor(i) + a / math.sqrt(1 + math.floor(i)),b * math.ceil(i) + a / math.sqrt(1 + math.ceil(i))))

[解説を踏まえて]
実数の範囲で、平方根の中身が負の値になることの考慮漏れでした。
数学的な話でしたね。。。

なぜそのケースが発生してしまうのかについて、実際はまだ腹落ちできていません。。。
REが発生したテストケースのテストデータを確認したいのですが、まだアップロードされていないようですね。。。

4-4-4. ソースコード

import math

a,b = map(int,input().split())

ans = b - a
i = 0
if ans > 0:
  print(a)
else:
  i = int(math.pow(a * a / (4 * b * b), 1/3) - 1)
  print(min(b * i + a / math.sqrt(1 + i),b * (i+1) + a / math.sqrt(2 + i)))

4-4-5. python文法の整理

小数点の切り上げ/切り捨て math.ceil(),math.floor()
使用に際して、mathライブラリをインポートする必要があります。

#使用例
import math

print(math.ceil(1.4)) -> 2
print(math.floor(1.4)) -> 1

平方根を表す math.sqrt()
こちらも、mathライブラリをインポートする必要があります。

#使用例
import math

print(math.sqrt(2)) -> 1.4142135623730951

n乗根を表す math.pow(x,a)
2乗根（平方根）はsqrt関数が用意されていますが、3乗根以上はpow関数を使います。

#使用例
import math

print(math.pow(8, 1/3)) -> 2