数弱がつらい話(ABC280感想)

 

この記事でやること

Denso Create Programming Contest 2022 Winter(AtCoder Beginner Contest 280) - AtCoder の参戦記(?)を書きます。多少は問題解説を入れますが、基本的にはただの日記です。

 

注意

提出コードのリンクを貼っていますが、全てPyPy3での実装となります。

コンテスト中に提出したものをそのまま貼ってあるので、可読性を意識せずに書いていることをご了承ください。←意識しなくても書けるようにする努力をしてください。

 

0回戦敗退

絶起しました。「ちょっと昼寝」のつもりが、目が覚めたら21:30でした。晩御飯も食べていなかったため、諦めて23:00からバチャで参戦。

コンテスト当日に昼寝を取る場合はアラームを設定しましょう。(自戒)

 

A問題

行ごとに input().count("#") して合計を求めました。

提出コード

 

B問題

数列 S の先頭に 0を加えて階差数列を取りました。

提出コード

 

C問題

 S, T の先頭から見ていき、 S_i \neq T_i となる最小の i を求めればよいです。 T の末尾に挿入されるケースに注意しましょう。

コンテスト中の私は問題文中で S, T のどちらに挿入したのかわからなくなったため、末尾の処理をどちらに挿入されていてもいいように書いたようです。頭が悪い。

提出コード

 

D問題

AC間に合いませんでした。(は?)

 K を試し割り法で素因数分解しておいて、各素因数ごとに N を求めてそれらのmaxを求めればよいです。

一生計算式をバグらせてました。数弱つらい。

提出コード

 

E問題

期待値dp とかいうやつです。

 \text{dp} [ i] := 体力 i のモンスターを倒すための攻撃回数の期待値

とすれば、

 \text{dp} [ i] = 1+\text{dp} [ i-1 ] * (1-P/100) + \text{dp} [ i-2 ] * P/100

と表せます。

 

modの割り算は逆元の掛け算で計算します。

フェルマーの小定理より、整数 p の倍数でない整数 a の、 \text{mod} ~p での逆元は a^{p-2} と表せるので、Pythonならpow( a,  p-2,  p) とすることで求められます。

提出コード

 

F問題

有向グラフとして見たとき、 X_i, Y_i の弱連結成分に「重みの和が0でない無向閉路(逆辺は重みを-1倍する)」が存在する場合にinfを出力します。

 

ぐるぐる回れば無限にポイントが得られる

そのような無向閉路の検出は重み付きUnioni-Findというデータ構造を用いれば実現できます。普通のUnion-Findでの経路圧縮時に重みも圧縮するだけなので、そんなに難しくはないです。自前の重み付きUnion-Findの実装では、リンク先の記事とは異なりunion by size による実装をしております。

提出コード

 

G, Ex問題

わかんないです…。

 

感想

D問題が通せないのは、数弱にも程があると思いました。

今までも茶、緑diff 程度の数学問題で沼ることが結構あり、前回のD問題でも1階微分して=0となる解を探すだけなことに気付かず、三分探索を書いてバグらせてました。そもそも傾きの単調性を調べるために2階微分してたのに、その時点で何故気付かないんですかね?

(ちなみに、これまでで最も酷かった数弱事件はABC266-Bです。ACしたのはコンテスト終了2分前らしいです。)

数弱を克服したいと思いつつも一生改善できていないことを実感するABCでした。

 

最後に

毎週土曜20:45にアラームが鳴るよう設定しました。皆さんも絶起には気をつけましょう。