本記事は、eeic （東京大学工学部電気電子・電子情報工学科） Advent Calendar 2022 の 1 日目の記事として書かれたものです。 毎年恒例の eeic Advent Calender ですが、私が確かめた時点でまだ今年のが立っていなかったので、立ててみました。12/01 現在、…
昨年に引き続き、ぴーよ (holeguma) さん、まさよし (masayoshi64) さんと組んでチームPWMtreeで出ました。4完25位でした。 本番 開始1分くらい問題が見られませんでした。1年前を思い出すいい余興でしたね。Cの担当だったので見ます。構文解析だったのでと…
はじめに 反省点の一つでもありますが、コンテスト中に記録をつけることを怠ったため、以下の内容は僕の記憶に基づいており、不正確な記述を含む可能性があります。 参加にあたって AHC は個人的にかなり楽しみに待っていました。その記念すべき第一回という…
ぴーよ (holeguma) さん、まさよし (masayoshi64) さんと組んでチームPWMtreeで出ました。5完20位でした。 回想 僕は高専から大学に編入しました。高専ではICPCには出ていません。理由としては国内予選に通る自信がなかったこと、参加する文化がなかったこと…
人力部門に出ました。 4月 問題が発表される。今年も人力臭がすごい。とりあえず暗号化については深く考える必要がないことがわかった。 すぐに市松模様作戦を思いつくが、のちに却下。 5月 学内審査と予選を適当にかわす。 6月 ビジュアライザを作る。メン…
問題 https://beta.atcoder.jp/contests/agc026/tasks/agc026_d 解法 高さが同じ列のヒストグラムを考えます。 左の列の塗り方が決まっているとき、その塗り方が赤青赤青……のように交互（以下マダラと呼びます）であれば、右の列の塗り方はそれと全く同じに…
全然わからん→解説見よ→意味不明→制約見落としてた→えーん 問題 https://beta.atcoder.jp/contests/arc103/tasks/arc103_d 解法 辺で繋がれたある頂点を考えます。辺を切ったときのそれぞれの連結成分のサイズをとすると、が成り立ちます。ここで、頂点を固…
問題 https://beta.atcoder.jp/contests/arc103/tasks/arc103_c 解法 木が構築可能であるための、次の必要条件が浮かびます。 実はこれらは十分条件でもあります。具体的には、次のようにして構成できます。 頂点間を繋ぐ。 直前に頂点間を繋いでいたとする…
これを通せたおかげで予選通過できました。嬉しい。 問題 https://beta.atcoder.jp/contests/code-festival-2018-quala/tasks/code_festival_2018_quala_d 解法 とします。DPをします。ガソリンスタンドまで来るにあたって、ガソリンスタンドで最後に補給す…
問題 https://beta.atcoder.jp/contests/code-festival-2018-quala/tasks/code_festival_2018_quala_c 解法 になったら、それ以降はで割らないものとします。そうすると、求める答えは本来の「回の操作後の数列としてありうるものの個数」に「回未満の操作後…
問題 https://beta.atcoder.jp/contests/arc100/tasks/arc100_d 解法 「全ての列についてのに一致する連続する部分列の個数の総和」から「カラフルでない列についてのに一致する連続する部分列の個数の総和」を引く方針で考えます。前者は簡単なので省略しま…
自力AC最高点を更新しました！ 問題 https://beta.atcoder.jp/contests/arc102/tasks/arc102_d 解法 まず、操作の性質を考えてみると、以下のようなものが浮かび上がります。 一度反転した3項の中央は、その後動かすことはできない 一度動かした項を元の位置…
これは流石に解きたかった 問題 https://beta.atcoder.jp/contests/arc102/tasks/arc102_b 解法 頂点から頂点に長さの辺と長さの辺を張る とすると、経路長からのパスが1本ずつできます。 まずはこれでパスの最大長さをを超えない最大まで持って行きましょう…
考察してて生えてきた図に既視感があると思ったら、以前諦めて解説だけ見た問題だった 問題 https://beta.atcoder.jp/contests/arc070/tasks/arc070_c 解法 というDPについて考えます。以下が成り立ちます。ここまでで部分点が取れます。 実はは、傾きが段階…
過去問。 なんかやけにあっさり解けて、順位表見たら通してる人が意外と少なく、ついに僕も覚醒したか？ と思ったらXor Sum回だった 問題 https://beta.atcoder.jp/contests/arc066/tasks/arc066_c 解法 正符号の後ろから括弧を開始するのは明らかに無意味で…
解けませんでした。そろそろ本番で700点問題を通せるようになりたい。 問題 https://beta.atcoder.jp/contests/arc101/tasks/arc101_b 解法 答えを二分探索します。「の中央値が以上かどうか」が判定できれば、それを満たす最大のが答えとなります。 「の中…
