ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ABC053 D - Card Eater

問題
提出コード
素直に、余分なカードを最高効率で食べていくことを考えます。
1回の操作で、確実に余分なカードを2枚減らすことができます。
余分なカードは最低でも2枚あるので、そのようなカードが2種類あれば、数字をi,j(i<j)とすると、
(i,i,j)
と選べば食べる2枚のカードは余分なカードになります。
また、1種類のみでも、3枚以上存在していた場合は、
(i,i,i)
と選ぶことで2枚のカードは余分なカードになります。
これを繰り返していくと、最後に余分なカードが1枚だけになる可能性があります。
この場合のみ、任意のカードを選び、
(i,i,k)
と選ぶ必要があります。
ということで、2枚以上存在している、余分なカードの枚数を数え、奇数だったら+1をしたら答えになります。

ABC053 C - X: Yet Another Die Game

問題
提出コード
誤読をしないように注意しましょう。
x以上になればいいので(ちょうどでなくて大丈夫です!!!)、できるだけ大きい数字をひたすらもってくればよいです。
ということで、6と5を順番に上の面に持ってくればよいです。
2回で1セットとみて、11点を加える操作とみなすことができます。
xを11で割り、2をかけたらこのパートの操作回数となります。
あとは、残り必要な得点が11未満になった場合のみを考えます。

  • 必要な得点が0の場合
    そこで操作は終了です。

  • 1以上6以下の場合
    最後に6の面を上にもってくればよいです(最初の操作で、5と6は好きな方から開始できるので、最後に6の面が上になるように適宜調整できます)。
    ということで、操作回数は+1されます。

  • 7以上の場合
    6点では足りないので、さらに5の面を上にして得点を重ねる必要があります。
    ということで、操作回数は+2されます。

最初の操作と、端数の操作の回数を足せば答えになります。

ABC052 D - Walk and Teleport

問題
提出コード

解法

この手の問題は、まずテレポートをする回数を固定しましょう。
ということで、テレポートする回数をk回とします。このとき、徒歩で移動する区間の個数はN-1-k個になります。
徒歩で移動する区間はどこになるかというと、区間の距離が小さい方から選んだN-1-k個になります。
前から順番に、徒歩でいくと決めた区間なら徒歩で1つ先の場所へ、徒歩でいかないと決めた区間は1つ先の場所へテレポートで移動すればよいです。
ということで、これを繰り返していると、結局は
 A×(X_i - X_{i-1} )\leqq Bならば徒歩で、そうでなければテレポートで移動すればよいことになります。
ということで、全ての区間について、距離にAをかけたものと、Bを比較して、小さいものを足していけば答えとなります。

ABC052 C - Factors of Factorial

問題
提出コード

解法

2~Nまでを素因数分解します。制約が1000までなのでO(N^{2})が余裕で間に合います。
そして、素因数の個数をそれぞれで記録しておきます。素因数分解したい数字をkとしたときに、j=2から順番に探索していき、kがjで割り切れる限り
あとは、答えとなる変数の初期値を1として、それぞれの素因数の個数+1をかければ答えになります。

ABC051 D - Candidates of No Shortest Paths

問題
提出コード

解法

a_i,b_iを距離c_iで通る辺M_iが使用されるには、a_ib_iの最短距離がc_iになっていればいいです。最短距離になっていない場合、a_ib_iを通るより最短距離になっているルートを通る方がいかなる場合にも距離が短くなるため、a_ib_iにおいての最短距離がc_iかどうかだけ調べればよいです。
ということで、辺の状態を保存し、それとは別にワーシャルフロイド法で全ての頂点間の最短距離を求め、最後に保存した辺が最短距離になっているかどうか調べればよいです。
最短距離になっていないものの個数が答えになります。
制約も、頂点の個数が100以下なので、ワーシャルフロイド法が間に合います。

グランディ数の問題の解き方メモ (ARC072 D - Alice&Brown)

あまりに苦手なので、やまさん(@yamasangamasan)に解き方のコツを聞いたのでメモしました。文章だらけなのでかなり読みづらいです...
グランディ数を使う問題は、
二人零和有限確定完全情報ゲームです(!)

AとBの2人がいて、ある操作行うようなゲームをします。お互いが最適な行動をしたときに、どちらが勝つか判定してください。
今回は以下の問題を例として使って行きます。
ARC072 D - Alice&Brown
XYは、便宜上X \leqq Yとしておきます。

