ABC157:水色競プロerのムーブ備忘録(コンテスト中の考察の流れ)

〇コンテスト名：ABC157

〇配点　 A:100 B:200 C:300 D:400 E:500 F:600

〇制限時間　 100分

　いつも通りのABC

〇コンテスト開始時のsyunsukeのレート　1269

〇今回の方針
　いつも通り。
　基本前から順番に解く。
　Cまではテストケースも程々に速度重視で。
　(Dが難しく、Cまでのペナで死にたくないので。)
　はまったら順位表をチェック。
　・今見てる問題を飛ばす？
　・何か簡単な解法がある？
　の判断材料に

コンテスト開始！
A - Duplex Printing
Nページを両面印刷する。
紙は最小で何枚必要か。

Nが偶数ならN//2、奇数なら(N+1)//2ですね。
それをそのままコードにすれば良いのですが、
コンテスト中は焦っているようです。
わざわざmathをimport して、math.ceilを使っていました。
もちろんそれでも解けるので大きな問題にはならないのですが、
シンプルに解ける問題はシンプルに解きたいところですね。

import math
N=int(input())
print(math.ceil(N/2))

0:57 AC

B - Bingo
3x3のマスのビンゴを行う。
N個の数字が選ばれたとき、ビンゴが成立しているか否かを答えよ。

いやこれ普通に難しくないですか？

ビンゴのマスが3x3で9マス
選ばれる数が最大で10なので全探索でも余裕ですね。

入力を受け取るリストLと
はじめに0で初期化してある3x3のリストBを用意して、
リストLの中に選ばれた数字があれば、リストBの該当箇所を1にする。

最後に、縦、横、斜めにビンゴ成立の可否を確認。

L=[]
for i in range(3):
    l=list(map(int,input().split()))
    L.append(l)
#print(L)

B=[[0,0,0]for i in range(3)]
#print(B)
N=int(input())
for i in range(N):
    n=int(input())
    for h in range(3):
        for w in range(3):
            if L[h][w]==n:
                B[h][w]=1

F=0
for h in range(3):
    cnt=0
    for w in range(3):
        cnt+=B[h][w]
    if cnt==3:
        F=1

for w in range(3):
    cnt=0
    for h in range(3):
        cnt+=B[h][w]
    if cnt==3:
        F=1

if B[0][0]+B[1][1]+B[2][2]==3:
    F=1
if B[2][0]+B[1][1]+B[0][2]==3:
    F=1
if F==1:
    print("Yes")
else:
    print("No")

8:23 AC
ABCのB問題史上最長コードを書いたかもしれません。

C - Guess The Number

3桁以内の整数で、1桁目の0は認めない。
各桁の情報が与えられるので、
情報に矛盾がなければ矛盾しない最小値を出力。
矛盾していれば-1を出力せよ。

長さNの空のリストを用意し、
情報通りの位置に情報通りの数字を入れる。
1桁目が0の場合は-1
ただし、すでに数字が入っていた場合、同じ数字ならOK。
違えば-1
最後に、空のリストに対し、1桁目であれば1、そうでなければ0を入れて出力。
これはB問題より簡単なのでは？

はいWA！

問題文を良く読みましょう。
00は認めないけど、0は認めるんですね。

修正してさっさと通しましょう。

またWA！

Nが1の場合、1桁目の0も認められますね。

N,M=map(int,input().split())
L=["" for i in range(N)]
#print(L)
if N==1 and M==0:
    print(0)
    exit()
for i in range(M):
    a,b=map(int,input().split())
    if N>=2 and a==1 and b==0:
        print(-1)
        exit()
    if L[a-1]=="":
        L[a-1]=b
    else:
        if L[a-1]==b:
            continue
        else:
            print(-1)
            exit()

for i in range(N):
    if i==0:
        if L[i]=="":
            L[i]=1
    else:
        if L[i]=="":
            L[i]=0

if N==1:
    if L[0]==0:
        print(0)
        exit()

ans=0
for i in range(N):
    ans+=L[i]*10**(N-1-i)
print(ans)

26:16 AC 2WA
注意力のない私にはなかなか難しい問題でした。

