ツバサの備忘録

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

diverta 2019 Programming Contest C - AB Substrings

問題
提出コード

解法

まず、それぞれの文字列の中に含まれるABの個数を調べます。これは、文字列をどのように連結しても、個数が変化することはないので、そのまま答えに加算されます。
では、文字列の連結によってあらたに増えるABの個数を調べます。
文字列を連結したときに、新たにABを増やすには、
...Aという文字列と、B...という文字列を、この順に連結する必要があり、このときに1つだけ増えます。
ということで、3種類の文字列の個数をカウントします。それは、

  1. B...Aのように、Bで始まりAで終わる文字列

  2. X...Aのように、B以外の文字で始まりAで終わる文字列

  3. B...Xのように、Bで始まりA以外の文字で終わる文字列

です。 それぞれ、C_{1},C_{2},C_{3}とします。

さて、それぞれのパターンをどのように使えばいいか考えてみます。
B...の文字列と、...Aの文字列は、1対1で対応するので、パターン1の文字列たちは、1つの文字列にまとめてしまっても問題ありません(Aで終わる文字列と、Bで始まる文字列の、個数の差に影響はありません)。
ので、B...AB...AB...Aのような、おっきな文字列に置き換え、C_{1}-1を答えに追加します。もしC_{1}=0ならこの操作はいりません。
次に、パターン1,2,3のうちどの文字列を優先して使用するべきか考えてみます。
すると、パターン2,3を先に利用してしまうと、パターン1の文字列1つではABを作成することができなくなってしまいますが、先にパターン1の文字列にパターン2,3の文字列を組み合わせてあげることで、パターン1の文字列を無駄なく使用することができます。その後に、残ったパターン2とパターン3の文字列を1つずつ使用して順番に組み合わせていけばよいです。min(C_{2},C_{3})です。
ということで、

  • 文字列中にはじめから存在しているABの個数をカウントする

  • パターン1~3の文字列の個数をカウントし、C_{1},C_{2},C_{3}とする

  • (C_{1} \neq 0のとき)C_{1}-1を答えに追加し、C_{1}=1とする

  • (C_{1} \neq 0のとき)C_{2},C_{3}が1以上ならば、それぞれから値を1減らし、答えのカウントをその分増やす

  • min(C_{2},C_{3})を追加する


感想

ツメが甘いのでバグをとりきるのに時間がかかりました。
焦りは禁物ですね。

AOJ 1553 Manhattan Warp Machine 1

問題
提出コード

解法

ある地点からは、ボタンを押すと正負2つの向きに進むことができてしまうので、単純なDPを行うことができません。
ので、代わりにダイクストラ法で始点から進んでいくと、うまく計算することができます。
コストc_{i}を辺の重みとみなし、それぞれのボタンについて、d_{i}-d_{i}に進める、とすると、座標を頂点、ボタンの移動を辺として答えを求めることができます。
座標は、少し多めに確保しておけば、全てのパターンを網羅しきることができます(ボタンの移動の順番は自由に変えられるので、正負をいい感じに交互に織り交ぜることで、配列の外に飛び出さないとたどり着かない、ということがなるなります)。

感想

ICPCを多少やっていたので秒でダイクストラを書き始めることができました。
1ペナを貰ったのは反省です(初期地点の場所を間違えました…)

AOJ 1551 A White Wall

問題
提出コード

解法

制約を見ると、愚直に全探索しても間に合うことがわかるので、ただひたすらに愚直に実装します。
今回は、[a_{i},a_{i} + L_{i} ]の幅に塗りますが、これを[a_{i},a_{i} + L_{i})に塗ると考えれば、[x,x+1)に塗ることをxに塗る、と表現できるようになり、配列のカウントに落とし込めます。
あとは、どこも塗られていない場所を一つ持ってきて、そこを始点とし、そこから塗られている区間の幅を調べていきます。
もしどこも塗られていない場所がない場合は、一周全てに塗られていることになるので、この場合だけ別処理をしてしまえばいいです。

感想

実はA問題なのですが、よく自分がバグるタイプの問題で、いきなり重かったです。
vectorの初期化を最近ギリギリにしていたので、こっちも余裕を持たせた方がいいのでしょうか…

