久しぶりですが、プログラミングコンテストに参加しました。解けた問題だけ考察を書いていきます。

天下一プログラマーコンテスト 2018

概要
「天下一プログラマーコンテスト」はガチンコの競技プログラミングコンテストです。今年もジャッジシステムや問題の作成・監修にAtCoder社が全面協力。
最強最速アルゴリズマーは誰だ!?

私はD完でした。

C - Align

問題概要：数列を適当に並べ替えて、隣接2項の差の合計を最大化せよ。

考察：

例えば数列 3,1,4,1,5,9 が与えられたとします。これをうまく並び替えると、

列  4   1   9   1   5   3 
差    3   8   8   4   2

となり、差の合計は 25 です。

明らかに大小大小……と交互に並べるのがよさそうです。小さい要素を「小」の位置に、大きい要素を「大」の位置に配置していきます。

あとはどの要素を端にするかですが、差の合計の式を考えると大きいプラスと小さいマイナスを優先したいので、中央値に近い要素を端に置くのがベストです。

まとめると、空の配列 (deque) を用意して、先頭に最大、末尾に最大、先頭に最小、末尾に最小の順で挿入していく、みたいな手続きでOK。最初に最大値を使うか最小値を使うかは、両方試せばよいでしょう。(※解説によるともっと簡単に実装できるそうです。)

筆者の解答

D - Crossing

問題概要：整数 N に対して、次の条件を満たす集合列が存在するか判定し、存在するなら一例を示せ。

1. どの整数 i (1 ≤ i ≤ N) についても、i を含む集合がちょうど2つある
2. どの2つの集合についても、共通して含まれる要素がちょうど1つある

考察：

集合の個数を K として、N = (1/2) K (K - 1) (= 3, 6, 15, ..) とできるなら、集合列を構成できます。次のようなグラフを考えればいいからです。

頂点数 K のグラフを作り、すべての頂点の間に辺を引きます。辺の個数は N 個ですから、 1~N を適当に割り振ります。各頂点につき、その周辺にある辺につけられた値をその集合の要素とします。これは条件を満たします:

1. どの i も、i がかかれた辺の両側の頂点 (集合) にしか含まれないから
2. どの2集合も、それらの頂点の間にある辺にかかれた値だけを共通して含むから

逆はどうでしょうか。

集合は他の集合と共通して含んでいる要素だけを持ちます。実際、もしそれ以外に要素を持っていたら、その追加の要素は3つ以上の集合に含まれていることになるからです。したがって、集合の要素数は (K - 1) です。

すべての集合には 1~N が2回ずつ出現するので、要素数の総和は K (K - 1) = 2N であり、 N = (1/2) K (K - 1) が必要になります。

したがって、 N = (1/2) K (K - 1) のときにしか構成できず、それなら上記の方法で構成できる、というのが正解です。

筆者の解答

おわりに

前回の AGC (参戦記なし) に惨敗してがっくりしてましたが、今後もまったりやっていきます。