AtCoder ABC132 参戦記

AtCoder の ABC 132 に参戦しました。

atcoder.jp

結果は 35 分弱で ABCD まで解けてパフォーマンスは 1496。E 問題が解けなかったわりにはパフォーマンスは伸びましたがまたしても水色落ちとなりました。

感想

A 問題

A 問題史上最難？if 文で比較するのも面倒だったので、各文字の出現回数をカウントして 0, 2 以外が出たら NG とした。

B 問題

単純に for ループ回すだけ。
A より簡単では...？

C 問題

ソートして - が答え。

D 問題

めんどくさい数え上げだが Red の数を 、分割数を とおくと、

• 分割数が を超えてしまうと実現不能なので組み合わせ数は 0
• Blue を分割する組み合わせ数 x それを可能にする Red の配置の組み合わせ数を [t]x: i] について出力する
• Blue を分割する組み合わせ数は
• Red の配置の組み合わせはめんどくさいが、 個が拘束されていることを利用すると 個のボールを 個の箱に分配する問題になって
• nCk の計算が間に合わないと予想されるので階乗を前計算する。それを使って を高速に求める。(逆元はその都度求めたがこれも用意すればさらに早い)

E 問題

コンテスト中は3 hop 先への有向グラフを構築しようとして TLE が取れなかった。
最終的に AC した考え方は以下の通り。

• ダイクストラ法がベース
• ダイクストラ法だと一度到達した頂点からは探索しないが、本問題では S からの到達を とすると で到達したことがあればその頂点からは探索しない

F 問題

たぶん DP, きっと DP