ツバサの備忘録

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

AGC005 A - STring

スタック

問題
提出コード

解法

この手の問題は、スタックをすぐに思い浮かべることができれば勝ちです。
次のようにシミュレーションしていけばいいです。

  • 次に見る文字がSだった場合
    問答無用でスタックにプッシュします。

  • 次に見る文字がTだった場合
    スタックのトップをまず確認します。トップがSであれば、スタックからその文字を取り出して、操作を終了します。
    スタックが空、もしくはトップがTであれば、次のTをスタックにプッシュして操作終了です。

これを最初から最後まで行い、最終的にスタックに残っている文字の個数が答えとなります。

感想

つい最近、括弧列の問題でスタックを利用するものを見たので、さらっと解くことができました。
2種類の文字列で、ある文字に別の文字を対応させる系は、スタックを活用すると楽ですね。

ABC046(ARC062) D - AtCoDeerくんと変なじゃんけん / AtCoDeer and Rock-Paper

条件の作成

問題
提出コード

解法

自分はシミュレーションをしました。
相手がpを出してきたときは、必ずこちらもpをだして相手にポイントが渡らないようにし、そして余ったpを出せる回数で得点を稼ぐ、といった方針です。
ということで、まずは相手のpの回数をカウントします。これをPとします。
そして、前からシミュレーションします。今自分がpを連続で出すことができる回数をGとします。今見ているターンで、相手が

  • pを出した場合
    あいこにするために、自分もpを出します。GとPのカウントを1つ減らします。

  • gを出した場合
    P \lt Gだった場合、得点に1追加し、Gを1減らします。
    それ以外のパターンでは、Gのカウントを1増やします。

このシミュレーションを最後まで行えば、答えが求まります。

ですが、実際はこのあたりのシミュレーションはどうでもよくて、N/2 - Pが答えになります。
最悪のパターンである、自分がすべてグーを出した場合の得点は-Pであり、ここから、自分がパーを出す回数を1増やすと、常に得点は1増えるため、パーを出せるだけ出すのが最善であり、最終的に上の数式が答えになります。
と解説に書いてありました。

感想

C問題同様、最終的な答えは綺麗な式になりますが、結局自分はシミュレーションをしていました。D問題は、式を出すよりもシミュレーションをした方がおそらくはやく解けるので、まぁどちらでもよかったかなと思っています。
思考の過程としては、まず相手に得点を取られないようにするにはどうすればいいか、を考え、そのためには相手がパーを出したタイミングで常に自分がパーを出せばいいことがわかり、そのうえで自分が得点を重ねていくためにどのような動きをすればいいか？を考えると、上のようなシミュレーションにたどり着きました。

ABC046 C - AtCoDeerくんと選挙速報 / AtCoDeer and Election Report

条件の作成

問題
提出コード1
提出コード2
GCD求める関数書いてますが関係ないです。

解法

提出コード1は、単純に場合分けしていきます。
現在の高橋君の票数をT、青木君の票数をAとします。

  • まず、1手前と比率が同じであった場合
    その回をスルーします。

  • 高橋君、もしくは青木君の票数を変えずに条件を満たすことができる場合
    つまり、T \ mod \ t_{i} = 0かつa_{i} \times (T/ t_{i}) \geqq Aとなる場合、もしくはt(T)とa(A)を入れ替えたパターンが成り立つ場合です。
    これは素直にA = a_{i} \times (T/ t_{i})とすればよいです。

  • それ以外
    (T/t_{i} + 1) t_{i}と(A/a_{i} + 1) a_{i}を計算します。
    高橋君の票数が前者の値になるか、青木君の票数が後者の値になるか、の2択です。
    まずは、票数が減るパターン、すなわち
    (T/t_{i} + 1) a_{i} \lt A、もしくは(A/ a_{i}+1)t_{i} \lt Tとなるパターンを排除します。これらのパターンになってしまった場合は、そうならない方を選択する必要があります。
    これらのパターンにならない場合は、二人の票数を改めて計算し、票数が少なる方を選択すれば答えとなります。

想定解の提出コード2は、すごい綺麗な解法です。
A \geqq k a_{i}かつT \geqq kt_{i}が成り立つ最小のkを求めればよいので、
k = max((A+a_{i} -1 )/a_{i} , (T+t_{i} - 1)/t_{i})
を求めていけばよいです。
これをN回繰り返せば、あとはA,Tを計算して答えとなります。

感想

過去に解いたときも、今回も、提出コード1のような解法で出しました。
2回とも、かなりバグらせているので、とても反省しています。
この手の問題で綺麗な立式ができるようになりたいですね…

AOJ 2933 - 矢 / Arrow (RUPC2019 Day3 D)

二分探索 前計算 コーナーケース

問題
提出コード

解法

