naoya_t@hatenablog

いわゆるチラシノウラであります

KEYENCE Programming Contest 2019 / キーエンス プログラミング コンテスト 2019

1/13(日) 21:00-23:00
2完でレート盛大に冷やした(1710→1642)
f:id:n4_t:20190113233045p:plain
C問題読み違えてましたね

A - Beginning (100)

vectorに入れてソートして{1,4,7,9}と比べた
→AC 2:23
https://atcoder.jp/contests/keyence2019/submissions/3998813

C - Exam and Wizard (400)

最小数のAを並べ替えてBをカバーさせる問題を自作して解いておりました
1WA出した後飛ばして

終了後

ああ、A同士で数を融通していいのね
それだったらめちゃ簡単なのでは?(足りない所がいくら足りないか合計する。余っている所がいくらずつ足りないかリストアップして降順ソートしておく。大きい順に補填していく。)
4分で解けて泣きそう
→AC
https://atcoder.jp/contests/keyence2019/submissions/4009278

D - Double Landscape (500)

サンプルケース#4が合わないまま試合終了;

終了後

縦横に同じ数があればその交点にその数が来るのは良いとして、そういう形で使われなかった場合にも必ず1回は出現しないといけないからその場合nCkのnとkを減らす必要があるのを見落としていた(そこに気づくまでが長かった)。

そこのところを考慮して数え上げて
→AC
https://atcoder.jp/contests/keyence2019/submissions/4010753

E - Connecting Cities (600)

(後日)
漢字の「山」の各頂点に都市があって、辺を辿って繋がっている感じの配置。これで最小全域木を作る。
ある都市iから見て、

  • 右にある都市jとの距離は A_i+A_j+D(j-i) = (A_i-D_i) + (A_j+D_j)
  • 左にある都市kとの距離は A_k+A_i+D(i-k) = (A_i+D_i) + (A_k-D_k)

即ち、ある都市iより右にあるすべての都市について (A_j+D_j) を求めておけば、その値が最小になる都市jが都市iの右側で一番低コストに接続できる都市である。(左も同様)。
(±の入れ替え面倒なので、reverseして同じことをやった)
で、そういう都市間の辺だけ残してあとは捨ててしまうことで辺の数はO(N^2)からO(N)になる。そこまで行けば最小全域木の構築は余裕では?
孤立した集合が出来てしまったりしないのか不安なので、確実に全てが繋がるように余分に辺を取ってみたけれど
→WA(1)
「反例界のtouristさん(鍵垢)」が挙げていた

4 2
1 4 4 1

で確かに落ちる。(22を返すべきところで23が出てくる。要は左端と右端を結ぶ辺が考慮されていない)

解説を読んだ

A_iの値を昇順ソートしてからほぼ同じことをやっている。
都市i(※ソートして振り直した新IDで)と結ぶのは都市1〜都市i-1まで(即ちA_iの値がより小さいもの)で、ソート前に左だったものから1つ、右だったものから1つ辺を選抜する。
新IDの若い順にRMQに足していって(左右別々に用意し、左にはA_i-D\cdot iを、右にはA_i+D\cdot iを追加)、一番コストの低い都市を見つけるようにした。
→AC
https://atcoder.jp/contests/keyence2019/submissions/4026888

元のWA解と何が違うんだろう?

  • 元のWA解では、都市iより右にあるすべての都市からコスト最小を1つ、左にある(〃)1つ選んでいる
  • AC解では、都市iより右にある、A_i\le A_j な都市の中からコスト最小を1つ、左にある(〃)1つ選んでいる

元のやつのほうが有利な気さえするのだけれど、前述のような反例で落ちるわけだし、どうも腑に落ちない。

解説や皆さんのブログ等を参考にしつつ考えてみる

(続く)

F - Paper Cutting (900)

(未読)