2018-12-29

ABC020 D - LCM Rush

問題
 提出コード(100点)
提出コード(満点)
100点から満点にもっていくことができず、解説を見ました…
言われれば確かにそうだけど～って感じですね。

解法

まずは100点までです。
$K$ の制約が少ないので、 $K$ について何かをするんだろうな、という気持ちになります。
すると、 $N$ までの数の中を、 $K$ で割った余りによって分類すると、
そのあまりが等しい数については、最大公約数も等しいことがわかります。
ここで、 $x$ と $y$ の最小公倍数 $LCM(x,y)$ は、おなじく $x$ と $y$ の最大公約数を $GCD(x,y)$ と表現したとき、
$\frac{xy}{GCD(x,y)}$
と表すことができます。
ので、 $K$ で割った余りが $x$ となるような数の総和をもとめ、そこに $K/GCD(x,K)$ をかけてあげれば、 $K$ で割った余りが $x$ となるような数と、 $K$ の最小公倍数の総和が求められます。
これを、全ての $x$ に対して行えば、 $O(K)$ でこの問題を解くことができます。
$K$ で割った余りが $x$ となるような数は、
$iK + x$ と表記することができます。
ここで、 $i$ は $0$ 以上 $(n-x)/K$ (切り捨て)以下の数となります。
$p = (n-x)/K$ とおくと、
$K$ で割った余りが $x$ となるような数の総和は、次のような計算式で求められます。
$px + \frac{Kp(p+1)}{2}$
ということで、
$(px + \frac{Kp(p+1)}{2}) 　\times \frac{K}{GCD(x,K)}$
を $1~K$ の $x$ に対して行えば、答えを求めることができます。 $10^{9}+7$ で余りをとるタイミングや、割り算のタイミングに気を付けましょう。
ということで、ここまでは今回自分が自力でできた部分です。
ここから先は、素因数分解やらなんやらをするのかなぁと思っていたのですが…
解法自体は解説そのままです。
結局、 $GCD(i,K)$ のパターンは、 $K$ の約数にしかならないので、 $1$ ~ $N$ の $x$ について、 $GCD(x,K)$ のパターンによって分けて総和を求め、あとは上と同じようにその総和と $\frac{K}{GCD(K,x)}$ の積を求めていけば答えが求まる、というものです。
そのために、まずは $GCD(K,x) = g$ となるような $x$ の総和を求める方法を考えてみます。
これは、 $GCD(K/g,x/g) = 1$ となるような $x/g$ の総和を求め、最後に $g$ 倍したものと同じになります。この総和は、包除原理を用いると、うまく計算することができます。
$K/g$ を素因数分解し、素因数の種類を洗い出します。今回は、例として3種類の素因数が存在し、 $a^2 b^3 c^4 = K/g$ だったとします。
このとき、まずは $1$ ~ $x/g$ についての総和を求め、そこから $GCD(K/g,i) \neq 1$ となるような $i$ を引いていくことを考えます。
そして、この後は

素因数を奇数種類使用した数の倍数の総和を減算し、偶数種類使用した数の倍数の総和を加算する

という操作を行います。
今回の例だと、 $a,b,c$ および $abc$ それぞれについて、 $1$ ~ $x/g$ の中での倍数の総和を求め、減算し、 $ab,bc,ac$ の倍数の総和については加算し直します。また、同じ素因数が2つ以上含まれているような場合( $a^2bc$ など)は、無視します。
総和を求めるときは、上で行ったような総和の求め方と同じようなことをします。
$a$ の倍数は、 $p/a$ 個(切り捨て)存在するので、これを $j$ 個としたときに、
$\frac{aj(j+1)}{2}$
という計算をすれば、総和を求めることができます。
また、素因数の種類および、同じ種類の素因数が2つ以上使用されているかどうかは、よくある素因数分解のアルゴリズムを用いれば、容易に調べることができます。

さて、 $GCD(K/g,x/g) = 1$ となるような $x/g$ の総和を求めることができたので、あとは $g$ 倍すれば $GCD(K,x) = g$ となるような $x$ の総和になります。
あとは、全ての $g$ について同じことを繰り返せば終わりです。 $g$ は、先ほどと同様よくある素因数分解等のアルゴリズムのようなものを使えば、 $O(\sqrt{K})$ で洗い出すことができます。
ということで、これらの式をバグなく気合で組み立て計算すれば、この問題を解くことができます。

