初中級者が解くべき過去問精選 100 問 茶コーダーが解いてみた #2( 工夫する全探索編 )

競技プログラミング 精選100問 問題解説

今日も "初中級者が解くべき過去問精選 100 問"
を解いていきたいと思います！

精選100問って何？

記事はこちら！
qiita.com
こんなに丁寧にまとめてくださっている e869120 さんには本当に感謝しかないです。

記事を上げるタイミングは、この問題は100問ありますが、細かく分野ごとに分かれていますので、分野ごとに全て解き終わったら書いていきたいと思います。

今日は第２回目！！

全探索：工夫して通り数を減らす全列挙

この工夫する全探索の分野は全部で５問あるので、紹介したいと思います！

5. C - Half and Half

https://atcoder.jp/contests/abc095/tasks/arc096_a

これ全探索の問題なのかな？
自分にはいまいち全探索の行い方が閃かなかったので、if文で分岐させてACしました。

a,b,c,x,y = map(int,input().split())
money = 0
if a+b >= c*2:
    money += min(x, y)*c*2
    if x > y:
        money += (x-y)*min(c*2, a)
    else:
        money += (y-x)*min(c*2, b)
else:
    money += a*x
    money += b*y
print(money)

6. D - Lucky PIN

https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_d

これは難しかった...(2WA)
ぱっと見はNの制約が大きいからO(N^2)でもうアウト。
でも見方を変えると、Nの中から
パスワードは000~999までしかないからこの1000通りを全探索すればいい！
１桁と２桁の時だけは０を足すため注意が必要！
計算量はO(N*10^3)

n = int(input())
s = input()
ans = 0
for i in range(1000):
    cnt = 0
    #３桁の暗証番号を設定
    i = str(i)
    if len(i) == 1:
        i = "00" + i
    elif len(i) == 2:
        i = "0" + i
    #そのようなパスワードを作成できるか判定
    for j in s:
        if i[cnt] == j:
            cnt += 1
        if cnt == 3:
            ans += 1
            break
print(ans)

7. C - 最古の遺跡

https://atcoder.jp/contests/joi2007ho/tasks/joi2007ho_c


これはベクトルを使う問題です。
AtCoderにはこのような数問と呼ばれる高校数学を履修していないと厳しい問題が結構出題されます。
今回はその1つです。
軽くだけ紹介しておくと、2つのベクトルを引き算して片方にマイナスをつける！！


詳しい解法については以下の記事がとても丁寧に解説しているので貼っておきます。
qiita.com

n = int(input())
ab = [tuple(map(int,input().split())) for _ in range(n)]
abset = set(ab)
ans = 0
for i in range(n-1):
    for j in range(i+1,n):
        x1, y1 = ab[i]
        x2, y2 = ab[j]
        dx = x2-x1
        dy = y2-y1
        if ((x1+dy, y1-dx) in abset) and ((x2+dy, y2-dx) in abset):
            ans = max(ans, dx**2+dy**2)
print(ans)

8. B - AtCoder Market

https://atcoder.jp/contests/s8pc-6/tasks/s8pc_6_b

これは何も見ずに解けて嬉しかった！！！
A, Bの制約がとても大きく全探索は一見無理そうに見えますが、
\displaystyle A_i < B_i
に着目してしばらく考察していたらある問題を思い出しました。それがこちらです。
atcoder.jp

絶対値の和を最小にしたい問題です。
分散が最小になるときはときは平均値なのは有名ですが、
絶対値の総和が最小になるのは中央値です！！

以前自分が疑問に思って競プロerさんに伺ったツイートも貼っておきます。

詳しくはけんちょんさんがとても丁寧に解説してくださっていますのでそちらの記事も貼っておきます。
drken1215.hatenablog.com

今回の問題の解法は求める距離をd, 入り口をa, 出口をb とすると、
\displaystyle \begin{eqnarray} d &=& \sum_{i = 1}^{n} |a-A_i| + |A_i - B_i| + |b-B_i| \end{eqnarray}
となり、第２項目は a, b が決まれば自動的に決まる定数みたいなものなので、
\displaystyle |a-A_i| と \displaystyle |b-B_i| をそれぞれ最小にしたいわけです。
よって、A, Bの中央値を持ってくることで最小化できます。

n = int(input())
a = [0]*n
b = [0]*n
ans = cnta = cntb = 0
for i in range(n):
    a[i], b[i] = map(int,input().split())
a.sort()
b.sort()
if n%2 == 0:
    cnta += (a[n//2]+a[n//2-1])//2
    cntb += (b[n//2]+b[n//2-1])//2
else:
    cnta += a[n//2]
    cntb += b[n//2]
for i in range(n):
    ans += abs(a[i]-cnta) + abs(b[i]-a[i]) + abs(b[i]-cntb)
print(ans)

9. D - 星座探し

https://atcoder.jp/contests/joi2008yo/tasks/joi2008yo_d

これは面白かった！！
自分の解法は正攻法かはちょっと微妙ですけど、
１つ１つの星座をM個あるデータに合わせるにはどれだけ平行移動する必要があるかを計算し、全て（N個のリスト）に共通して入っているものを出力します。
ポイントとしては、
if 〇〇 in list は時間がめちゃめちゃかかる！！！
なのでsetで＆をとって共通している要素だけを抽出してリストに戻すことで高速に解けます。
これは今後も活用していきたい！！

n = int(input())

a = [0]*n
b = [0]*n
for i in range(n):
    a[i], b[i] = map(int,input().split())

m = int(input())
c = [0]*m
d = [0]*m
for i in range(m):
    c[i], d[i] = map(int,input().split())

difx = [[0]*m for _ in range(n)]
dify = [[0]*m for _ in range(n)]
for i in range(n):
    for j in range(m):
        difx[i][j] = c[j]-a[i]
        dify[i][j] = d[j]-b[i]

ansx = difx[0]
ansy = dify[0]
for i in range(n-1):
    ansx = set(ansx) & set(difx[i+1])
    ansy = set(ansy) & set(dify[i+1])
ansx = list(ansx)
ansy = list(ansy)
print(*ansx, *ansy)

最後に

怪我をしてしまいました。（寝てて背中を痛めた〜〜〜〜！！！！）
でも直ってきたのでペースを取り戻して100問解きたいなー
やっとスタートラインを少し超えました。
この先厳しくなると思いますが、頑張って解き進めていきたいです！！