緑埋め
🤔 何が書いてあるの？
- 緑コーダーを目指して緑埋めしていく過程の記録
- 緑diffの問題の解法のメモ
📝 解いた問題と感想
-
第二回全国統一プログラミング王決定戦予選-B-Counting of Trees
【解説AC】大まかな方針は合っていたが，自力では2つのWAが取れなかった．ランダムなテストケースを作る環境が必要？それでもエッジケースに出会えるとは限らないけど．
-
数列の長さをNとしてS-3*NをN個に分ける分け方をコンビネーションで求めてAC．想定解はDPだったのでDPでも解いた．
-
【解説AC】愚直な方法で実装したらRE,TLEで通らず．解説を見たらMODでDPテーブルを作るような感じ．漸化式を作るということをめんどくさがらずにやって見るということは大事かもしれない．
-
BFSで解けた．
-
下記のような手順で自力で解けた
- nのほうが桁数が大きい -> sの?はすべて1にする
- nのほうが桁数が小さい
- sのはみ出ている部分に1がある -1
- sのはみ出ている部分に1がない はみでている部分を切る
- nとsは桁数が同じ
- 最高位の?を1にする，ほかを0にする
- n以下になった
- 最高位の?は1にする
- nよりも大きくなった
- 最高位の?は0にする
- n以下になった
- 最高位の?を1にする，ほかを0にする
でももっと楽な方法が解説されていた
- ?を全部0に変えてNよりも大きければ-1
- ?を全部0に変えてNよりも小さくなれば，大きい桁から順に再度1に変えてみる．N以下になれば1のまま，Nより大きくなれば0に戻す．
上の2点を簡素化している解答だった．1点目は3点目に包含されるので簡素化できた．2点目はSをできるだけ小さくするとN以下になるか，という点で発想は同じだが，解説のほうが圧倒的にシンプルに実装ができる．
-
- 自力AC．heapqで解いた．
-
- 【解説AC】答えを二分探索する発想がまだない．二分探索の続ける条件式も問題，実装者によって違う気がする．どう使い分けるべきなのか二分探索を集中的にやる時間も設けるべきかも．
まだまだ追記していきます