2018-12-28

ABC115 D - Christmas

再帰前計算動的計画法(DP)

問題
 提出コード
まずは、レベル $L$ バーガーをすべて食べたときの、食べる全体の枚数および食べるパティの枚数を求めます。
食べる全体の枚数を $a[L]$ とすると、
$a[L] = 2 \times a[L-1] + 3$
となります。
食べるパティの枚数を $p[L]$ とすると、
$p[L] = 2 \times p[L-1] + 1$
となります。
初期値は、 $a[0] = 1 , p[0] = 1$ です。
答えは、再帰によって求めることができます。
$solve(n,x) =$ レベル $n$ バーガーを、下から $x$ 層食べるときに食べることができるパティの枚数
とします。ここから先は場合分けをして求めます。

$n = 0$ のとき
$x=1$ なら答えは1、 $x=0$ なら答えは0です(問題の制約により、2以上になることはありません)。
上記を除き、 $x=1$ のとき
答えは0です。
$a[n] = x$ のとき
答えは $p[n]$ となります。
上記を除き、 $a[n]/2 + 1 \leqq x$ のとき
この式が意味するのは、レベル $n$ バーガーの半分を食べるかどうか、です。
必ずバーガーは奇数になるので、真ん中のパティの分が+1になっています。
このパターンでは、レベル $n-1$ バーガーを1つと、真ん中のパティを食べることが確定しているので、残りの部分だけ調べればよいです。
ということで、答えは $p[n-1] + 1 + solve(n-1,x - a[n]/2 - 1)$ となります。
それ以外、すなわち $a[n]/2 +1 \gt x$ のとき
一番下にあるバン1枚を食べたら、あとはレベル $n-1$ バーガーを食べる問題に帰着できます。
答えは $solve(n-1,x-1)$ です。

ということで、上のような再帰関数を作成すれば、答えを求めることができます。

2018-12-28

ABC115 C - Christmas Eve

未分類

問題
 提出コード

解法

問題の答えになるようにするには、木の高さをすべてソート昇順でソートし、連続したK本を選ぶのがよいです。
連続したk本の選び方は、N-K+1通りあるので、その全てのパターンについて、最大値から最小値を引いたものを計算し、その中の最小値が答えとなります。
昇順でソートしているので、長さKの区間を選べば、自然と区間の最初と最後がK本の木の最大値と最小値のペアになります。

2018-12-27

ABC076 D - AtCoder Express

実装系

問題
 提出コード
終わってから解説を見たのですが、あまりよくわかりませんでした()

解法

実装系だと思います。
まず、加速度は、常に1v/secで増加or減少させて、さっさと目標の速度に直すほうが効率がいいです。
そして、入力がすべて整数なので、この時点で加速度を切り替えるタイミングは、0.5秒単位であることになります(こうなるのは、サンプル4のような、目標の速度に達していないけど切り替えなければならないケースのみです)。
あとは、0秒(スタート)から、最後までの速度を、0.5秒単位で調べます。
まず、全ての時刻について、そのときの速度制限で初期化をしておきます。
$v_i$ は、 $l_i$ から $r_i$ 秒の間の速度制限だとします。
このとき、 $l_i$ から $r_i$ 秒の区間以外でも、 $v_i$ が影響をおよぼします。
というのも、 $l_i$ から $x$ 秒前だったとき、速度は最大でも $v_i+x$ しかだせません。同様に、 $r_i$ から $x$ 秒後だったとき、速度は $v_i+x$ しかだせません。
これを、すべての $v_i$ について行い、時刻が $p$ のときの速度を求めます。先ほどの計算を行い、現状の最大速度との最小値で更新していけばよいです。最初と最後は速度が0になっていなければならないことも忘れないようにしましょう。
この更新が終わったら、走った距離を求めます。
$p$ 秒のときの速度 $v_p$ と、その0.5秒後の速度を足し、0.5をかけたあとに2で割ればよいです。
というのも、距離=速度×時間であり、台形(三角形)の面積、つまり(開始時刻の速度+終了時刻の速度)×(走った時間)/2によって求めることができるからです。
これをすべての $p$ について計算すれば、答えを求めることができます。
0.5秒ごとの速度を記録する場合は、全ての秒数を2倍してあげれば、全部が連続した整数になるので、配列で情報を記録してあげることができます。

