京都大学プログラミングコンテスト 2020 出場記
A
座標同士のマンハッタン距離の累積和を求める問題。 距離の計算方法も問題文に書いてあるので、その通りに計算してACを得た。
B
最大で [100, 10000] サイズの整数行列の各行から1個ずつ数を拾っていって、拾い続けた数列が広義単調増加 ( a >= b, b>= c, ... ) になるような組み合わせ数を求める問題。
DPで解けそうな感じがしたけど、計算量が O(NK^^2) になってTLEの嵐だった・・
行末から値を選択していくことにして「n行目に 値x を選択したときの組み合わせ数」を dp[n][x] としてた。しゃくとり法などを用いて計算量を削減できないかなーと思ったけど、この問題は数字を選択するための数列が毎回変わるので適用できるイメージがわかなかった。時間をかけまくったけ全くわからず。
C
部分点がもらえるという問題を初めて見た。ABCでも昔は登場していたようだ。
問題文を読んでもどのような文字列の重複が評価されるのかイメージがわかなかったので、それを判定するコードを書いてみた。グリッドの横・縦それぞれに2文字以上の部分文字列をすべて列挙する感じだった。 それで重複を回避するグリッドを生成するコードを書こうと思ったけど、時間がなかったので 6x6 のグリッドを手作成してAC(60点)を得た。
D以降
問題を見なかった
