AtCoder Regular Contest 101
AtCoder Regular Contest 101に参加しました!
AtCoder Beginner Contest 107 beta版
AtCoder Regular Contest 101 旧版
AtCoder Regular Contest 101 beta版
解けた問題だけ解説をしていきますー
要項
AtCoder Beginner Contest 107 / Regular Contest 101
rated 1200 / 2800
8/25(土) 21:00 ~ 22:40 (100分)
100-200-300-700-900-900 (6問)
ペナルティ: 5分
方針
まずは落ち着いて速く2完、あとは残った時間でE問題に挑みたいところ。
もしDが不可能そうでもBeginnerに出ている問題なことを考えると典型問題なので、全列挙でもない限りはちゃんと解き切る!
EFに関しては多分難易度通り
というかDは数え上げ&逆元の可能性もあるな、あれ難易度の割に点数が跳ね上がるし
A - Train
前から両目の電車の後ろには後両あることから、答えはです。
B - Grid Compression
まず、例を見ながら考えてみましょう。
4 4
##.#
....
##.#
.#.#
この時、まずは行について考えていくと、行目が削除される条件は任意のに対しが.であることです。
そうでない行は、今回の例の場合は1,3,4となります。
同様に列について削除されない列は1,3,4となります。
ということは、, についてを表示していけば答えの形になりますね。
という風に、行と列について独立に削除しない場所を求めた後、その順に表示していけば答えが表示できます。
このやり方の場合はとなります。
今回はもっと雑に、各マスについて上下左右と自身が全て.なら表示せず、そうでないなら表示するというコードを書いてもなので通りますね。
C - Candles
まず、異動に関して無駄な移動をしないことを考えると、次の移動しかありません。
- 原点以上左側のろうそくを個消してから、原点より右側のろうそくを個消す
- 原点以上右側のろうそくを個消してから、原点より左側のろうそくを個消す
これは、あるろうそくについてそこで引き返すと考えると見通しが良くなります。
先に、まず原点の位置がどのろうそくの間、あるいはどのろうそくと同じ位置になるか求めておきましょう。
次に、を決め打ちます。
この時、そこまでに消せたろうそくの本数と時間はで求めることができ、ということは後何本消すかが分かるので、残りの移動時間もで求めることができます。
ということは、つまり任意のについて時間を導出し、そのうちの最小を出力すればで答えを導出できます。
D - Median of Medians
ごめんなさい、解けなかったです
結果
ox-- 1完(300点) 39:43(4WA) / 59:43
710位 パフォーマンス: 1000
レート: 1752→ 1695(-58)
感想
爆死です!