ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

ABC110 参加記録&解説

AtCoder Beginner Contest 110 - AtCoder

もはや参加記録というより解説メインになっているので、今回からタイトルに「解説」って付けます。

結果は20分台全完で11位。1桁順位の壁は厚い。

f:id:betrue12:20180924005239p:plain

A - Maximize the Formula

A - Maximize the Formula

解法

作れる式の形は xy+z または x+yz しかなく、どちらも「10の位の数字が1つ、1の位の数字が2つ」という構成になっています。入力のうち一番大きいものを10の位に割り当てると最大になります。

ACコード

B - 1 Dimensional World's Tale

B - 1 Dimensional World's Tale

解法

 X x_{1}, ..., x_{N}」 が左に、「 Y y_{1}, ..., y_{m} 」が右にキレイに分かれればよいです。 X 側の最大値  X_{\max} Y 側の最小値  Y_{\min} を出して、 X_{\max} \lt Y_{\min} であれば No War です。

ACコード

Submission #3250414 - AtCoder Beginner Contest 110

C - String Transformation

C - String Transformation

解法

「2つのアルファベットを選んで入れ替える」という操作を繰り返すと、どのようなことが起こるでしょうか。

  • abに、baに置き換える」という操作を行うと、元文字列の ab に、 ba になる。
  • その状態からさらに「bcに、cbに置き換える」という操作を行うと、元文字列の ac に、ba に、cb になる。

このように繰り返していくと、26文字のアルファベットが、それを1対1の対応で置換されたものに置き換わります。ここで言う「1対1対応」は数学用語には「全単射」というものですが、このレベルの問題であれば直観的な「1対1対応する」のイメージを持っていれば十分です。つまり、

  1. 同じ文字が異なる文字に変換されない。
  2. 異なる文字が同じ文字に変換されない。

の両方が満たされていれば Yes です。

実装においては、変換をmapなどで管理して  S, T の文字を順番に調べていき、同じ文字なのに前と違う変換先になっていれば1の理由で No 。最後に変換先の文字を全部調べて重複があれば2の理由で No とすればよいです。他に、 S \to T T \to S の両方について1だけを調べる、という方法もあります。

ACコード

D - Factorization

Submission #3253308 - AtCoder Beginner Contest 110

解法

 a_{1} \times a_{2} \times \cdots \times a_{N} = M が成り立つということは、 a_{1}, ..., a_{N} M の素因数を分配したものになっています。含まれる素因数が異なれば必ず値は異なるので(素因数分解の一意性、ですね)、この問題は「素因数の分配の仕方は何通りあるか?」と言い換えることができます。また素因数それぞれについての分け方は独立なので、全部の素因数について分配の仕方を考えて、それを全て掛け算すればよいです。

f:id:betrue12:20180924015211p:plain

ある素因数を  p とし、それが  M k 個含まれているとします。求めたいのは「 a_{1}, ..., a_{N} に、 k 個の区別されない要素を分配する方法は何通りあるか?」ですが、これは「重複組合せ」と呼ばれるもので、結果は  _{N-1+k}C_{k} になります(リンク先に、「なぜそうなるのか?」を丸と仕切りを用いて解説した記載もあるので見てみてください)。これを全て掛け算すると答えになります。

…とはいえ、この問題を解いて実装する上では

  • 重複組合せについての公式を持っている(知識)
  • 素因数分解できる(ライブラリ)
  • 比較的大きな数において、  _{N-1+k}C_{k} \mod (素数) 、またはこれを計算するのに必要な階乗と階乗逆元を前計算できる(ライブラリ)

これらの材料が必要になります。知識・ライブラリともに非常によく使うものなので、是非準備しておきましょう。

ACコード

さいごに

Cは考察ミスで「単射であればいいのかな?」と考えていたため、時間を余計に使ってしまいました…

Dはほぼ知識問題と言っていいと思いますが、かなり重要知識なので、本番解けなかった人も是非ライブラリ含めて身につけておくと良いと思います!