AGC033 C - Removing Coins

問題
提出コード

解法

それぞれのターンで、ある頂点を指定すると、その頂点を根とする木について、葉になっている頂点が消えることになります。
そして、どのような頂点の選び方をしても、木についている頂点を減らすのに一番時間がかかる部分は、木の直径の部分です。ある頂点を選んだ際、一番遠くに存在するコインは、もちろんその頂点からの距離が一番遠いものになります。その頂点は、必ず木の直径の端点になっている(この問題の解説に載っています)ので、ネックになるのは木の直径です。
ということで、木の直径が勝敗に関係していそう、ということがわかったので、木の直径がどのような場合に勝敗がどうなっているかを調べます。

  • 直径が0の場合
    頂点が1個の場合です。もちろん、先手がコインを取って終了なので、先手の勝ちです。

f:id:emtubasa:20190505032753p:plain

  • 直径が1の場合
    頂点が2個です。もちろん、先手と後手が1回ずつコインを取って終了です。後手の勝ちになります。

f:id:emtubasa:20190505032837p:plain

  • 直径が2の場合
    図のように、真ん中を選択すると、直径が0のパターン、端を選択すると、直径が1のパターンにうつります。
    先手は、直径が1になるパターンを選択すればよいので、直径が2の際は先手の勝ちです。 f:id:emtubasa:20190505033107p:plain

  • 直径がXの場合
    直径が2の場合同様、操作後はX-1のパターンとX-2のパターンにうつります。ということで、X-1X-2のパターンのうち、どちらか一方でも後手が勝つものが存在していれば、直径がXのパターンでは先手の勝ち、そうでなければ後手の勝ちになります。

ということで、フィボナッチ数列のDPのような感じで、入力された木の直径のパターンにおける勝敗を求めていけば、答えを求めることができます。
木の直径は、上でも挙げたこの問題の解法のように、まずはランダムな点からBFSを行い、最も遠い頂点を求め、改めてその頂点からの最長距離を求めれば、そこが直径になります。

感想

木の直径に気づきさえすれば、後は丁寧に調べていくことで解ける問題でした。はじめは、直径の偶奇に注目していましたが、それでは解けないことがわかったので、直径が小さい方から愚直に書き出していきました。
実は、木の直径がXの際の勝敗は、3で割った余りを求めることで、O(1)で求めることができるらしいです。今回はその必要がなかったですが、そこまで気づけるようにもなりたいですね。

AGC033 A - Darker and Darker

問題
提出コード

解法

マスA_{ij}が黒になるのは、初期状態における黒いマスA_{xy}とのマンハッタン距離を全て調べ、そのうちの最小値回だけ操作を行ったときになります。
ので、全てのマスについて、初期状態に存在している黒いマスとのマンハッタン距離の最小値を調べ、その中で最も大きいものを選べばよいです。
が、愚直にこれを計算すると間に合わないので、工夫する必要があります。
あるマスと別のマスにおけるマンハッタン距離は、4方向にBFSした際の手数と同じになります。
距離を求めるために黒いマスからBFSすることを考えると、最初に、キューに黒いマスを全て放り込み、そこからまだたどり着いていないマスへBFSを行うことで、黒いマスと全てのマスとの最短距離が求まります。
あとは、求まった距離の最大値を求めればよいです。

感想

これを5分ほどでバグなく書くことができたのはICPCのおかげ…でしょうか?
あんまりAGCっぽくないなと思いました。

Tenka1 Programmer Beginner Contest 2019 D - Three Colors

問題
提出コード

解法

まず、三角形の成立条件を思い出すと、長さx,y,zの三角形が存在するには、
x+y \gt z, y+z \gt x, z+ x\gt y
が全て成立している必要があります。
逆に、xが最長の辺かつx \geqq y+zを満たしているとき、三角形を作成することはできません。両辺にxを追加した後に2で割ると、

  • x \geqq \frac{x+y+z}{2}

