KEYENCE Programming Contest 2019

ABCDの4完438位を果たし、ビギナーコンテスト以外で初めての青パフォ(1708)を獲得した！実験だいじ。

A - Beginning (100点)

問題: A - Beginning
順番が関係ないので、４つの数字を小さい順にソートして、[1, 4, 7, 9]になっていればYESを出力する。

拙解 (C++):
Submission #3998594 - KEYENCE Programming Contest 2019 / キーエンスプログラミングコンテスト 2019

B - KEYENCE String (200点)

問題: B - KEYENCE String
正しくスマートな解法に到達するまでに4WAを連打してしまった（反省）
$S$ の両端から何文字 "keyence" に一致するかを数えて、合わせて |"keyence"| 以上ならば中をくりぬいて "keyence" が作れるので、YESを出力する。どちらか一方が0でも片方が7以上つまり完全に一致していればYESなことに注意する…という問題かと思っていたが、どうやら「…keyence」「keyence…」の形のテストケースはなかったらしい*1。

拙解 (C++):
Submission #4002299 - KEYENCE Programming Contest 2019 / キーエンスプログラミングコンテスト 2019

C - Exam and Wizard (400点)

問題: C - Exam and Wizard
なかなか手こずった。しかし、色々実験して「順番は関係ない」「足りない分は否が応でも変えざるを得ない」ということに気づくと、「余剰分が大きいほうから配分を割り振る」という貪欲で通った。
具体的には、まず新しい配列 ${V_i:=A_i-B_i}$ を作ってソートし、累積和を取っておく。lower_boundで0以上の最初の項を探してそれ以前の負の項の総和（=足りない分）が、大きいほうから何項の和で賄えるか、というのを一つずつ見ていくと、 ${O(N)}$ で解ける。

拙解 (C++):
Submission #4005842 - KEYENCE Programming Contest 2019 / キーエンスプログラミングコンテスト 2019

D - Double Landscape (500点)

問題: D - Double Landscape
BとCで時間とWAを大幅に食ってしまい、終了30分前に取り掛かった時点でac-predictorが緑パフォを指し示しており、これはやばいと思いつつ解いた。結果解けたので良かったが…
これは紙とペンを駆使して解いた。
まず、最大値が制約になっているので、より大きい値がより制約が多い。列と行の順番は関係ないので、 $\{A_i\}$ と $\{B_i\}$ をソートする。したがって大きい値 $NM$ から始めて、一番最大値の大きい右下のところから書き始めるのがいいとわかる。
そして、今書こうとしている値 $K$ が書き込める範囲（つまり ${K \le A_i \land K \le B_j}$ ）を見たとき、その左端の列・上端の行が等しいかどうかによって４通りの場合分けができる。