ABC444C - AtCoder Riko
https://atcoder.jp/contests/abc444/tasks/abc444_c
忙しくて先週は記事を書けませんでしたが今週は書きます。
コンテスト中の動き
ABはすぐ終わり、Cを見てしばらく考えてわからず、Dを見てある程度解いてみてどうしても合わなくて悩みました。それからEも一応見て方針は思いつきそうでしたが細部まで詰め切れるかどうか、正しく実装できるかどうかわからなかったこと、CもDも放置してEに行っても盛大に失敗する可能性が高いことを考えて無視しました。
一度は完全にコンテストを諦めて2完のまま終わる覚悟をしましたが、パソコンから離れて家事をしているときにふとC問題の解法を思いつきました。急いで戻ってきて、そしてなんとか正解することができました。奇跡的に閃いてそれでようやく3完……2回連続の茶色パフォーマンス……直視したくない現実ですが受け止めていきます。
考察1
最初僕は全探索系の問題だと考えました。お菓子の長さの総計は sum(A) で求められるので L の値はその約数になります。しかし、sum(A) は最大で $ 3 \times 10^{14} $ にもなりますから約数の数はかなり多くなります。以下の「高度合成数の一覧」を見ると……$ 1.8 \times 10^4 $ 個ぐらいはあるでしょうか。
そして、個々の L 候補に対してその値が正しいかどうかを確かめるのには最大 O(N) の計算量がかかります。$ 1.8 \times 10^4 $ に $ 3 \times 10^5 $ を掛けると TLE でしょう。というわけで却下です。
考察2
次に考えたのは、配列 A の中からいずれか 2 つを選んで合計値を見て、その値が作れるかどうか……これも明らかに無理ですね。選ぶ段階で $ N \times (N-1) $、作れるかどうかでさらに計算量がかかります。このあたりで諦めました。
考察3
というわけで諦めたのですが、ふと次の解法を思いつきました。図に描いてみると、割れる前の AtCoder りこはこういう形になっています。
先ほどまでは長さ L に着目していましたが、本数 M の方を見てみますとこちらは取りうる範囲が L よりはるかに狭くなります。これを基準に全探索できるのでは？と思って次のようなコードを書きました。
実装
N = int(input())
A = list(map(int, input().split()))
D = dict() # 何の長さが何本あるかを表す
for a in A:
if a not in D:
D[a] = 0
D[a] += 1
sumA = sum(A)
ans = []
for m in range(max(N//2, 1), N+1):
if sumA % m != 0: # 約数じゃないやつは省く
continue
l = sumA // m
# 後は実際に作れるかどうかを試す。
flag = True
for a in A:
if a == l: # 折れていない AtCoder りこ
continue
# 相方になる断片が存在していなければ NG
if l-a not in D:
flag = False
break
# 相方になる断片が同数あれば OK, なければ NG
if D[a] != D[l-a]:
flag = False
break
if flag:
ans.append(l)
ans.sort()
print(*ans)
これでACできました。実行時間も 181ms と高速です。しかし……終わってからあらためて見返すと $ O(N^2) $ になってしまっている気がします。コンテスト中は夢中で気づかなかったのですが。条件を満たさないものを早めに排除して break していったおかげでたまたま速かったのかもしれません。いづれにしてもラッキーでした。
公式解説より
あとで公式の解説を読み、ある事実を知らされました。折れなかった AtCoder りこが無かった場合、一番短いやつと一番長いやつを足せば合計長さ L になるはずということです。以後、短いやつと長いやつを順次ペアにしていけばいいです。なぜこんな単純なことに気づけなかったのか……目から鱗でした。
どうすれば気づけたのか？
終わってから考えてみると、僕は入出力例3をほぼ見ていなかったことに気づきました。急いでいたのもありますが、どうせ見ても仕方ないだろうと高をくくっていたのです。それがまずかった気がします。
6
10 187 344 100 434 257答 : 444
……見ていれば気づけたかというとやっぱりなんともいえませんね。ただ、最初にソートしておけば気づけた可能性はあります。
6
10 100 187 257 344 434答 : 444
実際のところこれで僕が気づけたかどうかはわかりませんが、僕の中で考察の基本として
- 入力例にヒントがあることもある
- ソートしても問題ない場合はとりあえずソートしてみる
というのがあるので、それに忠実に丁寧に考えていけばよかったのかもしれません。
あるいは、実際に 〇゛○〇゛りこ を用意して割ってみればよかったのかもしれません。