[AtCoder 参加感想] 2019/11/24:ABC 146

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

スポンサーリンク

全体感想

37分6完1ペナルティで22位でした。

37分は、過去のABC(6問)での自己べタイムみたいです。1ペナがもったいなかったけど、上出来ですね♪

はじめにEを7:30で提出したのですが、ここでバグを出していました。FA狙えたっぽかったな、惜しい(提出結果を見守らず問題Aに進んだのもFA逃しの要因)。

問題Cを誤読していて死にそうになりました。

問題A – Can’t Wait for Holiday

weekday = 'SUN,MON,TUE,WED,THU,FRI,SAT'.split(',')
dic = {x:7 - i%7 for i,x in enumerate(weekday)}

{‘SUN’: 7, ‘MON’: 6, …}
としても良いですが、こんな感じで書いてみました。

問題C – Buy an Integer

しばらく、$d(N)$ を、「$N$ の各桁の和」と勘違いしていました(これでも解けますが、Eくらいありそう)。昨日、誤読で反省したばかりだというのに…。

・桁数を固定して考える
・値段に単調性があるので2分探索

などの方法があると思います。後者で解きました。自然数 $N$ の桁数は、

len(str(N))

でOKです。

問題D – Coloring Edges on Tree

グラフの辺彩色といえば、知識としては

[Vizing の定理] 辺彩色数は、$\Delta(G)$ または $\Delta(G) + 1$ に等しい
[Konig の定理] 2部グラフの辺彩色数は、$\Delta(G)$ に等しい

などを一応装備しています。木グラフは2部グラフなので、辺彩色数は $\Delta(G)$ に等しい、と思考しました。いや、流石に木グラフなので、もっと簡単事情ですがw

今回は、適当に上から塗っておけばよいです。

(1) 色情報の持たせ方

今回のように、木グラフの辺に関する情報を扱う場合、「頂点を見ている」のか「辺を見ている」のかで思考が乱れやすいです(主観)。なるべく概念の定義を厳密にすること、なるべく頂点に関連付けることなどを意識します。根付き木と見たとき、根以外の頂点は、唯一の親を持ちます。このことから、

・$v$ の親が $p$ であるとき → color[v] に辺 $pv$ の色を持たせる

と定めて色を管理しました。

(2) 再帰を避ける (Pythonを中心に)

グラフのdfsは、入力次第で再帰回数がかなり深くなり、適当な回数を超えるとエラーになります。深い再帰を扱う方法として、

import sys
sys.setrecursionlimit(10 ** 7)

というような対策方法が1つ存在します。ただこれも常に宣言通りの再帰上限で挙動するわけではなく、環境次第で上手く動作しなくても文句は言えません。

もうちょっと頑張って再帰上限回数をいじる方法も存在しますが、事情は大きく変わりません。

詳しい説明は省きます(ちゃんと書けるほどの理解がないので)が、基本的には関数の深い再帰は負荷も大きく、パフォーマンスが悪くなりやすいです。(そもそも、デフォルトの再帰上限回数が小さく設定されている理由を想像してみましょう。単なる嫌がらせ?流石に違うはずで。)

私は最近では、sys.setrecursionlimit は全く使わない方向にシフトしています。木グラフであれこれする場合は、

・親から子側へ向かう、topological 順序を計算する(リストをstackとして使う)。
・for ループの形で、親側・あるいは子側から処理していく。

という手順を踏みます(同時にやることもできるけど、処理を切り分けた方が頭を使う量を減らせると思います)。

今回の問題の実装例:
他には例えば:EDPC V – Subtree

現状、これをやっただけでも、Python (or PyPy) での実行速度最速になる割合がかなり高く、関数の深い再帰を避けている Python 競プロ勢はほとんど居ないと思われます。ぜひお試しください。

※ 深い再帰でエラーが出たり、パフォーマンスが下がるのは、Pythonに特化した話ではないです。

問題E – Rem of Sum is Num

公式解説とだいたい同じかと思います。$A_i – 1$を改めて $A_i$とおくことで、
・要素の和を $K$ で割った余りが $0$. 
・長さが $K$ 未満
を満たす区間を求めればよいと分かります。
区間内での要素の和を検出したいので、とりあえず累積和は作ります。また、$0$ 番目に余分な $0$ を入れておきます。
・A = [0, 3, 1, 2, 4] → Acum = [0, 0, 3, 4, 6, 10]
こうしておくことで、
・区間和を全て調べる $\iff$ Acum[r] – Acum[l] を全て調べる(ただし $l < r$)
という形で扱えます(A[0] を初項とする区間の扱いを気にしています)。
あとは、常に最新 $K$ 件の Acum[l] の度数分布を持ちながら $r=1,2,\ldots$ を調べるようにすればよいです。「最新 $K$ 件の情報」を維持するためには、$r$ を増やしたときに、追加と削除を 1 件ずつ行うようにすればよいです。
今回は、「Acum[l] を K で割った余り」の度数分布を持つことになります。$K$ が巨大なので、Python なら dict / defaultdict などを利用すると良いと思います。リストで持つと巨大すぎてダメです(1ペナ)。

問題F – Sugoroku

「辞書順最小」という課題です。これを実現するには、とにもかくにも、「初手をなるべく小さく抑えるにはどうすればよいか」を考えなければいけません。
そのためには、「1歩進んだら、あと何回で行ける?」「2歩進んだら、あと何回で行ける?」というような自問自答を行う必要があります。したがって、
・各地点を出発地点としたときに、ゴールまで何回かかるか?
を求めていこうという気持ちになります。(「ある地点まで何回かかるか」ではなく)「ゴールまで何回」なので、ゴールに近いところが最も簡単で、後ろから遡って計算していきます。
ついでに、
・各地点を出発地点としたときに、ゴールまで最小回数・辞書順最小で移動するときの移動先
も同時に求めていくようにしておけば、経路復元ができます(各地点の移動先あるいは移動前の管理をするというのは経路復元の一般的な手法)。
ベストな移動先の検出は、移動回数が $M$ 回以下であることも踏まえて、heapqで行いました。
・後ろからみる。
・各 n に対して、(移動回数, n) のタプルを heapq に入れていく
・計算では、heapの最小値を見て、使える(移動距離が $M$ 以下)なら使う。使えないなら今後二度と使えないので捨てる。
あとは、禁止地点は INF を入れるなどして実装しました。

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