Mitarushi さん原案。自力では初手の多項式で剰余を取るパートから気づかなかった。その後も正しく立式して 多項式の諸演算を実装する必要があるので、解説を見た後に通すのですらかなり苦労した。個人的には 0 AC 筆頭だと思っていたが、本番では hos_lyric さんに解かれていて感嘆した。
G: Graph Weighting (800)
tokusakurai 原案。グラフと最適化。原案当初は 固定かつ最適化パートはなしの構築問題だったが、運営陣から簡単という意見を多数受けたので強化をすることとなった。数え上げにする案もあったが、のいみの案をさらに強化をする形で現在の問題となった。ステップが 3 つ程あって、どれも突飛なものではないため難易度推定は難しかったが、本番は 6 AC と想定より多くの人に解いてもらえた。
H: Huge Segment Tree (700)
SSRS さん原案。SSRS その 2。中難易度数え上げその 2。問題設定が面白い。想定解は多項式で立式して式変形を重ねているが、分割された区間の一番長い部分がどの段にあるかで場合分けして立式しても畳み込みの形になって解ける。当日運営の控室で SSRS さんに H は fps 経由しなくても解けるという話をしたら、fps ではなく多項式だと説教された。
最終的な結果を見てもだいぶ難しいセットだったと思いますが、簡単枠が嘘解法を誘発するような問題ばかりだったのが全体としての AC の低さに大きく寄与しているのだと思います。Universal Cup でもトップのチームにもギリギリ全完されないくらいの難易度だったのは良いですが、多くのチームにとって高難易度の面白い問題に割ける時間が短くなってしまったのは調整ミス感があります。全体的にも WA が発生しやすい問題が多かったので、その辺りをふまえた難易度調整は今後の課題になると思います。5h という枠に囚われず、より長いコンテスト時間や Day1 Day2 という方式にするのもありですね。
感想
個人としては作問活動をするのは初めてで、その中で 2 問出題できたのは非常に良い経験となったので、今後も作問活動を行っていきたいです。コンテストとしては問題名や問題文など細部までこだわり、clar も 0 と非常に質の高いものができたと思っています。会場をお貸しいただいた MC Digital 様、コンテストサイトを提供いただいた AtCoder 様、ご参加いただいたコンテスタントの皆様にこの場を借りて感謝申し上げます。
乗車した車両は JR 西日本の W7 系。JR 西日本車両にのみ搭載されている車内チャイム「北陸ロマン」がかなり好きなので、気分が高揚した。座席に着くと、備え付けの JR 東日本車内サービス誌「トランヴェール」と北陸新幹線敦賀開業が特集されている雑誌を読んだ。私が中高時代のトランヴェールは今のものよりも大きく、巻末に JR 東日本の路線図が載ってていたのだが、それがなくなっていたのは残念である。今年 3 月の北陸新幹線延長開業はホットな話題であるが、かがやき号が金沢以遠で各駅停車になるというのには腰を抜かしてしまった。新幹線の最優等種別が県庁所在地駅を容赦なく通過していくのは個人的には好みなのだが、途中から失速してしまうのは悲しい。
大宮駅までは最高 130 km/h なので、在来線と同程度の時間を要する。しかし、ここからがかがやき号の真骨頂で、大宮を出ると次の長野まで約 200 km をノンストップで走り抜ける。とりわけ上越新幹線と分岐する高崎駅までは最高 275 km/h で走るので疾走感を感じられる。高崎駅を出た後は最高 260 km/h となり、トンネル区間も多いため速度はやや控えめとなる。実際地図を見ると、この区間で平地を走るのは高崎・軽井沢・佐久平・上田・長野駅近辺のみであることが確認できる。それでも在来線だと半日かかる大宮長野間を 55 分というのは驚異的なスピードである。
公苑内には人間用の温泉もあったが、そこはかなり古いうえに完全に観光地価格だったので、一旦バス停の方まで引き返すことにした。山を下った後は次のバスが一時間半後だったので、ひとまず湯田中駅に向かって足を進める。歩いている途中で日帰り入浴可能な温泉施設「みやま温泉わくわくの湯」があったので、衝動的に立ち寄った。料金は 500 円で受付は常駐しておらず、硬貨を投入するとゲートが通れるようになるというシステムになっていた。浴場への入口を開けるとまず体の洗い場があり、そのさらに先の入口を開けると露天風呂がある。先客はいなかったので、5 m 四方以上もの広々とした露天風呂を占有できた。屋根に積もった雪がぱらぱらと降ってくるのも風情があり、気分が良かったので随分と長居をしてしまった。
WITH T1 AS(
SELECTCOUNT(DISTINCT SESSION_ID) AS CNT_ALL
FROM
PURCHASE_HISTORY
), T2 AS(
SELECT
*,
COUNT(DISTINCT SESSION_ID) AS CNT_A
FROM
PURCHASE_HISTORY
GROUPBY
ITEM_CODE
), T3 AS(
SELECT
P1.ITEM_CODE AS ITEM_A,
P2.ITEM_CODE AS ITEM_B,
COUNT(*) AS CNT_AB
FROM
PURCHASE_HISTORY AS P1
CROSSJOIN
PURCHASE_HISTORY AS P2
WHERE
P1.SESSION_ID = P2.SESSION_ID
GROUPBY
P1.ITEM_CODE,
P2.ITEM_CODE
), T4 AS(
SELECT
ITEM_A,
ITEM_B,
CNT_AB,
TA.CNT_A AS CNT_A,
TB.CNT_A AS CNT_B
FROM
T3
INNERJOIN
T2 AS TA ON ITEM_A = TA.ITEM_CODE,
T2 AS TB ON ITEM_B = TB.ITEM_CODE
WHERE
ITEM_A != ITEM_B
), T5 AS(
SELECT
*
FROM T4
CROSSJOIN
T1
), T6 AS(
SELECT
ITEM_A,
ITEM_B,
ROUND(100.0 * CNT_AB / CNT_ALL, 5) AS SUPPORT,
ROUND(100.0 * CNT_AB / CNT_A, 5) AS CONFIDENCE,
ROUND(1.0 * CNT_AB * CNT_ALL / (1.0 * CNT_A * CNT_B), 5) AS LIFT
FROM
T5
ORDERBY
LIFT DESC,
SUPPORT DESC,
CONFIDENCE DESC,
ITEM_A DESC
)
SELECT
*
FROM T6
SUM や MAX などの集約関数の後ろに OVER 句をつけることで、列の値全体を使った計算をすることができます。集約を行うグループごとに 1 行にまとめられるのではなく、各行のデータを残したまま計算結果を付与できるのが GROUP BY 句を使う場合との大きな相違点です。
使い方
ウィンドウ関数は以下のような構文で使うことができます。
aggr(column_1) OVER(PARTITION BY column_2 ORDERBY column_3)
ここで、aggr は SUM や MAX などの周約関数です。
PARTITION BY 句
column_2 の値ごとに分類した後に集約することができます。ここは GROUP BY column_2 で集約するのと同様です。
PARTITION BY 句を省略することもでき、その場合は全体が 1 つのグループとなります。
ORDER BY 句
column_3 をキーとしてソートした後に、先頭行から該当する行までだけを集約することができます。この ORDER BY 句の後に ROWS BETWEEN x PRECEDING AND y FOLLOWING と続けると、該当する行の 行前から 行目後まで (inclusive) だけを集約することもできます。より詳細な行の指定方法については、以下の記事が参考になります。
ORDER BY 句を省略することもでき、その場合は PARTITION BY 句で分割されたグループごとに全体を集約します。
使用例
以降では、このウィンドウ関数の具体的な使用例について見ていきます。
順位付け
以下の表 TITLE_RANKING において、TITLE の降順に順位を付与することを考えます。
NAME STATE TITLE
-------- ------ -----
fujii active 19
habu active 99
nakahara retire 64
ooyama retire 80
tanigawa active 27
watanabe active 31
yonenaga retire 19
集約範囲を全体にして RANK 関数を適用すればよいです。
SELECT
*,
RANK() OVER(
ORDERBY TITLE DESC
) ASRANKFROM
TITLE_RANKING
ORDERBY
STATE ASC,
RANKASC;
NAME STATE TITLE RANK
-------- ------ ----- ----
habu active 99 1
ooyama retire 80 2
nakahara retire 64 3
watanabe active 31 4
tanigawa active 27 5
yonenaga retire 19 6
fujii active 19 6
STATE で分類して順位をつけることもできます。
SELECT
*,
RANK() OVER(
PARTITION BY STATE
ORDERBY TITLE DESC
) ASRANKFROM
TITLE_RANKING
ORDERBY
STATE ASC,
RANKASC;
NAME STATE TITLE RANK
-------- ------ ----- ----
habu active 99 1
watanabe active 31 2
tanigawa active 27 3
fujii active 19 4
ooyama retire 80 1
nakahara retire 64 2
yonenaga retire 19 3
