プログラミングよくわからんケモノのABC392

ABC392感想

C問題……。
一先ず4完出来たので、一旦よしとしましょう。

A問題

数字の書かれた紙が3枚あって、そこから2つを選び、その積が選ばなかった残り1つと同じ値になるか、って問題です。

いつものA問題の通りに言われた通り、実装です。
楽に書く方法なんていくらでもありますが、如何に直感的で可能な限り短く書けるか、を大事にしています。
今回の場合は、リスト型で受け取るんじゃなく、a, b, c みたいに受け取れば多少はシンプルに書けたな、くらいは考えています。

python abc392_a.py

def main():
    l = list(map(int, input().split()))
    
    if l[0] * l[1] == l[2]:
      print("Yes")
      
    elif l[0] * l[2] == l[1]:
      print("Yes")
      
    elif l[1] * l[2] == l[0]:
      print("Yes")
      
    else:
      print("No")

main()

B問題

Nと数字の書かれたメモが与えられるので、1～Nのうち、メモに書かれていない数字を出せって問題ですね。

まあ、これも書いてある通りに実装すればいいんですけど……。
今思うと N - 数字の書かれたメモの要素数(しかもMとして与えられてる。) を使えば一旦リストに入れる作業分手間ですね。

python abc392_b.py

def main():
    N, M = map(int, sys.stdin.readline().rstrip().split())
    l = set(list(map(int, sys.stdin.readline().rstrip().split())))
    
    ll = []
    for n in range(1, N + 1):
      if n not in l:
        ll.append(n)
        
    print(len(ll))
    print(*ll)

main()

C問題

今回一番苦しんだ問題です。
ゼッケン番号iを付けた人aが、人bを見ているので、その人bがつけているゼッケンの番号をゼッケン番号昇順で答えろ。って問題です。

あまりにも意味が分からないので、少し丁寧に解説します。
与えられるリストが、

• 番号iの人が何番目の人を見ているか
• 番号iがつけているゼッケンは何番か

の２つです。

大事なのは、この2つのリストの他に、

• 1 ~ 人の数までの番号のいずれかを持つ人間のリスト

があることを忘れないことです。

では素直に実装する場合、何が起こるかを考えてみましょう。

1. i = 1とする
2. i番のゼッケンをつけている人が見ている人の番号をjとする
3. j番目の人がつけているゼッケン番号を出力する
4. iがまだ人の数を超えていないならiに1を加える
5. 2に戻る

こうなるわけです。
ただ、これをやるのは面倒なので、私の実装としては、先に出力するリストを用意しておいて、人順に見ていき、
リスト[見ている側のゼッケン番号] = 見られている側のゼッケン番号
としました。

python abc392_c.py

def main():
    N = int(sys.stdin.readline().rstrip())
    l = [0] * N # 出力用リスト
    sl = list(map(int, sys.stdin.readline().rstrip().split())) # 誰を見ているかのリスト
    zl = list(map(int, sys.stdin.readline().rstrip().split())) # ゼッケン番号リスト

    for z, i in zip(zl, range(N)):
        l[z - 1] = zl[sl[i] - 1]

    print(*l)

main()

書いてみるとシンプルなんですけどね。。。

D問題

サイコロ2つの同じ目が出る確率を求めてくれ。って問題が${}_NC_2$回来るので、その中で最も大きい値を答えろって問題ですね。

そもそも一般的な6面サイコロを2つ振った時の出目が同じになる確率は1/6ですが、これはそれぞれの出目に対して、対応している面がいくつあるかの和算なんです。
なので、各サイコロを数字ごとに、それがいくつあるのかをリスト化し、

数値iが、サイコロaにいくつあるか × サイコロbにいくつあるか、の和算 分の
サイコロaの要素数 × サイコロbの要素数

を各サイコロの組み合わせに対して行い、それの最大値を愚直に出力しました。
サイコロの数は最大でも100しかないことから、${}_{100}C_2$ より、4950通りしかないため、雑に計算しても良かったのはありがたいですが、浮動小数の比較がめちゃくちゃ怖かったですね。
分数状態での比較が出来るようになっておいた方がよさそうかな、と思っています。

python abc392_d.py

import itertools as it
import collections as cs

def main():
    N = int(sys.stdin.readline().rstrip())
    il = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(N)]
    l = [[ll[0], cs.Counter(ll[1:])] for ll in il]
    
    al = 0
    for i, j in it.combinations(l, 2):
      sl = [0, i[0] * j[0]]
      
      for ik in i[1].keys():
        sl[0] += j[1][ik] * i[1][ik]
        
      if al < (x := sl[0] / sl[1]):
        al = x
        
    print(al)

main()

E問題

競プロあるある、橋の付け替え問題。

辺を付け替えることは出来ても、追加することは出来ないため、余ってる橋を流用すればよさそうですかね。
それぞれ連結判定をとって、島化。
後は連結判定に不要な辺を適当に島にくっつけていけば、島化した時点で何手必要かはわかるはずなので、それっぽくやれば終わりそうです。

まあ私はグラフ問題には本当に手も足も出ませんし、諦めてます。
割と何とかなりそうな部類ではあるので、解けるようになりたいですね……。

F問題

問題文の通りです。

言われた通りにやれば終わる（超難易度）みたいな問題だと感じてます。
素直に前から見ていくと多分無理で。配列を用意して後ろから何とかやればできそうだな、と挑戦はしたものの、サンプル程度なら抜けられますが、なかなか上手くはいきませんでした

ただ、この問題。手前に入るか、奥に入るかの2通りでしかないですよね。
だから最初は二分木を作ろうとしてたんですけど、これで解けるのなら、私のグラフに対しての知識が弱すぎですね……。

G問題

こんなに行けそうなのに無理なんだ。って問題です。

要するに等差数列になるリストを作れ。って問題なんですけど、等差数列[A, B, C]は$2B = A + C$が成立する仕様を使って、二重ループ + 二分探索でいけないもんなんだろうか？と思っていましたが流石G問題。余裕のTLEですね。
これは本当に手も足も出ませんね。いつかできるようになるんだろうか。