B - Colorful Lines(ARC130)
問題
感想
色とかグリッド上の状態をどのようにすればいいのか。ちょっと複雑で迷った。
解法
まず、一番知りたいのは最終的な「各色のカウント数」である。それを知るためには以下の二点に気を付けなくてはいけない。
同じ行、列にクエリが飛んで来たらもともと塗られていた色は塗りつぶされる。
色を塗った以降の行、列の個数を保持しておく。そうすることで最終的に塗りつぶされている個数がわかる。
愚直にやってもいいのだが、クエリを逆順にするといい感じに解決できそうなのが見える。 上の課題は順に以下のような説明がつく。
行、列にそれぞれ使用済みの番号を保持する。すると、使用済みである場合はそのクエリは結局は塗り替えられてしまう色となるため無視できる。
逆順に回すと、そのクエリを受け付けた時点の個数さえ把握しておけば塗り替えられるマス目はおのずと把握できる。
以上、パズル要素が強い問題でした。
感想
仕事終わりのモヤがかかった頭ではちと迷う。あと、この逆順という発想はすごく大事。DPでもお目にかかるので手札として持っておくべきだなと。
D - Rain Flows into Dams(ABC133)
問題
感想
わからないものがあったら変数おいて解こうね
解法
サンプルケースの２がわかりやすいのでそれを用いて解説する。
5
3 8 7 5 5
山が５個のパターンですね。 まず、求める山の水量をX1,X2,...X5とし、またダムの水量もA1,A2,...A5とする。 ダムの水量を立式すると
- 2A1=(X1+X2)
- 2A2=(X2+X3)
- 2A3=(X3+X4)
- 2A4=(X4+X5)
- 2A5=(X5+X1) となる。
X1,X2,X3について解くと、
- X1=A1-A2+A3-A4+A5
- X2=A1+A2-A3+A4-A5
- X3=-A1+A2+A3-A4+A5
ここでb+aをするとX2=2A1 - X1という結果が得られる。同様にしてX3=2A2 - X2とX1が決まればすべての値の結果が得られる。 なので、実装方針としては最初にX1を求め、そこからすべての値を順に求めていけばよい。
- まとめ 変数おいて考察。あとは式を解こうね。。。焦ってはいけない。
C - Stones(Tenka1 Programmer Beginner Contest 2019)
問題
感想
やらかした。愚直に見ていこうとしてしまいちゃんとテストケースで落とされた。
解法
明らかに足りなかった考慮が完成形が決まっていること。つまりは....####や#####、.....という左側に白、そこから右側に黒がある（もしくはどちらか単色しかない）場合しか条件を満たさない。
なので、今回は最小の変更数を求めたいので左側の黒の数と右側の白の数を保持しながら合計値の小さいものを求めればｏｋ
まとめ
「完成形から考える」という視点。ほかの問題でもあるのでそういった視点で見れるようになるのも大事。
B - Balls of Three Colors(ARC128)
問題
感想
わかりませーん。緑diffですが、解けませんでした。「同じ数字が二つ生まれればいける」みたいなところも気づいたが、全く気にも留めずにスルー。こういうのって日頃から頭を使っていない証拠なのだろうか...
解法
まず、Ｒ,G,Bの組み合わせで同じ数字の組み合わせを作るというところをゴールにどうすればよいのか考える。ボールの個数の遷移を考えると(-1,-1,+2)みたいな動きしか生まれない。つまりは二組のボールの差は3しか変化しない。（お互いに-1,-1ずつで差はひらかないパターンもあるがそこは問題にならない）
ということは、二組の数字を同じ数字にするためには差が3の倍数でなければならないというところが見えてくる。なので、まず実現可能かは3の剰余が0であることを確認すればよい。
次はその回数について。
実はよくよく考察すると(0,10,7)みたいなときには(-1,9,9)みたいな遷移を避けるため(1,9,6)みたいなものを一度挟むみたいな処理を特段考慮する必要はないということがわかる。
以下、（R,G,B）としＲをそろえる場合を考える。結構がばがば解説なのであてにしてはいけない。
G>=Rの時
これは素直に行けそうかなと思います。上記の考え通りに行う。
G<Ｒの時
要は二組の数字を最小回数で同じものにそろえる場合、動きうるボールの遷移は以下の二通りを決まった回数回行う。
- （R-1,G-1,B+2）
- （R+2,G-1,B-1）
ここで、最小回数について考慮すると結局は１と２の回数は決まっているということに気づく。もし、操作順ならこの部分も考慮しないとですが今回はあくまで回数のみ
丁寧に解説するなら、例とか挙げるべきですがちょっとお疲れ気味なのでいったん端折ります。
ともすると、この上記二つのパターン分けをする必要もなさそうなので、あとは数えていきます。
さて、結局は
- どのボールに合わせるかを決める
- 残りのボールが3の倍数差か確認する。
- 上記を満たす場合、同じ数字にそろえるまでの回数 と すべてを一つのボールに変更する回数 を足す。
- これをそれぞれのケースで3通りずつ試していく。その最小値を記憶して出力
といった感じになる。
同じ数字にそろえるまでの回数:差は３ずつ埋まっていくので、(X-Y)%3回分（X,Yは最終的にはすべて同じボールに変換される色のボールの個数）
すべてを一つのボールに変更する回数:二つのボールの合計値の半分。
以上を計算して、最小値を算出、出力すればOK
感想
システマチックに考えたいです
A - Triangle（AGC036）
問題
感想
間違えたわけではないんだが、キレイに解けなかったので一応はっておく。三角形の面積を使った問題で変数を固定化するところまではよかった。
が、変数を固定化する部分を間違えて誤差にやられた。
解法
editorialでわかる。
https://img.atcoder.jp/agc036/editorial.pdf
なぜかx2とy3を固定化して、x3とy2を変数としてsqrtなどして対応したせいで計算ミスった。
感想
丁寧に数式を変形しようね
C - ABC conjecture(ABC227)
A - Colorful Subsequence(AGC031)
問題リンク
感想
愚直にやってTLEした。そこから「もとの文字列から順序を変えずにつなげたもの」をそのまま受け取ってしまい、元の配列の順番のまま数え上げる方法がわからず（というか面倒）になって集中力がつきてしまった。
ちなみに、今回も考察不足で「もとの文字列から順序を変えずにつなげたもの」は別に順序を気にしなくてもよいことがわかる。...マジでしっかり考えましょう。最近頭動いてない。
運動するとちょっとは脳機能あがるかな
解法
まず、文字列列挙するのはわかる。それで「もとの文字列から順序を変えずにつなげたもの」をそのまま受け取ると、入力の文字列のindexを考慮しながら実装するのだがTLEに。
そこでもう一つの条件である「すべて異なる文字からなるものの数」を求めるということに注目する。すると、元の文字列の順番を考慮しなくてもよいことが見えてくる（実際に私は見えなかったが）。
アルファベット毎に考える。"a"を考えると
- 文字列中に一つしか出現できない。
- "abbbacccaa"という文字列があった場合。どの"a"を文字列中に表示させるかを考えればよい。表示する"a"が決まると自然と並び順も決まる。ここが見えなかった
- 非表示というパターンもあるので忘れずに。
以上を踏まえると、各アルファベット毎に数え上げて、その個数+１個（+１は選択しないパターン）をかけ合わせていけばよい。
そして、最後にすべて選択しないという空文字の場合を考慮し、-１してMODとって終了。
まとめの感想
文字列列挙。アルファベットが高々26通りなので、そういところに注力すると計算量落とせるのかなと思って解いていったが、結局解けずじまい。