D - Friend Suggestions
・・・
・・
・
問題文が複雑すぎて理解できません。
順位表を確認して、DとEのどちらを解くか考えましょう。
・・
Dのほうが解かれています。

3回問題文を読んでも、何をもとめられているのかわかりません。
テストケースから考えましょう。

やっとわかりました！
友人の友人の・・とつながっており、
直接の友人でなく、ブロックしている人でもない人を友人候補と呼ぶ。
各人の友人候補を出力せよ。

友人の友人の・・とつながる人はUnionFindで求められますね。
各人が所属するグループの人数から、直接の友人の人数を引き・・
ブロックの扱いに困りました。

ブロックしている人を1人ずつ数えていては間に合いません。
間に合いません。間に合いません？間に合います。
ブロックは最大2x10**5しかありません。

よって、
①UnionFindにより、友人の友人の・・とつながるグループ内の人数を調べる
②グループ内の人数から、直接の友人数を引く
③ブロックしている人がグループ内にいるか否かを判断し、いればその人数を引く
でこたえが求まります。

ですが、
①pythonで提出してしまいTLE
②pypyに修正するもTLE
③入力の高速化
import sys
input=sys.stdin.readline
　を忘れていてTLE
④コードの無駄を解消し、再提出もTLE
⑤UnionFindの「サイズの大きいほうに足す」の部分のコードが抜けており、
　非常に効率の悪いUnionFindになっていたことに気づきやっとAC
そもそも、①、②、③、④はしなくてもACできたかもしれません。

import sys
sys.setrecursionlimit(1000000)
input=sys.stdin.readline

N,M,K=map(int,input().split())

P=[i for i in range(N+1)]
size=[1 for i in range(N+1)]

def find(a):
    if a==P[a]:
        return a
    else:
        return find(P[a])
        
def union(b,c):
    B=find(b)
    C=find(c)
    if size[C]>size[B]:
        P[B]=P[C]
        size[C]+=size[B]
    else:
        P[C]=P[B]
        size[B]+=size[C]
G=[0 for i in range(N+1)]
for i in range(M):
    a,b=map(int,input().split())
    G[a]+=1
    G[b]+=1
    union(a,b)
#print(P)
PP=[]
for i in range(N+1):
    PP.append(find(P[i]))
#print(PP)
PPP=[0 for i in range(N+1)]
for i in range(1,N+1):
    PPP[PP[i]]+=1
#print(PPP)

B=[[]for i in range(N+1)]
for i in range(K):
    c,d=map(int,input().split())
    B[c].append(d)
    B[d].append(c)
#print(G)
#print(B)
ans=[]
for i in range(1,N+1):
    ANS=PPP[PP[i]]-1-G[i]
    for j in B[i]:
        if PP[j]==PP[i]:
            ANS-=1
    ans.append(ANS)
print(*ans)

76:20 AC 4WA
コンテスト中に4WAってはじめてかもしれない。

E - Simple String Queries
長さNの文字列が与えられる。
クエリがQ個与えられ、クエリは
1 i文字目をcに変更
2 l文字目からr文字目までの文字の種類数を出力
のどちらかである。
クエリを処理せよ。

思いついたのは、下のように2次元リストを用意し、
各アルファベットの出現位置をリストに入れておく。

1 のクエリがきたら(例えば1 2 e)
　eの列に2を加えてソート
　bの列にあった2は一つ前の数字(ここでは1)に変えてしまう。
2 のクエリがきたら、
　a～zまでをbisect_leftとbisect_rigntの間の数字の有無を判断。
　あれば種類＋１

１のソートが心配ではあったが、ほとんどソートされた状態の所への追加なので大丈夫なのでは？
と思いましたがダメでした。

どうやって高速化しようか？

と、ここまでで時間切れ。

この問題はあとでゆっくり解説を見て勉強します。

結局
76:20 4完 6WA 1248位でパフォ1215 レートは-5で1264
6WAはダメです。
しかもUnionFindを作り損ねて4WAって。
その場で書けるアルゴリズムも、コンテスト中はライブラリを使ってミスを減らすべきかもしれません。