[AtCoder 参加感想] 2019/10/27:ABC 144

  A B C D E F
問題文
自分の提出
結果 AC AC AC AC AC AC

スポンサーリンク

全体感想

63分6完で39位でした。

atcoder 初参加から、ちょうど半年です。だから何?何もありません。

今回のセットの感想
・F:難しかったけど面白かった!
・E:最近のEにしては易しめ?
・D:最近のDにしては難しめ?

面白かったです。順位も最近の中では高い方でした。
Fで40分。ほとんど詰まらずやり切ったつもりで、割と上出来だと思うのですが、まだまだ最上位には及びませんね。

問題B – 81

9×9に出現する数のsetの作成:

se = set(x*y for x in range(1,10) for y in range(1,10))

内包表記がお手軽。

問題C – Walk on Multiplication Table

$N$ の約数を検出するには、$\sqrt{N}$ まで試し割りすればよいです。こういうのを $10^6$ 回のループを回すと python では遅くなりがちです。単純な並列処理は numpy が簡潔で、コード量も少ないです。

U = 10**6 + 100
x = np.arange(1,U,dtype=np.int64)
div = x[N%x==0]

U以下の約数の一覧が手に入ります。$\sqrt{N}$ を上限としてもよいかと思います。定数を上限にするならば、$10^6$ まででよいですが、$1$ 足りない等の処理のミスを予防するために少し余分に計算しています。なお、提出コード実行時間の9割くらいが numpy を import するところにかかっていて、主要の計算部分は 10ms 単位なので、TLEにはまだまだ余裕があります。

問題D – Water Bottle

数学に基づく基本的な計量ですね。

基本的な三角関数やそれに基づく立式などは、ある意味、競プロテクニックの大部分よりも世の中で必要とされうる率は高そうで、こういうスキルをきちんと問うていくの非常に良いと思います。
一応、理解の役に立ちそうな図を描きました。奥行の $a$ をかければ体積です。

問題E – Gluttony

$A$ の値が大きい人ほど、最終値が大きいとしてよいです。追い越している場合、追い越さないとしても操作回数は変わらないので。
※ [10,5] → [3,4] とするくらいなら、一度横並び [5,5] になっているはずなので、役割を入れ替えられる。
最終的なAの値が確定すれば、操作後の割り当ては「大きいAを小さいFに割り当てる」です。これも、証明が必要なら「そうでないとすると入れ替えても損にならない」型の証明が使えます。
したがって、初めから、「大きいAの人が小さいFを担当する」となります。
あとは実際に修行手順をシミュレートしていこうとすると、 $K$ が大きすぎて厳しいです。(「現時点での $a*f$ が大きい $a$ から処分していく」というアルゴリズムを実装できるけれど、$K$ が大きいので難しい)。逐次的な貪欲というよりも、最終状態が操作回数のみに依存(順序に依存しない)ことを利用して、操作回数列だけを上手く割り当てる必要がありそうです。
ここで二分探索の出番で、目標スコアを定めると、各Aの必要修行回数が定まり、条件を満たすかどうかが確認できます。
今回も、たくさんの値に対して並列に必要修行回数を計算すればよいので、numpy で実装するのがお手軽(コーディングが楽)かつパフォーマンスも良いです。
Asum = A.sum()
def test(x):
    # 全員がx秒以下に収めるための必要コストがK以下である
    return Asum - np.minimum(A,x//F).sum() <= K

問題F – Fork in the Road

「ループがあったらマルコフ過程で難しいやつだな?」などと少し悩みましたがDAG(directed acyclic graph)に関する問題でした。条件 $s_i < t_i$ が重要です。

1本の辺を切断したとしても、「もともとその辺を通っていた場合」の部分の計算が変更されるのみです。

・辺 $st$ を削除したとする。
・「頂点 $s$ に辿り着かない場合の条件付き期待値」は変化しない。
・「頂点 $s$ に辿り着く場合の条件付き期待値のみが変化する」

ことが分かります。したがって、

・$p = $頂点 $s$ に辿り着く確率
・$x = $頂点 $s$ から出発してからゴールするまでの移動回数期待値(辺削除前)
・$y = $頂点 $s$ から出発してからゴールするまでの移動回数期待値(辺削除後)

としたとき、全体としての移動回数期待値は、$p(y-x)$ だけ変化します。よって、$p,x,y$ が計算できる程度の情報を準備してあげればよいです。これは

・各頂点 $s$ への到達確率(手前から順に計算可能)
・各頂点 $s$ を出発点としたときの、ゴールまでの移動回数期待値(後ろから順に計算可能)

の2つのデータを持つことで達成できます。計算量は $O(N+M)$ です。

タイトルとURLをコピーしました