キーエンスプログラミングコンテスト2021
キーエンスプログラミングコンテスト2021
最近負けすぎててマジでヤバい。どのくらいヤバいかというとCodeforcesでhighest-400, AtCoderでhighest-250をしてしまったくらいヤバい。
そして緑落ちした。ここ一ヶ月何がどうなってるんですかね。危機感を感じたのでわかんなかった問題は全部ブログでまとめることにした。
よく上級者は、低レート帯なら質より量と言うけど、それって既に数学力の蓄積があることが前提な気がしていて、強い人が一瞬で流せるような思考でも僕には時間をかけて理解しなきゃいけないんだなあということを改めて実感した次第です。
どうしても時間がかかってしまうから一日何問こなせるかはわからないけど、スタートラインに立つ才能もないから仕方ないね......。
A問題
何でこれ解けなかったの？ねえ。純粋に精進不足です。解法ガチャで最初に引っかかったものをずっと考え続けてしまうのをやめなければ。
やった思考としては
- 積の最大値は最大値どうしの掛け算
- けどAで選ぶべきindex( i )はBで選んだindex( j )以下でならなければならない。
- ある範囲のBの最大値を求めて、それより左にあるAの要素の最大値をセグ木とかで求めたらうまくいかないかなーと思いながら投げたらWA。
- 一番ダメだったのはワンチャンとか思いながらこれを投げたことかも。低難易度でやることじゃねえ。反省してください。
- こういうペア系を扱うときにガチャで排出される解法は大体「片方固定する」なんだけど、何故かAを固定することばっかり考えてた。は？？
- 逆から見てみたりもしたけどあまり有効じゃなかった。
- そして何も分からずしんどくなったのでBに行って終わった。
全てがダメだな。どうしてこうなった。
要はBの方を固定してAの最大値を取ってくれば良いだけ(それまでの値とのmaxを取る)なので、300点です。
敗因は、Bを固定することを何故か1ミリも考えなかったこと。
よく考えるとこういう系でAじゃなくBを固定するの初めて見た気がするな。
これAとBが逆だったら解けてただろうな。いやなんで？？
一度やり方が見えなくなると焦ってしまって、ガチャ結果がどれも当てはまらないように見えてしまうのかも。こころの問題。
高難易度帯では通用しないだろうけど、ひとまずは「いうて自分の知識と思考力で解けないことはないやろ」くらいに高を括ってしまうのが良いのかな。
B問題
若干焦ったけど解けた。K個に分けるの面倒で無意味にバグるからやめてほしいです。
C問題
これは完敗かも。自分の知識にないDPだったけど、正直今のDPのやり方が解法ガチャに依存しすぎているのでもう少し抽象的なやり方を身につけたいね。
解説見たけど三分の二は完全に何？という感じ(そもそも言い換えからして考えなかったな......)。
すぬけさんの動画見た。これ水色diffってマジ？ dp[i][j][k] まではうんうんそうですね～っていうか何でこれ思いつかなかったの？ だったけどそこからkを落とすところで草生えた。そっかぁ......。
dp[i][j][k]に行くまで
ある経路に対して、通っていない空白マスごとに3をかける必要がある。関係ないマスの文字は自由に決めていいからね。
ので、k = それまでに通った空白マスの数として dp[i][j][k] でやると解ける。ここにすら行ってなかったのはダメ。
今まであまりこんな遷移の問題をやったことがなかったとはいえ、通ってない空白マスごとに3をかけることすら分からないの、数弱の面目躍如だな。頭大丈夫か？
kを落とすまで
この発想の転換は正直言われてもしばらく意味が分からなかった。難しくて困るんだよね。
お気持ちというか、再現しやすい考え方としては
- やっぱり「通ってない空白マス」を扱おうとすると係数をかけるときに必要な情報をDPの状態として持つ必要が出てきてつらい
- 出来るだけ「通っている空白マス」でやっていきたいですね
- 空白マスを踏むごとに、情報を更新できるとうれしい
- 最初のマスの係数を
として取っておくと、空白マスを踏むごとに1/3していけばいい ← 大天才過ぎて困る
でもDPとして考えると、最初のマスで係数として を取っておくことを考えるのはまあまあ自然な気がする。そうするとこの更新もまあ自然な気がするなあ。
自分の頭が悪いと困っちゃうね。
DはTLを見る限り天才っぽいので困るな。Eの方が典型っぽいけど......？