簡単のため、Nにも送風機があるとしてよいです。
矢の長さがiのときの損失回数がわかっていれば、各クエリに対して二分探索をして答えを求めることができます。
ということで、長さがiのときの損失回数を頑張って求めます。
送風機と送風機の間にすっぽり矢が収まると、損失を受けます。
例えば、送風機jと送風機j+1の間の長さが m_{j+1} - m_{j} - 1
なので、その区間で長さiの矢に対しておこる損失の回数は、
max(0,m_{j+1} - m_{j} - i)
となります。
矢の長さが1増えると、その区間でおこる損失の回数は1減ります。損失回数が0になるまでこの法則は成り立ちます。
矢の長さがiのとき、損失回数は送風機間の長さのみに依存するため、送風機間の長さを昇順でソートしても問題ありません。ということでソートをします。
さて、i=1から順番に損失回数を計算していきます。なぜかというと、iの場合は明らかに\sum (送風機間の長さ)なので、すぐに求めることができるからです。
iの長さの矢に対する損失回数を、i-1の際の情報を元に計算します。
長さiの矢に対する損失回数をc_{i}とすると、
c_{i} = c_{i-1} - (長さi-1以上の送風機間の区間の個数)
となります。
あとはこれを求めていけばよいです。が、コーナーケースがただ一つ存在し、スタートから一番最初の送風機までの区間です。
この区間では、矢の長さがどのような場合でも、最初の送風機までの区間分の損失が生じます。
この損失を追加し忘れないようにしましょう。
あとは、前計算したものをもとに、二分探索をすることで答えを求めることができます。

感想

なんとなーくやりたいことは浮かんでいましたが、バグの祭りでした。
なんとなく、はじめからこうなるであろうことは予測していましたが…
途中でチームメイトのすずくんがコーナーケースに気づいてくれたので感謝です。

AOJ 2931 - 括弧を語る数 / Parentheses Number (RUPC2019 Day3 B)

スタック

問題
提出コード

解法

まず、順列pに逆の情報を持たせます。すなわち、
i 番目の開き括弧が j 番目の閉じ括弧に対応しているとき、 数列のi番目の値は j である。
というようにします。
すると、スタックを利用して、次のような操作を行うことで、問題の条件を満たす括弧列を作成することができます。
まず、今見ている配列の添え字をi、次に出現する閉じ括弧がj番目であるとします。

  1. スタックにp_iをプッシュします。と同時に、答えとなる文字列sに"("を追加します。

  2. スタックの一番上と、jを比較します。数字が同じであれば、スタックからその数字を取り出して捨てます。そして、jを1増やして、sに")"を追加します。

  3. 2の操作が行える限り行います。スタックが空になるか、数字が一致しなくなったら1の操作に戻ります。p_{i}をすべてプッシュし終えていたら、全ての操作を終了します。

こうしてできたsが答えとなります。ただし、スタックの中身が空になっていなければ、問題の条件を満たす文字列が無かったことになり、":("を出力することになります。

感想

括弧列といえばスタックを頭の片隅に入れている気がします。
今回も片隅においてはいたのですが、うまい処理を思いつけずにいたので、先輩にヒントをいただきました。
再帰でやろうとしていたので、こっちの方がおそらくシンプルに実装できたと思います。

AOJ 3057 - First Kiss (RUPC2019 Day2 G)

グランディ数

問題
提出コード

解法

まずは、キッポーが1本のときについて考えます。
この問題についてのグランディ数を求めることができれば、あとはN本のキッポーについてのグランディ数のxorを取った結果を見ればよいです。
キッポーの長さを0にした方が負けなので、1だけ残して相手のターンにまわすことができれば勝つことができます。
ということで、長さが1の際を最終地点として考えていきます。
基本的に、[1,D]の長さだけ1ターンで食べることができますので、
[2,D+1]の長さで自分のターンになれば、長さを1にして相手のターンに回すことができます。
逆に、現在の長さがXのときは、[X-D,X-1]の任意の長さにすることができます。
これを踏まえると、長さがXのときのグランディ数は、
(X-1) \ mod \ (D+1)
となります。
これが0なら後手の勝ち、そうでなければ先手の勝ちです。
あとは、N本のキッポーについて、先ほどの式でグランディ数を計算し、xorをとっていけば、1本の際と同様の判定で勝者を調べることができます。

感想

小学生かそこらのころ、0からスタートして、交互に1~3加えた数字を言っていき、21だか23になったら負け、というゲームをしたことがあります。
確か何かの新聞の広告で、このゲームについての必勝法を考えよう！みたいな問題が載っており、似たようなことを考えました(グランディ数とかそういうのは知らないので、どの数字を言ったら確実に負けてしまうのか、とかそういったあいまいな話ですが)。
グランディ数の問題にしては割とシンプルなため、珍しく自力で解くことができました。うれしいです。
ちなみに、この記事を全て書き終えてから、キッポーがポッキーになっていたことに気づいて慌てて直したのは秘密です。

AOJ 3058 - Ghost (RUPC2019 Day2 H)

Dinic法(最大流,最小カット) 燃やす埋める問題

問題
提出コード

解法

燃やす埋める問題です。
詳しくはこちらを。
始点と終点s,tおよび各幽霊に対応する作り、sから各幽霊、各幽霊からtに辺をはります。
この際、sから出てくる辺を左に向くパターン、tへ向かう辺を右に向くパターンとすると、
今i番目の幽霊が向いている向きが

  • 右のとき
    sから出てくる辺は容量A_{i}、tへ向かう辺は容量0

  • 左のとき
    sから出てくる辺は容量0、tへ向かう辺は容量A_{i}

となるように辺をはればよいです。
そして、i番目とj番目の幽霊が向かい合っているときにBの恐怖度が発生するとしたとき(i \lt jとします)、
iからjに容量Bの辺をはると、うまく条件を表現することができます。
あとは、フローを流していき、最小カットを求めれば答えとなります。

感想

問題を見た時点で燃やす埋める問題だ！となったので、成長を感じます。
こういう気づけばあとはコピペで終わるような問題をさらっと解けるようになると気持ちいいですね。