WITH T1 AS(
SELECT
SESSION_ID,
CAST(SUBSTR(PROCESS_ID, -1) ASINTEGER) AS PROCESS_ID,
EX_TIMESTAMP,
MAX(EX_TIMESTAMP) OVER(
PARTITION BY SESSION_ID
ORDERBY PROCESS_ID ASC
) AS PRE_TIME,
MIN(EX_TIMESTAMP) OVER(
PARTITION BY SESSION_ID
ORDERBY PROCESS_ID DESC
) AS NEXT_TIME
FROM
PROCESS_LOG
),
T2 AS(
SELECT
SESSION_ID,
PROCESS_ID,
COUNT(*) OVER(
PARTITION BY SESSION_ID
ORDERBY PROCESS_ID ASC
) AS PRE_CNT
FROM
T1
WHERE
EX_TIMESTAMP = PRE_TIME
AND EX_TIMESTAMP = NEXT_TIME
),
T3 AS(
SELECTMAX(PROCESS_ID) AS PROCESS_ID,
COUNT(*) AS CNT
FROM
T2
WHERE
PROCESS_ID = PRE_CNT
GROUPBY
PROCESS_ID
),
T4 AS(
SELECT1AS PROCESS_ID
UNIONALLSELECT
PROCESS_ID + 1AS PROCESS_ID
FROM T4
WHERE
PROCESS_ID < 5
)
SELECT'STEP' || T4.PROCESS_ID AS PROCESS,
CASEWHEN T3.CNT ISNULLTHEN0ELSE T3.CNT
ENDAS CNT
FROM
T4
LEFTOUTERJOIN
T3 ON T4.PROCESS_ID = T3.PROCESS_ID
H 問題は torisasami が見えていて、燃やす埋めるになりそうというので、とりあえず最大流を写経して確認してもらう。考察の話を聞くと、実際に燃やす埋めるの形に帰着で来ているので書いてみる。サンプルの出力が答えの約 2 倍になるのでおかしいなと数分考えてしまったが、ペアを重複カウント & 同じもの同士のペアもカウントしてしまっていた。修正するとサンプルが合ったので、提出 (2:58 AC)。
残りはもう 3 問しかなく、順位表的に解かれているのは I と J。J は貪欲で良さそうと 2 人が言う。もしこの貪欲が正しければ HLD + 遅延セグ木で解けるので、とりあえずそれを書いてみることにした。この 2 つの写経は AOJ ICPC の Do use segment tree と全く同じ状況なので、その問題のタイムアタックをしていた甲斐があったなと思ってなんだか嬉しかった。実装は 30 分くらいでできたが、提出すると WA が出る。冷静にコードを見返すと、遅延セグ木で頂点 に該当する情報をそのまま 番目の点に入れてしまっていたのに気づき、修正して提出するとまたも WA が出る。この辺りで、貪欲も良く考えたら嘘くさくないかと思うようになり、反例を考えるもそちらもなかなか作れないという歯痒い状況に陥ってしまった。
J は貪欲が嘘だと沼なので、より解かれている I に一旦向かうことにした。torisasami は濃度でソートして貪欲でできないかということを考えていたが、私は見た目が LP なのでそちらの線で考えてみることにした。sapphire15 が双対を取ったらどうか？と言ってきたので、丁寧に行列表現に書き下して双対を取ってみる。その間に sapphire15 が J の貪欲の証明ができたと言うので改めてコードを見返してみると、遅延セグ木の初期化の部分を修正していたつもりがまだ間違っていたのに気づいて蒼ざめた。再修正して提出すると今度は AC (4:19 AC)。このミスはあまりにも初歩的すぎて本当に申し訳なかった。
残った時間で I を考えていたが、双対 LP をこねくり回しても釈然としない。torisasami は最後の希望にかけて自明な必要条件を書く。ラスト 2 分でサンプルがあって提出するも、さすがにそれで通るほど ICPC は甘くない。ここでタイムアップとなった。
WITH T AS(
SELECT
MEMBER_CODE,
MIN(DATE(LOGIN_DATETIME)) AS MINDATE
FROM
ACCESS_LOG
GROUPBY
MEMBER_CODE
)
SELECT
MINDATE AS FIRST_LOGIN,
COUNT(*) AS MEMBER_CNT
FROM
T
WHERE
MINDATE BETWEEN'2023-08-01'AND'2023-08-31'GROUPBY
MINDATE
ORDERBY
FIRST_LOGIN DESC
問題 3
まず最初に 7 月中の最初の受注日をまとめるテーブルを作り、その次に 7 月中の最初の受注日より 1 年以上前の受注日の MAX をまとめた表を作りました。最後に、2 番目に作った表で受注が NULL でない人だけ表示するというコードを書き、開始約 30 分後にサンプルが合ったので出してみますが WA が出ます。その後、なぜ落ちるのかわからずほぼ同じコードを投げてみますが通りません。しばらくして、1 年以上前にも、1 年以上前より後にも両方受注がある場合にバグることに気づきます。受注の MAX を 7 月中の最初の受注日より前に取り、その値が 1 年以上前であるのみ表示するように書き換えることで、開始約 52 分後に AC しました。
WITH T1 AS(
SELECTMIN(ORDER_DATETIME) AS ORDER_DATE,
MEMBER_CODE AS CODE
FROM
EC_ORDERS
WHEREDATE(ORDER_DATETIME) BETWEEN'2023-07-01'AND'2023-07-31'GROUPBY
MEMBER_CODE
),T2 AS(
SELECTMAX(DATE(ORDER_DATETIME)) AS LAST_DATE,
EC_ORDERS.MEMBER_CODE AS CODE
FROM
EC_ORDERS
INNERJOIN
T1 ON EC_ORDERS.MEMBER_CODE = T1.CODE
WHERE
ORDER_DATETIME <
CASEWHEN ORDER_DATE ISNULLTHEN'0000-01-01'ELSE ORDER_DATE
ENDGROUPBY
EC_ORDERS.MEMBER_CODE
)
SELECT
ORDER_DATE,
T1.CODE,
CASE OPTOUT_TYPE
WHEN0THEN'可'WHEN1THEN'不可'ELSE'不明'ENDAS OPTOUT
FROM
T1
INNERJOIN
MEMBER_MST ON T1.CODE = MEMBER_MST.MEMBER_CODE,
T2 ON T1.CODE = T2.CODE
WHERE
LAST_DATE ISNOTNULLANDDATE(LAST_DATE) < DATE(ORDER_DATE, '-1 year')
ORDERBY
ORDER_DATE DESC,
T1.CODE DESC
WITH T1 AS(
SELECTSUM(
CASE KIND_CODE
WHEN'100'THEN TOTAL_VALUE
ELSE0END
) AS VAL,
SUM(
CASE KIND_CODE
WHEN'150'THEN TOTAL_VALUE
ELSE0END
) AS CNT,
RANK() OVER(
ORDERBYSUM(
CASE KIND_CODE
WHEN'100'THEN TOTAL_VALUE
ELSE0END
) DESC,
SUM(
CASE KIND_CODE
WHEN'150'THEN TOTAL_VALUE
ELSE0END
) ASC,
PF_CODE ASC
) AS RNK
FROM
CONVENIENCE
WHERE
SURVEY_YEAR = 2019GROUPBY
PF_CODE
), T2 AS(
SELECTSUM(VAL) AS VAL,
SUM(CNT) AS CNT,
(RNK + 2) / 3AS GRP
FROM
T1
GROUPBY
GRP
ORDERBY
GRP ASC
), T3 AS(
SELECT
T2.GRP,
T2.VAL,
T2.CNT,
SUM(
CASEWHEN MT2.GRP <= T2.GRP THEN MT2.VAL
ELSE0END
) AS CUMVAL,
SUM(
MT2.VAL
) AS ALLVAL
FROM
T2
CROSSJOIN
T2 AS MT2
GROUPBY
T2.GRP
)
SELECT
GRP AS NO,
VAL AS TTL_SAL,
ROUND(100.0 * VAL / ALLVAL, 1) AS PER_SAL,
ROUND(100.0 * CUMVAL / ALLVAL, 1) AS CUM_SAL,
VAL / CNT AS AVG_SAL
FROM
T3
WHERE
NO <= 10ORDERBY
NO ASC
私が F を実装している間に二人は G の考察を済ませていたようで、高々 30 手でゲームが終わるので状態数は になるのでメモ化再帰で間に合いそうということです。メモリが結構かさみそうなので生配列で十分な長さの配列を確保しておいた方がメモリ節約に効くかと思い、長さ の生配列を用意してみたら、仮想環境のメモリが少ないせいで手元で RE しました。仕方ないので unordered_map を使って実装して、提出すると WA が出ます。0 個の山に対して操作するのを許容する実装をしていたので、そこを修正すると通りました (1:10 AC)。
K は torisasami が解けていそうだったので完全に任せることにして私は sapphire15 と J を考えました。同じ x 座標の点の個数で平方分割というアイデアが出て、大と大、大と小の組み合わせは簡単にできそうです。残る小と小は苦戦しましたが、sapphire15 が反対の座標に注目するといういいアイデアを思いついて解決します。toriasami は K でペナを出していたので、一旦コードを印刷してもらってその間に J の実装を進めました。
残っている問題で通されている問題が B のみだったので、torisasami に B を読んでもらっていたのですが、難読で正しく理解できているか怪しいということを聞きました。一緒に一行ずつ読み進めていきます。彼は挿入した後のものに対して編集操作をできるのかどうかがわからなかったようですが、さすがにそんな訳はありません。それはなしという方向性で考えると、 の長さ 以下の全文字列について との編集距離がわかれば DP できるのがわかったのですが、これは愚直にやると 時間かかるところ始点を固定することで でできます。その後は edit distance のライブラリを写経して無事 AC できました (2:21 AC)。
残るは AC なしの D,H,I 問題で、その中でも H は明らかにグロそうだったので見なかったことにして sapphire15 が D を、torisasami と私が I を考えました。I は良さそうな DP を思いついた気がして時間もなかったので適当に書き始めていたのですが、書いているうちに普通に 2 乗じゃんとなって終了しました。sapphire15 は D の良さげな方針を思いついていたようですが、どう実装に起こすのかを思い描くことができませんでした。
最終結果は 7 完で 4 位でした。最後に 2 問通して追い上げましたが、中盤の空白が長すぎてだめでした。特に F 問題はラグランジュの反転公式を使うようで、この公式自体は知っていたものの実戦で使えるレベルには習得できていないということなので、自分の未熟さを感じました。SSRS さんは F を実験エスパーで式を見つけたと仰っていたのですが、そんなことができるのかと俄かに信じがたかったです。あとは実装力が課題で、E を実装する時間が長すぎたのと、解法までは見えていた D に取り組む時間がなかったのが悔やまれます。
風呂上がりで疲れがどっときて、眠さがピークに達している状態で ABC が始まります。C が少しめんどかったものの A から E まではあまり詰まらずに解け、F も大まかな解法はすぐわかりましたが細かいところを詰めるのに苦労しました。残る G は判定問題を最大流問題に帰着できることはすぐにわかりましたが、計算量を落とす部分で詰まります。このあたりで無意識に唸っていたようで、後にルームメイトから指摘されました（ごめんなさい）。結局前回の universal cup でやった手法で になりそうなことがわかったので、重い腰を上げて実装を始めます。終了 1 分前にやっとこさサンプルが合ったので出してみるとまさかの TLE で、実はフローを流すかどうかを見る部分で かかっていました。ABC が 7 問体制になって問題数が減ったにもかかわらず 2 連続で全完に失敗し、心も体もクタクタになりました。
ABC 終了後は krps さんが C で詰まっていたことを知りました。 の 3 重ループを回すのが実装楽そうと言ったもののあまりピンと来てないようだったのですが、一度止めたリールを再開できると勘違いしていたみたいでした。
