精進記録: ABC25 - ABC37 C問題
今日の精進はABC25 - ABC38。
ただし、ABC25はまだデバッグが終わってない。 (-> 追記: ACした)
30番台は難易度が低く、20番台になると急に難易度が上がる。
600点クラスの問題が混じっているらしく、現時点ではなかなか険しい。
簡単な問題でも、相変わらずケアレスミスによるWAが多い。
以下解いていたときのメモ。
ABC37
一つ前のループとの差分を使う。
->一発AC
ABC36
座圧を座圧。
->一発AC
想定解法によるとmapを使うのが楽らしい。
C: 座圧
この操作は座標圧縮と呼ばれ，プログラミングコンテストでよく使われる
手法である.
-
map に，a1 , . . . , aN をキーとして追加する.
-
map ではキーが小さい順にソートして保管されているので，小さいほうから順に 0, 1, 2, . . . と値を割り当てる.
-
bi を求めるには，map で ai に割り当てられた値を参照すればよい.また，map を使うと N ≤ 100000 に対しては十分高速に動作することが知 られている.
ABC35
操作対象を開区間[l, r+1)にして、盤面に対して、l に+1, r+1に-1を加えていく。最後に累積和を取ると、O(N)で最終盤面が計算できる。AOJの座圧問題のときに勉強したテクニック。
->一発AC
ABC34
(i,j)の定義に注意。左下から。
必然的に最短経路になるので、
(W-1 + H-1)から縦に進むH-1回を選べばいい。
二項係数のmod付き計算は既に用意してあるので一瞬
->一発AC
C問題30番台はやたらと簡単な気がする。
ABC33
+, * しかないので、0にするためには
+でつながった各 * クラスターについて、その構成要素のうちの一つを0にする。
前から見ていくことにすれば、+と+の間についてその時点での値をtempに記録しておき、+に出会った段階でtemp != 0ならans+1でok
ループを抜けた時点でももう一度判定が入ることに注意。
-> 一つだけ通らないテストケースがありWA.
-> 9*9*.....のような連中は、long longでさえtempに格納すると溢れる。
シンプルに0の個数をカウントするべき。 -> AC
制約に対する注意力不足。
9*9* … だろうが0が一回でも入ってくれば関係ないという考えが危ない。
オーバーフロー時の動作は未定義なのだから、9*9* …*9 == 0 かもしれない。
一時間ちょっとで6問ぐらい。悪くはないが、30番台の難易度を考えるともう少し早解きできるようにしたい。
ABC32
途中でint溢れが起こりうる。
部分列を[l,r)として l, rについてループを回すのは通らない(部分点)。
累積積みたいなものを計算しようにも、容易にlong long溢れする。
まず、0が含まれていれば答えは自明なので、0がない場合だけでok.
部分列の左端が lのときに条件を満たす最大のrが求まっているとうる。
左端がl+1番目だったときsiが1以上とすると、alが範囲から抜けることで常に部分列積は減少する [l+1, r]の積 <= [l, r]の積。
よって、新しいrの探索は前のrから初めて良い(しゃくとり法)
部分列積を更新するときにtempをs[j-1]で割るが、サンプルケース4のような場合にtempが0になってしまうので、1とmaxをとっておく。
->一発AC
別の方法としては、sの最小値よりもKが小さい場合について別で処理しておくというもの。サンプルケース4のような場合に一般に気づけるか怪しいので、やはり危険そうな場合を察して排除しておくことが大事。
ABC31
全探索しても大丈夫っぽいが、同じ点のときに左側を選ぶという操作が面倒?
左からループを回しておけば、同じ値では更新されないのでok.
方針はすぐに立ったのに、実装にやたらと時間がかかってしまった。
あと、最大値を格納するための変数maxtakahashiの初期値を-1にしていてWAした。
注意力不足。
ABC30
可能な登場便で最も早い時間のものを取っていけばok.
残存便数の管理はvectorのpop_back()でやれる。
AとBを管理するvectorを書き間違えてWA食らった。
想定解法はlower_boundを使って順次取っていくというもの。
確かに。
ABC29
短いので全て探せば良い。aの数とbの数についてループ回して、
next_permutationで列挙する。
想定解法は文字数に関する再帰。
頭文字がbのものの辞書順が頭文字aのものより前になることはありえないので、辞書順で小さい文字を使ってDFSすればよい。
文字の種類が増えてもそのまま使えるという点で、想定解の方が優れている。
再帰への慣れがまだ足りてない。
とりあえず、これで10問。
ABC28
B問題って感じ。
想定解法の方がシンプル。ゴリ押しで通る問題でもコード書く前にもっと考察するクセをつける。
ABC27
Nが現れるプレーヤーが、Nに達するまでに 2xを選択していればそれを2x+1にすることで勝てる、というような方針で書いたが、N = 12で不成立。
解説AC。無念。
ゲーム系の問題は実験することが大事。上の方針は、相手の行動を考慮できていない。
N = 12の場合、2x+1にする余地はあるが、takahashiが初手で2を選択した時点で敗北が決定しているので意味がない。
上の考察は、Nに至るまでパスを相手も選択するという前提が入ってしまっている。
推定 600点相当の問題だったらしい。
cf) めちゃめちゃ力技だけど面白いアプローチ
TLEするが回るコードを作って実験し、OEIS https://oeis.org/A061547
を使って勝敗の切り替わりを決める数列を推定。結果をコードに埋め込んで提出。
ちょっと反則的だけど、どうしても解法が思いつかない場合には使えそうなテクニック。
ABC26 344点
木を作ってからpostorder dfsで埋めていく。
-> 一発AC
今回は結果オーライだが、int溢れについての可能性を本当はちゃんと考慮するべきだった。
ABC25 569点
またゲーム問題 & 高難易度(569点)
こう見ると、ずいぶんと出題傾向が最近と違うことが分かる。
パターンは高々9!なので、指定条件の通りに計算する。
まず、全ての合法手を調べ、点を割り振る。
各葉ノードには、その場面でのchokudai, chokumiの点をもたせる。
chokudaiのターンでは、可能な手の各々からの部分木を見て、
次のターンでchokumiが点を最大化したときのchokudaiの点の最大値になる点を選択。
最後の一手はchokudaiによるもので、これは一意。
8ターン目のchokumiのターンが最後の選択肢。
chokumiは、可能な２つの手のうち、自身の点が大きくなる方を選ぶ。
自身の子 = 葉の２つのうちで、chokumiの点が大きいもののノード値をコピーしてくる。
７ターン目のchokudaiは、自身の子である3つのノードのうちでchokudaiの点が最も大きいもののノード値をコピーする
これを繰り返して最終的にルートノードの値を取得すれば良い。
postorder dfsであれば、盤面の生成と上記を同時に行えるので、盤面を保持しておく必要がない。
ゲーム展開は9!あるが、盤面の状態は3^9未満の種類しかない。
最終点数はその盤面にどう到達したかには関係ないので、一度点数が決まった盤面については、dfsを枝刈りしてよい。
-> 形にはしたが、サンプルケース2の答えが合わない.....
(追記)
プレーヤーの順番判定が狂ってたっぽい。直してなんとかAC。
恐ろしく時間かかった。基本的な実装力がまだまだ足りなさすぎる。
