2020/01/16
キーエンス プログラミング コンテスト
Solved By kkktym
Topcoder: 0
Codeforces: 241
AtCoder: 1503
AOJ: 62
yukicoder: 10
library-checker: 0
Sum: 1816
ACRate: 1888 -> 1866
キーエンス プログラミング コンテスト
ABC 3完 (60:55+2ペナ) 冷えた、あかん
A - Two Sequences 2
Cn を決める際に新たに An と Bn のみチェックすればいいだけということはわかる。Cn = max(Cn-1 , max(Ai)*Bn) (1 <= i <= n) なので、Aの最大値を保持しておけばできる。
B - Mex Boxes
非常にこどふぉっぽさを感じた。まず 0 の数が X 個 (<= K) だった場合 K - X 個の箱については 0 が表示されることが確定する。確定した箱については除いて次に 1 について同じように見る。なんか変な実装をして 1 ペナもらってしまった。本当にダメ。
C - Robot on Grid
マスの位置を状態に持ってそのマスに到達できる経路数を管理するDPで、書いてある文字に応じて遷移が変わるやつ。ここまでが典型で、あとは全ての盤面についての経路数を考えないといけないところがちょっと考えるポイント。遷移する時にうまいこと数えられないかを考える。例えば、あるマスから右に移動した時には移動元のマスより下にある空白マスについては通らないことが確定するので、自由に文字を選べることになる。空白マスの数を X とすると 3X を経路数にかけてあげればよし。前処理として、各マスの右にある空白の数、下にある空白の数を求めておく。サンプル 3 をコードテストにぶち込んで 1681 ms を確認！提出！→ MLE！？初めてMLEになってめっちゃ焦る。でもよく見ると 1024MB 制限のところを 1078MB だったので、ひと工夫でいけそう。DP 配列を使い回すことにして改造。 しかし、めっちゃバグらせて 20 分も使ってしまった...
D - Choosing Up Sides
一回のチーム分けで同じチームになるペアの数は Comb(2N-1, 2)*2 増える。全ペア数は Comb(2N, 2) なので、この最小公倍数をとりたくなる。すると結局、(n, m) = (2N-1-1, 2N-1 ) となることがわかる。これはもらったぜ！と思ったがここからが本番で、うまい構築が全然できずに死。 こんなのは綺麗な簡単な構築法があるはずなんですよね、手でがちゃがちゃやるんじゃなくてそれを考えるべきだった...
ARC108 D - AB
コンテスト前にウォーミングアップを兼ねて通しておいた。場合分けをすればいいことはもう知っていたので、した。A と B の対称性をうまく処理できなくて WA が嵩んでしまった。
おさんぽ
たまたま家の近くに哲学の道があるので散歩した。もう inf 回散歩したけど、来年からできなくなることを考えると既に郷愁の念で胸がいっぱいです。
まとめ
結構気合を入れて参加したコンテストで冷えて悲しい。でも最近明らかに高難度が通せるようになってきてるのは確かなので気にせずがんばる。