基本方針

  1. 操作ができずに負けが決まる状態をグランディ数が0であるとし、小さいケースについてのグランディ数を求めていく
    後で詳しく述べます。
    先にグランディ数を簡単に説明すると、0のときは後手が勝ち、それ以外だと先手が勝ちになるようなものです(逆もあります)。

  2. グランディ数が0になるパターンとならないパターンの規則性に目星をつける
    ある条件を満たすとグランディ数が0に、満たさない時には0以外になる、というような規則性を探します。

  3. 先ほどの規則性によって求められる数が、実際に正しいグランディ数であることを証明する
    これは、2つのことを証明します。
    ある状態においてグランディ数が0であったときに、そこから1回操作をすると起こり得る全ての状態(以降は遷移先と表現します)についてグランディ数が0となるものが存在しないこと(もちろん、遷移先が必ず0以外になる、ということと同じです)
    ということと、
    ある状態においてグランディ数が0でないときに、遷移先にグランディ数が0となるものが少なくとも1つは存在すること
    の2つです。これは、帰納法を用いて証明することができます。

小さいケースのグランディ数を求める

ある状態Sについてのグランディ数を求めます。

  • Sのとき、なにも操作ができない状態ならばグランディ数が0となります。

  • それ以外の場合、Sの遷移先のうちどれか1つの状態をS'としたときに、あり得る全てのS'についてのグランディ数を求め、S'に存在しない数のなかで最小の非負整数となります。

今回の問題において、ありうるX,Yの状態を(X,Y)という表記をすると、
(0,0), (0,1), (1,1)はこれ以上遷移ができないのでグランディ数は0です。
(0,2)は(0,1)に遷移できます。(0,1)はグランディ数が0なので(0,2)のグランディ数は1になります。
(1,2)は(0,2)に遷移できます。(0,2)はグランディ数が1なので(1,2)のグランディ数は0になります。
(0,4)は(0,2)と(1,2)に遷移できます。この2つのグランディ数はそれぞれ0と1なので、(0,4)のグランディ数は2になります。

そして、グランディ数が0のときは後手の勝ち、それ以外のときは先手の勝ちとなります。
グランディ数が0のときは、必ず0以外の状態に遷移するしかなく、またグランディ数が0以外のときは必ず0となるような遷移が存在します。
なので、グランディ数が0でないような状態で自分のターンが回ってきたとき、グランディ数が0となるように操作をしてから相手にターンを回せば、必ず勝つことができます。

こうして求めたグランディ数について、どのような場合に0、どのような場合に0以外になるか、規則性を見つけます。
今回の問題における規則性は、
|X-Y|\leqq 1ならばグランディ数は0、それ以外なら0以外
という規則です。規則の見つけ方については、最後に簡単に述べますが、基本的には経験と発想力で見つけるしかないかと思います…


帰納法で示す

数学的帰納法で、2つのことを証明します。
ある状態Sにおいて、規則性を適用して求めたグランディ数をg(S)とします。このg(S)が実際のグランディ数と一致することは、以下の二つを示すことができればよいです。

  • ある状態Sにおいてg(S)=0であったときに、任意の遷移先S'についてg(S') \neq 0であること(もしくは遷移先が存在しないこと)

  • ある状態Sにおいてg(S)\neq 0のときに、遷移先S'g(S')=0となるものが少なくとも1つは存在すること

です。この2つを示すことができれば、g(S)は正しくグランディ数を求められていることになります。
今回用いる帰納法についての軽いおさらいです。ある自然数nに関する事柄(今回は上記の2つのことです)が成り立つことを、

  • n=1の場合に成り立つ

  • n=kのとき(もしくはn \leqq kのときに成り立つとき)に、n=k+1で成り立つ

の2つのパートに分けて証明します。
これを組み合わせると、n=1で成り立つのでn=2で成り立ち、n=1 (とn=2 )で成り立つのでn=3で成り立ち…と全てのnについて成り立つことができます。

帰納法を用いてどうやって証明するかというと、まずは全ての状態をグループ分けしていきます。そのときに番号を割り振り、nを決めていきます。
今回は、n = X+Yとします。(0,0)はn=0、(0,2)と(1,1)がn=2、といった具合です。
ここで、nの決め方で注意するべきポイントが存在します。

  • ある状態においてn=kだったとき、その遷移先ではnk未満であること

です。でないと、証明の際にループをしてしまい証明できなくなります。
例えば、n=max(X,Y)のように定義をしてしまうと、(2,2)の遷移先に(0,3)が存在するため、n=2の遷移先にn=3が存在することになってしまいます。これでは証明ができません。
規則性を探す実験の段階で、このnについても気を配りつつ探していくといいでしょう。
ということで上記のことに気を付けながらnを定義していきます。
ということで、定義したnをもとにして、見つけた規則がグランディ数を求めることができていることを証明していきます。
規則性を振り返ってみます。

  • |X-Y|\leqq 1ならばグランディ数は0、それ以外なら0以外

です。これを適用して求めた数が、

  • ある状態Sにおいてg(S)=0であったときに、任意の遷移先S'についてg(S') \neq 0であること(もしくは遷移先が存在しないこと)   

  • ある状態Sにおいてg(S)\neq 0のときに、遷移先S'g(S')=0となるものが少なくとも1つは存在すること

