ツバサの備忘録

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

ARC065 D - 連結 / Connectivity

数え上げ Union-Find木

問題
提出コード

解法

UnionFind木を貼ると解ける問題です。
鉄道について、辺をそのままUnionFind木に反映させると、根が同じ都市については、連結であることになります。
道路についても同様です。ということで、まずはUnionFind木を2つ用意し、鉄道と道路それぞれについて辺を付け足していきます。
あとは、鉄道と道路両方の根が一致する個数を数え上げます。
mapを用意し、鉄道と道路の根のペアをキー、そしてそのようになる都市の個数を紐づけていきます。
n個の都市すべてについて道路と鉄道の根のペアを求め、mapにおいて対応する場所に+1していくことで、出力の際にmapで対応する場所を見るだけで答えが求まります。

ABC048 D - An Ordinary Game

グランディ数 条件の作成

問題
提出コード
グランディ数を利用する問題は、ぱっとみで使うだろうなーというのがわかっても、そこから答えに結び付けるのが難しくていつも解くのに時間がかかります…

解法

お互いが操作できなくなる状態では、必ず2種類の文字になっていて、それが交互に並んでいるような状態になります。
ababa...のような状態です。
ababacacaca...やababcaca...のような状態でも、まだまだ文字を削除できます。
このことにさえ気づくことができれば、あとはいけると思います。
このようなパターンでありうるのが、
ababab...baという、両端がそろっている状態、もしくは
ababab...abという、そろっていない状態です。
そして、両端の文字を消去することができないという問題の条件から、どっちになるかは初めから決まっています。
前者のパターンでは、最終的に文字数が奇数に、後者では偶数になります。
また、最初の文字の偶奇は簡単に調べることができるので、お互いが最善を尽くしたときに消去できる文字数の偶奇がわかります。
この偶奇が、結局は勝者を決めることになります。
ということで、初期状態の文字数の偶奇と、両端が同じ文字であるかどうかを2進数で表し、2つの排他的論理和をとると、勝者がわかります。

ABC048 C - Boxes and Candies

貪欲法

問題
提出コード

解法

貪欲法で問題ありません。
a_iとa_{i+1}についてみて、x以下なら次に進みます。
xより大きかった場合、xになるようにキャンディを減らしていくのですが、このときi+1の方を優先的に減らしていきます。すると、a_{i+1}とa_{i+2}についてみたときに、よりキャンディを減らす必要数が少なくなります。
ということで、あとはこれを繰り返していくことで、答えが求まります。

ABC047 D - 高橋君と見えざる手 / An Invisible Hand

未分類

問題
提出コード
デバッグ出力と一緒に答えの出力を消してしまわないように注意しましょう。

解法

高橋君が最大の利益を得るとき、売る町と買う町は1つずつで、それぞれT/2だけ買い、T/2だけ売ることになります。
売値と買値の差が一番大きい場所が、その売る町と買う町になります。
その際、利益を1円下げるには、このどちらかの値段を1円ずらせばいいことになります。
ですが、(売値-買値)が最大になる場所が複数箇所存在しているとき、その複数箇所それぞれについて、売る町もしくは買う町のどちらかの値段をずらす必要があります。
また、問題のA_iがすべて異なるという条件から、候補の売る町(もしくは買う町)が同じ町になることはありませんので、例外を考慮する必要はありません。
よって、あとはその候補の個数を調べればよいです。
まずは、(売値-買値)の最大を求めます。
A_0～A_{i-1}の中での最小値を、A_iから引いたときが最大値の候補になりますので、これをすべてのiについて行えばよいです。これはO(N)で求められます。
利益の最大値(xとします)が決まったら、あとは売る町と買う町のペアの個数を求めます。
mapを使い、i-1までに、A_i - xとなるようなA_jが存在するかどうかをしらべ、存在したらカウントを増やしていけば良いです。
このカウントが、最終的な答えとなります。

ABC047 C - 一次元リバーシ / 1D Reversi

未分類

問題
提出コード

解法

