AtCoder ABC 109 C - Skip (茶色, 300 点)

一瞬「訪れる順番によって状況が変わらないか...」と不安になるかもな問題だけど、よく考えたら訪れる順番を考える必要もない。ソートしても OK だけどソートする必要はなかった。問題へのリンク問題概要個の点が一直線上に並んでいて、各頂点の座標はで…

2018-09-06

AtCoder ABC 107 C - Candles (ARC 101 C) (緑色, 300 点)

ある量を固定して考える ABC-C AtCoder AtCoder300点緑色diff N個からK個を選ぶ設定の問題最適化テク:最適解の形を考える ARC-C 一直線上のN点の問題最小コスト点が移動していく問題最適化問題

問題概要 N 本のろうそくが一直線上に並んでいる。最初は原点にいて、N 本のうち K 本のろうそくに火をつけたい。ろうそくと同じ座標に到達すると火をつけることができる。火をつけるのに要する時間は 0 秒である。移動距離を最小化せよ。解法 K 個の連続す…

2018-07-27

AtCoder AGC 013 C - Ants on a Circle (橙色, 700 点)

不変量周期性に着目する各kに対して AtCoder AtCoder700点 AGC-C 一直線上のN点の問題橙色diff 点が移動していく問題弾性衝突操作後の結果を求める問題

蟻さんぐるぐるなのん問題へのリンク問題概要 (AGC 013 C) 長さの円周上を匹の蟻が動く。どの蟻も 1 秒間に 1 だけ動く。互いに反対方向に動いている 2 匹の蟻がぶつかったら、互いに向きを反転させて動く。匹の蟻は最初の地点にいた。どの蟻が最初に…

2018-06-04

AtCoder AGC 025 C - Interval Game (黄色, 700 点)

区間最短路問題解空間:O(N!)通りの選択肢最適化テク:解を変形していく(最適性を失わずに) 最適化テク:端点のみを考える Greedy AGC-C AtCoder AtCoder700点一直線上のN点の問題黄色diff 点が移動していく問題各区間から1点ずつとってくる問題ジグザグ N個の区間の問題最長路問題

コンテスト本番における僕のコード: https://beta.atcoder.jp/contests/agc025/submissions/2612210 tourist のコード: https://beta.atcoder.jp/contests/agc025/submissions/2609185 解けたとはいえ、反省点も多い感じですね。。。問題へのリンク問題概…

2018-06-03

2018 codeFlyer 予選 C 徒歩圏内 (400 点)

しゃくとり法数え上げ問題 unrated公式コン AtCoder AtCoder400点 3つのものの真ん中に着目する前処理数列一直線上のN点の問題典型要素を詰め合わせた教育的問題 3つ組(i<j<k)の問題【問題集】累積和・二分探索法・しゃくとり法解空間:O(N^2)通りの選択肢補集合を考えるある量を固定して考える累積和テク:左右両端からの累積和や累積結果を前処理累積和テク:累積和や累積結果を前処理しておく

実装力って大事だなと。 Before: https://beta.atcoder.jp/contests/bitflyer2018-qual/submissions/2601840 After: https://beta.atcoder.jp/contests/bitflyer2018-qual/submissions/2603569 問題へのリンク問題概要長さの単調増加数列が与えられる。…