という2つの条件を満たしていくことを示していきます。

  • n=1の場合に成り立つ
    n=1とは限らず、小さい数ケースについて成り立つ、でも大丈夫です。
    小さいケースは最初に実験をしていれば、その規則が実験結果と等しくなっていることで証明になります。
    今回は、n=0,1,2についてまとめて証明します。

[1]. n=0
(0,0)のみです。g(S)=0です。遷移先が存在していないのでこれは条件を満たします。

[2]. n=1
(0,1)のみです。g(S)=0です。これも遷移先が存在しません。

[3]. n=2
(1,1)および(0,2)です。前者はg(S)=0、後者はg(S) \neq 0です。(1,1)は遷移先が存在 しません。(0,2)の遷移先には(0,1)があり、これはg(S')=0なので条件を満たします(XYは、便宜上X \leqq Yとしていたので、本来なら(1,0)に遷移をするのですが(0,1)と表記しています)。

ということで、n=0,1,2の場合は条件を満たしていることがわかりました。

  • n=kのとき(もしくはn\leqq kのときに成り立つとき)に、n=k+1で成り立つ
    ここがふんばりどころになります。うまくn\leqq kの条件を利用できるようにして当てはめていきます。今回はあまりこの条件は必要ないですが…
    k+1 \geqq 3の場合についてのみこれが示せればいいです(0,1,2は証明済みのためです)。
    このとき、X,Yのうちどちらか片方はすくなくとも2より大きく、必ず操作ができます。
    X\leqq Yという条件をたてていたので、Yを操作することを考えていきます。
    X=YX+1=YX+1 \lt Yの3つのパターンに分けることができます。最初の二つは、g(S)=0で、最後のパターンのみg(S) \neq 0です。

  • X=Yのとき
    Yからpだけ減らし、Xにその半分を追加するとします。
    このとき、(Y-p, X+\frac{p}{2})となります。
    X=Yであることから、(X+\frac{p}{2}) - (Y-p) = \frac{3p}{2}となり、p \geqq 2であることから、3以上の差が生まれます。ということで、遷移先はXYの差が必ず1より大きいので、g(S') \neq 0です。

  • X+1=Yのとき
    上と同じことを考えます。
    Yからpだけ減らし、Xにその半分を追加するとします。
    このとき、(Y-p, X+\frac{p}{2})となります。
    この差は、(X+\frac{p}{2}) - (Y-p) = \frac{3p}{2}-1となり、差は2以上です。
    よって、g(S') \neq 0です。

  • X+1 \lt Yのとき
    Yからpだけ減らし、Xにその半分を追加するとします。すると、差は次のようになります。
     (Y-p) - (X+\frac{p}{2})  = Y-X-\frac{3p}{2}
    |Y-X-\frac{3p}{2}|\leqq1となるようにpを決めます。
    p=\frac{(Y-X+1)}{3}×2とすると、遷移先のX,Yの差が1以下になり、g(S')=0になります。

ということで、全てのX,Yのペアにたいして、n=k+1のときに条件を満たすことがわかりました。
ので、

  • |X-Y|\leqq 1ならばグランディ数は0、それ以外なら0以外

という規則はめでたくグランディ数を求めていることになりました。
あとは、これをもとに答えを出力していけば答えとなります。

規則性の見つけ方

グランディ数の規則性の見つけ方は、経験によるものが多いです(やまさん談)。
問題の操作でどんなことをするかによって、ある程度目星をつけることができるみたいです。
一例を以下に示します。もちろん例外もありますので、頭の片隅に入れておく程度がいいかと思います。あくまで経験による感覚的なものですので、違っている場合もあります。ご了承ください。

  • 2つの数字を操作するパターン
    今回の問題のパターンです。このパターンの場合、
    2つの数字を式で表した結果が規則になっている場合が多い
    みたいです。特に、
    操作において、片方で減算してもう片方で加算、のような操作をすると2つの数字を加算、もしくは減算した式が規則になることが多いそうです。
    もし操作が、掛け算や割り算だった場合は、規則に掛け算や割り算、余りなどが絡むことが多いそうです。

  • 文字列を扱うパターン
    1文字ずつ減らしていく操作ならば、文字列の長さの偶奇が基本的に絡んできます。

  • 終了条件が多いパターン
    終了条件だけをみて、何かしらの規則が見つかることが多いです。


おそらくこれだけでなく、膨大な量のパターンがあると思います。経験していくしかなさそうです…
あとは、この問題に限ったことではないですが、小さいケースにコーナーケースが潜んでいることがありますので注意をしましょう…
これらをもとにして、問題の時間制限内に答えを見つけられるような計算量の規則を探していけば、この手の問題に答えることができるようになります(といいですね!)。

終わりに

グランディ数は個人的にあまり見かけない問題ではありますが、解けるようにしておくとだいぶ変わってくるかなと思っているので、このメモをもとに自分も解けるようにしていきたいですね…