ICPC 参加記書きました

ICPC OB/OG の会 (JAG) 様主催の夏合宿に参加してきた．非常に刺激的で楽しかったので，参加記を書く． 8/16 (Day 1) Day 1 - Before Contest 院試が終了して自堕落な夏休みを送っているせいで生活リズムが破壊されており，前日の睡眠に無事失敗した．集合時…

1 年のときは比較的簡単な問題が 3 人揃って解けなかったせいで敗退した．2 年のときは 1 ペナ と 順位 1 つの差に泣いた．3 年のときは 序盤のスピードと zkou の天才的な閃きのおかげでギリギリ通過した． 国内予選は 1 年を通して自分の感情の起伏が最も…

列 についての最小値を根とする Cartesian tree についての性質 について，頂点 と の一方がもう一方の先祖である 特に， と は必ず先祖と子孫の関係にある クイックソートの期待計算量の解析にもこの性質が利用できる

未証明だけど多分正しい主張 2 つの文字列 をこの順で連結したものを で表す．文字列 について， とおく． がともに回文となるための必要十分条件は以下の通りである: を の先頭 文字を抜き出して得られる文字列とする． を文字列 の反転とする．このとき は…

有向グラフであって，全ての辺の向き付けを取り除いて無向グラフとみなすと完全グラフになるものをトーナメントグラフという．以下では をトーナメントグラフとして，その性質について述べる．証明についてはどれも冷静に考えたら簡単なので省略する． 性質1…