片側のみに石を置いて直しても、両側から石を置いて直しても手数は特に変わらないので、片側からのみで考えていきます。
すると、左から右向きに見ていったときに、

  • 白から黒になる、もしくは黒から白になっている境界の個数

がそのまま答えの手数と一致します。
ということで、境界の個数を調べたら答えとなります。

ABC113 D - Number of Amidakuji

前計算 動的計画法(DP) 数え上げ mod N 考察系

問題
提出コード
DPをします。
まずは、下準備をします。
ある高さについて、幅がxのとき(つまり、x+1本の棒があるとき)に、横線の置き方がいくつあるかを計算します。
これをmemo[x]とします。 x=0のとき、横線はおけないのでmemo[0]=0です。
x=1のとき、横線を置くか置かないかの2通りです。よってmemo[1]=2です。
x=2のときについて考えます。
横線を置くと1、置かないと0とすると、
00,01,10の3通りです。
memo[2]=3です。
これ以降については、実はフィボナッチ数列のようになっています。
幅がxのとき、一番右側に横線を置くか置かないかで場合分けをします。

  • 横線を置かないとき
    一番右端を除く、x-1の幅についての置き方を考えればよいので、これは
    memo[x-1]になります。

  • 横線を置くとき
    一番右端に横線を置くと、その左側は自動的に横線を置くことができなくなります。
    残ったx-2の幅については自由に置くことができるので、これは
    memo[x-2]になります。

ということで、
memo[x] = memo[x-1]+memo[x-2]
となります。
Wの最大値が8なので、これは手計算で求めてもいいですし、プログラムを書いてO(W)で求めてもいいと思います。

さて、答えの数え上げをしていきます。
dp[i][j]=一番上の高さのときに、一番左の棒からスタートしたときに、上からi番目の高さにいるときに、左からj番目にたどり着くようなものの個数
とします(jは0-indexedとします)。初期状態は、dp[0][0]=1です。
すると、
i-1のときに、j-1、j、j+1の3つのどこかにいる必要があります。
それぞれ、i-1のときに、左上、真上、右上にいて、そこから横線を通り（または通らず）、今の場所に移動します。

  • 左(右)上から移動してくる場合
    考えることは同じなので、今回は左上から移動する場合についてのみ考えます。
    j番目の棒線にたどり着くとき、j-1とjの区間に横線を引くため、jとj+1およびj-2とj-1の区間には、横線があってはいけません。
    ですが、それ以外の部分は自由に横線をひくことができます。
    この部分は、jより左側と右側に分割することができ、幅がそれぞれ
    w-1-(j+1)とj-2になります。
    ということで、この二つの幅についての横線の置き方は、memoを参照することで求められます。
    あとは、その二つとdp[i-1][j-1]を掛け算すればよいので、
    memo[w-1-(j+1)]×memo[j-2]×dp[i-1][j-1]
    となります。
    同様にすると、右上から移動するパターンは
    memo[w-1-(j+2)]×memo[j-1]×dp[i-1][j+1]
    となります。

  • 移動せずに降りてくる場合
    jの左右には横線があってはいけません。しかし、それ以外は横線を自由に置くことができます。ということで、次のようになります。
    memo[w-1-(j+1)]×memo[j-1]×dp[i-1][j]


ということで、この3つの式の和がdp[i][j]の値になります。
これを計算していくと、答えがdp[h][k-1]にあります。

ABC113 C - ID

未分類

問題
提出コード

解法

Y_iがすべて異なるので、まずはi、Y_i、P_iの3つの情報をセットにして、Y_iで昇順にソートしていきます。
その後、ナンバーを決めていきます。
P_iがj番目であったとき、左側の0を除いた市の認識番号は、
j+P_i×10^{6}
です。
あとは、左側に0を付ければ答えとなります。
これは、string型の変数を用意して作成します。
先ほど求めた認識番号の10で割った余りを代入、認識番号を10で割る、ということを認識番号が0になるまで繰り返します。
終わったら、string型の変数が12桁になるまで'0'を代入し、最後に前後反転をしたら答えとなります。
これをすべての市に対して行えば完了です。