2018-12-27

ABC021 C - 正直者の高橋くん

幅優先探索(BFS)

問題
 提出コード
辺被りを考慮しないコードも提出してみたのですが、どうやらないらしいです

解法

cnt[i] = i番目の町へ行く最短経路の数( $10^9+7$ で割った余りをとります)
とすると、cnt[b]が答えになります。初期値は、cnt[a]=1です。
あとは、aから幅優先探索をしていけば答えが求まります。
最短距離を記録しておき、今xからyへ向かったとします。
aからyへの最短距離が、xの最短距離+1と等しければ、cnt[y]にcnt[x]を加算していきます。
これを繰り返し、キューの中が空になるまで行えば、答えが求まります。
ある頂点をキューに入れる操作を、間違えて2回以上行わないこと、そして $10^9+7$ で割った余りを取り忘れないようにすることを特に注意しましょう。

2018-12-26

ABC114 D - 756

数え上げ

問題
 提出コード
バグを生やしやすい問題です。相変わらずこういう問題でバグを生やしてしまいます。

解法

$N!$ をまずは素因数分解し、それぞれの素因数が何回登場しているかを調べます。これは、それぞれについて $O( \sqrt{N})$ で調べることができるので、全体で $O(N \sqrt{N} )$ になります。
素因数分解が完了したら、いよいよ約数が75個になるような数を数え上げていきます。
このような数を作成するには、以下のようなパターンが存在します。

1種類の素因数を74個使用した数
2種類の素因数をそれぞれ2個、24個使用した数
2種類の素因数をそれぞれ4個、14個使用した数
3種類の素因数をそれぞれ3個、5個、5個使用した数

ということで、あとはこれらの条件を満たす個数を数え上げることができれば、答えが求まります。
まずは、 $N!$ の素因数を、登場した回数によって5パターンに分けます。
素因数の個数が74回以上、24以上74未満、14以上24未満、4以上14未満、4未満です。
それぞれをパターン0,1,2,3,4と割り振っていきます。

さて、最初に調べた条件に、これらのパターンを当てはめていきます。

1種類の素因数を74個使用した数
ここに使用できる素因数はパターン0の素因数のみです。
パターン0の個数がそのまま答えになります。
2種類の素因数をそれぞれ2個、24個使用した数
前者はすべてのパターン、後者はパターン1もしくは0が使用できます。
前者と後者で使用するパターンが違うときは、それぞれのパターンの個数の積で、同じときは、(使用するパターンの個数)×(使用するパターンの個数-1)で数えることができます。
2個しようするのと、24個使用するのは全く違うものなので、組み合わせではなく順列になります。
2種類の素因数をそれぞれ4個、14個使用した数
数え方は上と同様です。使用できるパターンは、前者がパターン0~3、後者が0~2です。
3種類の素因数をそれぞれ3個、5個、5個使用した数
このパターンのみ注意が必要です。5個使用する素因数が2つあるので、ここだけ順列ではなく組み合わせを調べる必要があります。
3個使用する素因数はすべてのパターン、5個使用する素因数はパターン4以外が使用できます。
使用するパターンをi,j,kとし、それぞれ3個、5個、5個と割り振ることにします。
ここで場合分けをしていきます。被り防止のため、kはj以上としておきます。
1) i=j=kのとき
　　(iの個数)×(iの個数-1)×(iの個数-2)/2で求めることができます。
2)i=jのとき、もしくはi=kのとき
　　(iの個数)×(iの個数-1)×(iとは値が異なる、jもしくはkの個数)となります。
3)それ以外のとき
　　(iの個数)×(jの個数)×(kの個数)となります。

あとは、これらをすべて全探索して、和を求めれば答えとなります。

2018-12-26

ABC114 C - 755

再帰

問題
 提出コード
C問題で再帰を書くの、バグらせるのが怖くないですか…？

解法

最終的な答えがそこまで多くないので、全てのパターンを列挙していきます。
再帰を用いて解きます。
引数を2つ用意し、今上から何桁決定したか、という変数とx、今どんな値になっているか、という変数yを用意します。
あとは、その関数内で、yが問題の条件を満たしているかどうか、そしてx+1桁目を3,5,7のどれかに決めて再帰を行っていけば、yが問題の条件を満たすたびにカウントを増やすことで、答えが求まります。

ツバサの備忘録

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