という条件がでてきます。
仮にこの状況になった場合、xx,y,zの中で最も大きい値になっているはずです。
x+y+z\sum a_{i}で求めることができるので、x \geqq \frac{x+y+z}{2}となるような塗り分け方は、どうにかして求めることができそうな気がします。ということで包除原理を利用して、全ての塗り分け方から、三角形を作成できないようなパターンを引くことで答えを求めることにします。
xが最大であると仮定して、そのときにx \geqq \frac{x+y+z}{2}となる場合の数を求めることにします。すると、これはy,zが最大の場合も全く同じ状況になるので、3倍すればよいはずです。
場合の数を、動的計画法で求めていきます。

  • dp[i][j] = i番目までの数を割り振って、xの値がjになるようなものの場合の数

とします。これは、

  • dp[i+1][j] = dp[i][j] \times 2 + dp[i][j-a_{i}]

という遷移で数え上げることができます。
右辺の1つ目の項は、a_{i}xに割り振らない場合で、残ったy,zのどちらかに割り振ることになるので、2倍します。 2つ目の項はa_{i}xに割り振る場合です。
この遷移を利用して数え上げを行い、あとはsum = \sum a_{i}として、
\displaystyle \sum_{i=(sum+1)/2}^{sum} dp[n][i] \times 3
を求めれば、三角形にならないパターンを数え上げることができる…
はずですが、コーナーケースが存在します。
sumが偶数の場合、(x,y,z) = (sum/2,sum/2,0)となるケースが存在するかもしれません。このパターンは、上のDPをそのまま用いると重複して数えてしまいます。2つのsum/2を区別してsumA,sumBとすると、
dp[n][sum/2]には、
(sumA,sumB,0),(sumA,0,sumB),(sumB,sumA,0),(sumB,0,sumA)
の4つのパターンが含まれているはずですが、最後に全体から引く際に、xが最大という条件を外してこれを3倍するため、合計12パターンが引かれることになります。が、(sumA,sumB,0)というパターンは、3! = 6通りの並べ方しかないため、2回分引いてしまっていることになります。 
これを解消するために、これらのパターンも数え上げてしまいます。これまた動的計画法を利用します。
このパターンは、2種類のみにa_{i}を割り振ると出来上がるので、

  • dp2[i][j] = i番目までの数字をxyのみに割り振って、x = jとなるようなものの場合の数

とすると、遷移は先ほどとほぼ同じで、

  • dp2[i+1][j] = dp2[i][j] + dp2[i][j-a_{i}]

という遷移で数え上げることができます。
先ほどの2倍をする部分だけが消えた形になります。
ということで、この遷移を行うとdp2[n][sum/2]は、(sumA,sumB,0),(sumB,sumA,0)の2パターン分だけ綺麗に数え上げられているはずです。
あとは、この部分の調整も行いつつ、

  • sumが奇数の場合
    3^{N}  - \displaystyle \sum_{i=(sum+1)/2}^{sum} dp[n][i] \times 3

  • sumが偶数の場合
    3^{N}  - \displaystyle \sum_{i=(sum+1)/2}^{sum} dp[n][i] \times 3 + dp2[n][sum/2] \times 3

を求めると、答えになります。

感想

解けるべき問題だった…?気がします。コンテスト中、似たようなDPをすることまでは思いついていたのですが、細かいところを詰められなかったのと、そもそもコーナーケースに気づいていませんでした。
雰囲気でDPを解いているのがバレる回でしたね。

AOJ 1150 - 崖登り

問題
提出コード

解法

面倒くさそうに見えますがダイクストラをします。
マス目が少ないので、左のマス目、右のマス目、どちらの足を動かす番か、という情報を全て持ちながらダイクストラができます。
足を動かす際は、動かさない方の足を基準にして、距離と方向を決めます。少し広めに探索して、条件(マンハッタン距離が3以下、等)を満たさなければそこは探索をしない、というようにやってあげると、簡単な2重ループで書けるので楽でした。
また、初期地点は、右足と左足どちらも同じSのマスにいる、と考えると楽になります。
あとは、丁寧に遷移しながらダイクストラをして、Tにつくまでの最短時間を求めれば終わりです。

感想

今回は、xyが問題文と自分のコードで逆になっていたため、それが原因となるバグを埋め込み、そして初期状態は、両足がそれぞれ別のSのマスにいなければならないと誤読しました。
遷移が多くなるだけで、頭の中が整理できなくなってしまうので、もう少し綺麗なコードにしたいと思います。