キーエンスプログラミングコンテストの感想
キーエンスプログラミングコンテストに参加しました。
問題はこちらから。
結果はこんな感じでした。
a,bの2完(0wa)
順位：2180 / 3850
パフォーマンス：794
もうちょっとうまくできたかなという印象です。とくにA問題がなかなか解けずに焦りました。どんどん時間が経つにつれてさらに焦りました。
でも、レーティングを維持できたので、まあ良しとしましょう。現在はまだ水色の問題を解くよりも、茶色、緑色の問題をこなす勉強をしているので、とりあえずの目標は達成です。問題もそうですが、焦らずいきましょう。
A問題
数列a,bのn番目までの各要素の積の最大値cnを求めます。ただし、bの要素はaの要素以上のインデックスのものを用います。
はじめは、bの要素の条件を見ていなくて、なんだ簡単じゃんって思いました。が、そんなに甘くはありませんでした。
いろいろ考えて
答えの出力はiが増加するにつれて大きくなるはず。
ということに気づきまして、aiとbiが今までの最大値を超えたかどうかで場合分けをしようということになりました（これもまだ正しくないです）。
ma = i-1までのaの最大値
mb = i-1までのbの最大値
とすれば、
ma<=ai && mb <= bi
ma > ai && mb > bi
ma > ai && mb <= bi
ma <= ai && mb > bi
この4つですね。問題なのは4個目です。ma <= ai && mb > biでaiは大きいけど、biは小さいときです。maの値を更新したいけど、そうするとbi*aiが最大値になるのか？もうそうだとして、例えば、i+1でさらにbi>b(i+1)のときにどうするのか？
となりまして、頭がパンクしました。
結局、
aは i<=nのどれでも使える。と考えると、ma*biが今までの答えよりも大きくなるか？でよさそう
となりました。つまり、
ci = max(max(a0,...,ai)*bi, c(i-1))
が答えです。45分かけて無事AC。いっぱい考えて、答えはこの一行って考えると、なんか面白いですね。数学だ。
Ｂ問題
k個の箱にn個の数字が書かれたボールを詰めていきます。箱に入っているボールに書かれた数を除いた、非負の最小値がその箱のスコアになります。kこの箱のスコアの最大値を求めましょう。
これは、ぱっとこたえがわかりました。
小さい数字から各箱に詰めていくと(数は適当です)
1箱目：0 1 2
2箱目：0 1 2 3
3箱目：0 1 2 3
4箱目：0 1 2 3 4 5
こんな感じです。6はないものとして、6以上は無視します。
あとはここに書かれた数の個数が答えになります。要はこのヒストグラムの面積です。
ここで、箱の数はK以下、数i+1は 数 i の個数 ni より多く存在してもniとする（5が2000個あっても、1とします）。
Ｃ問題
似たような3次元のDPがあったので、そんな感じで解けないかなーっていろいろとやっていました。
以下試験中の考察です（間違ってます）
dp[i][j][k] : i,jに、kと書かれたときのi,jまでの行き方
もし、R,D,Xのいずれかが書かれていたら(Rとする）
dp[i][j+1]['R'] = dp[i][j]['R']
dp[i][j+1]['D'] = dp[i][j]['R']
dp[i][j+1]['X'] = dp[i][j]['R']
D,Xのときも同様に行います。
何も書かれていなかったら、R,D,Xの全てが書かれているとみなして、すべての遷移を行います。
実装をしましたが、テストケースが合わず。よくよく考えてみたら、書き込み方が3^(HW-K)通りあるんだから、そこをなんも考慮してないということに気が付きました。
じゃあ、3^(HW-K)から到達できないのを引いてやろうと思いましたが、30秒考えて、違うと悟りました。
でも、解答を見るに3^(HW-K)から引き算ではないにしろ、減らすようでした（ぱっと見ただけなので、おそらくですが、、）。
まだまだ、C問題は遠いですね。
この記事が気に入ったらサポートをしてみませんか？