ARC095に参加した

ARC095に参加しました。CとDを40分くらいでやっつけて、Eに1時間取り組むも解けず。 レートは935→1010になりました。 ようやっとレート4ケタの世界へ。単調増加し続けていきたいものです。

前回の記事：

amalog.hateblo.jp

振り返り

C: Many Medians

よく考えずにnumpyのmedianで毎回算出するコードを投げつけて無事TLE。アホや……

抜いた1個が半分より小さければ番目を、半分より大きければ番目を投げればOK。

import numpy as np

N = int(input())
X = np.array(list(map(int, input().split())))
idx = X.argsort()
res = np.zeros(N, dtype=int)
res[idx[:N//2]] = X[idx[N//2-1]]
res[idx[N//2:]] = X[idx[N//2]]
for i in range(N):
    print(res[i])

D: Binomial Coefficients

には最大のやつ、にはの半分に一番近いやつを選べば最大になるという直感に従ってAC。

結果的には直感が正しかったわけだけど、こういうのって証明する前に提出していいんだろうか。

N = int(input())
A = sorted(map(int, input().split()))

n = A[-1]
r = sorted(A[:-1], key=lambda x: abs(x-n/2))[0]
print(n, r)

E: Symmetric Grid

実はARCに参加するようにして初めてE問題を解く(笑)

考えたこととしては、

• 行の交換、列の交換をしても、同じ行・列に含まれている文字は変わらない
• 点対称を作るためには同じ文字セットを持つ行・列のペアが必要

ということでペアを探索して余りが行・列ともに1以下ならOK、みたいなコードを書いたわけですが無事WA。

よく考えてみるとこれらは必要条件に過ぎないんだよなぁと思って反例を探したけど思いつきませんでした。

想定解は行の並べ替えを全探索して、列はよしなに並べ替えるらしい。

反省

C、Dが簡単だったので1時間以上Eに取り組めたのに解けなかったのは悔しい。

思いついた解法が上手く行かなかった時、全探索→場合の数を上手く減らす、っていう基本の流れを1回も確認しなかったのは反省。