けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

2018-09-08から1日間の記事一覧

AtCoder ABC 109 D - Make Them Even (400 点)

最初は「一度選んだマスを使えない」を完全に呼び飛ばしてしまった上に、それに気づいた後も「奇数マス同士をマッチングして、うまく経路を設定する」という方向の考察をしまくって、上手くいかずに迷走した... 問題へのリンク 問題概要 (ABC 109 D) 縦 行、…

AtCoder ABC 109 C - Skip (300 点)

一瞬「訪れる順番によって状況が変わらないか...」と不安になるかもな問題だけど、よく考えたら訪れる順番を考える必要もないん。ソートしても OK だけどソートする必要もないのん (ソートして良さそうだったらとりあえずソートすること自体はとてもよさそう…

AtCoder ARC 092 D - Two Sequences (500 点)

桁ごとに考えるしかなさそうなのはそれはそう... 問題へのリンク 問題概要 (ARC 092 D / ABC 090 D) 要素の数列 と が与えられる。 個の整数 の XOR 和を求めよ。 制約 < 解法 XOR 和と言われた時点で、各桁ごとにカウントしたい気持ちにはなる。 個の整数の…

AtCoder ARC 094 D - Worst Case (700 点)

最適性を失わずに解を変形していくことで、都合のいい解の形だけ考えればいいようにする系の問題。 問題へのリンク 問題概要 (ARC 094 D / ABC 093 D) 人の参加者が 2 回のプログラミングコンテストに参加しました。順位がつくのですが、同順位はないものと…

Codechef Product on the segment by modulo

Disjoint Sparse Table の勉強をした!!! 詳しいことは Disjoint Sparse Table と セグ木に関するポエム (のししゃん) Codechef Tutorial - Disjoint Sparse Table あたりを参考に。 問題概要 数列が与えられて、「区間 [L, R) の積を P で割ったあまりを…

AtCoder ARC 101 D - Median of Medians (700 点)

今更前々回の ARC を見て、噂の 700-D Median of Medians を見てみたけど、これはJOI 2017 予選 F - L番目のK番目の数https://t.co/EEfPlJ18Tkとほぼ同じ問題な気がしたん。— けんちょん (@drken1215) 2018年9月6日 とは言え、完全に一緒ではなくて後半の議…