ABC093(バーチャル):水色競プロerの復習

昨日のABC156のDが解けずに爆死して一晩。やっと気力が戻ってきたので精進しました。それにしても久々にレート40以上削られました。
今日はABC093の復習です。
〇コンテスト名：ABC093

〇配点：不明

〇制限時間100分(A～Dまでの4問の時代のコンテスト)

〇今回の方針

　心のリハビリがてら気楽にいきましょう。

コンテスト開始！
A - abc of ABC
"a","b","c"からなる3文字の文字列が与えられる。並べ替えて"abc"にできるか判定せよ。

入力をリストで受け取ってソートしてリストが["a","b","c"]と一致すれば"Yes"そうでなければ"No"

S=list(input())
S.sort()
if S==["a","b","c"]:
    print("Yes")
else:
    print("No")

1:33 AC

B - Small and Large Integers
A以上B以下の整数で、A+K以下、B-K以上の数字を昇順に出力せよ。
これは地味に難しいですね。
①A+K以下でB-K以上の数字を2度数えないように注意
②A+K以下だけどBより大きい、B-K以上だけどAより小さいものに注意
ですから。
pythonなら、dictで①を回避し、②はmax,minを使って回避しました。

A,B,K=map(int,input().split())

D={}
for i in range(A,min(A+K,B)):
    D[i]=1
for i in range(max(B+1-K,A),B+1):
    D[i]=1
L=list(D)
L.sort()

for i in range(len(L)):
    print(L[i])

dictを使い、たとえば5を入れる場合、既にdictの中に5があろうがなかろうがdictの5には1を入れる。
後でdictをlistに変換し、listをソートして出力。
setを使っても良かったかもしれません。(setのほうが自然かも？)
6:32 AC

C - Same Integers
整数A,B,Cが与えられる。
①それらのうち2つに対して+1
②どれか1つに対して+2
①と②の操作を行い、A,B,Cを同じにする。
必要な最小の操作回数を求めよ。

A,B,Cの大きさの順がバラバラだと扱いにくいので、
A,B,Cはlistで受けて、ソートして大きい順に並べてしまいましょう。
これでlist[0]が最大、list[2]が最小です。
list[1]とlist[2]に対し、list[0] - list[1]だけ①を行う。
これでlist[0] == list[1] >= list[2]です。
次に、(list[0] - list[2]) % 2 == 0 であれば、list[2]に②を繰り返すだけでlist[0] == list[2]にできます。
(list[0] - list[2]) % 2 == 1であれば、list[2] == list[0] +1になるまで②を繰り返し、
最後にlist[0] とlist[1]に対して①の操作をする必要があります。

L=list(map(int,input().split()))
L.sort(reverse=True)
#print(L)
ans=0
SA=L[0]-L[1]
ans+=SA
L[2]+=SA
L[1]+=SA
#print(L)
if (L[0]-L[2])%2==0:
    ans+=(L[0]-L[2])//2
    print(ans)
else:
    ans+=(L[0]-L[2])//2+1
    ans+=1
    print(ans)

11:28 AC

D - Worst Case
高橋君は2回のコンテストに参加し、結果はA位、B位であった。
スコアをA*Bで定義したとき、高橋君よりスコアの小さい参加者は最大何人か？

これは難しい。
過去に解説を見て考え方を知ってるので何とかなりますが、初見で解いた方々の頭の中はどうなってるんでしょう？

基本的にA*B>=X＊Xとなる最大のXを探します。
aを1以上の整数とすれば、
(X-a)*(X+a)はX*Xより小さいので、(X*X=X^2, (X-a)*(X+a)=X^2-a^2,です)
このaを数える方針です。

後で考える際に楽にするため、AとBの小さい方をA、大きい方をBとします。
・A=3,B=6とすればX=4となり、X+1とX-1を掛けたものは必ずX^2より小さくなります。
・A=3の場合は3を飛ばして2に行っても、必ずX^2より小さくなります。
・手元でテストしてOKだったので証明せずに通しましたが、
　AとBとXの関係は|X-A|<=|B-X|になるようなので、
　先に(X-a-1)*(X;a)となり、その後(X-a-1)*(X+a+1)となり
　結局X^2よりは小さくなります。
これを基本にして、例外を弾いていきましょう。

例外１．A=Bの場合
　　上図ので上段も下段も3にすると、
　　A*B>X*X を満たす最大のXは2ですが、X=3として、(X-a)*(X+a)　a>=1としたほうが基本より1つ多くの組ができますね。
例外２．A+1=Bの場合
　　上図で上段を3、下段を4にすると、
　　A*B>X*X を満たす最大のXは3ですが、上段も下段も3のケースが作れません。
　　なので、基本より1つ少ない組しかできません。
例外３．A*B>X*(X+1)を満たす場合
　　上図で上段を3、下段を7とすると、
　　A*B>X^2を満たす最大のXは4ですが、XとX+1の組でも(ここでは4と5）A*Bより小さければ、
　　上段も下段もXｋら始める基本より、上段X、下段X+1、上段X+1、下段Xからはじめられるこちらのほうが、
　　1つ多くの組が作れます。
例外４． A!=BかつA*B=X*XとなるXが存在する場合
　　上図で上段を2、下段を8とすると、
　　A*B=X*Xを満たすX=4が存在します。が、問題文の条件がA*B>X*Xなので、X*Xを除く、基本より1つ少ない組が作れます。

基本にこれらの例外を加えればOKです。

Q=int(input())
for i in range(Q):
    A,B=map(int,input().split())
    if A>B:
        A,B=B,A
    if A==B:
        print((A-1)*2)
    elif A+1==B:
        print((A-1)*2)
    else:
        SQ=int(pow(A*B,0.5))
        if SQ**2==A*B:
            print((SQ-1)*2-1)
        elif SQ*(SQ+1)<A*B:
            print((SQ-1)*2+1)
        else:
            print((SQ-1)*2)

35:53 AC

もちろん初見では手も足もでません。
過去に色々な解説を見て、考え方を既に知っていたから解けた問題です。
でもいつかはこれを初見で解けるようになりたいですね。