AtCoder Beginner Contest 129
今回は数学問が出たので温まってやっと青色になれました!!!
ですが凡ミスで黄パフォ出し損ねたのでそれはそれ
A - Airplane (100点)
問題: A - Airplane
環状線の3点を巡回するルートではどれか1つの道を通らないので、を出力してAC。。
maxとmin間違えて1WA出してしまいました
拙解 (C++14): Submission #5834846 - AtCoder Beginner Contest 129
B - Balance (200点)
問題: B - Balance
素朴に全探索する。累積和を取ればだが、なのでいちいちすべてのについて2グループの和をとってでも十分間に合ってAC。
拙解 (C++14): Submission #5837108 - AtCoder Beginner Contest 129
C - Typical Stairs (300点)
問題: C - Typical Stairs
ド典型のDP問題。
とする。まず0段目には「何もしない」の1通りでたどり着くため、dp[0]だけ1であとは全部0で初期化する。段目にたどり着く方法は段目とからの2通りあるので、
ををとりつつ素直に実装してAC。
拙解 (C++14): Submission #5839535 - AtCoder Beginner Contest 129
D - Lamp (400点)
問題: D - Lamp
行/列ごとに見たときに '.' がいくつ連続しているかを、行でのそれを、列でのそれをとして*1で前計算する。そうするとマスにランプを置いたとき照らされるマスは個となるので、これをすべてのマスについてチェックして最大値をとってAC。。
拙解 (C++14): Submission #5844368 - AtCoder Beginner Contest 129
E - Sum Equals Xor (500点)
問題: E - Sum Equals Xor
全加算器を考えると、繰り上がりが生じたときには次の桁がNXORになってしまいが成立しなくなるので、考えるべきは各桁がのものだけになる。ここで、を超えてはならないので、たとえばのとき、
101100101 101100100 1011000** 1010***** 100****** 0******** (ただし'*'は0あるいは1のどちらでもよい)
のように1のある桁を0にして、その後ろが任意、という風にすればよい。が2進数桁として、上桁をに一致させるのが何通りであるかをとってとし、あとは'1'の桁について、上のように任意の桁がd桁あるときをmodを気にしつつ足していけばAC。。
などの巨大な数でも文字列として扱うことができればになって間に合う。この前予選落ちしたGCJでもあった。
拙解 (C++14): Submission #5848363 - AtCoder Beginner Contest 129
F - Takahashi's Basics in Education and Learning (600点)
問題: F - Takahashi's Basics in Education and Learning
二分探索してを満たす最大のを求めていけば、桁の項の個数を求めることができる。
(以下、Editorial見ました)
ここで、(作る整数, 足していく項の値, 1)というベクトルを考えると、足していく項の桁数をとして、
とする写像を構築すればよく、これは線形写像
なので、行列累積が使えてに持ち込むことができる。すべてのについて10進桁の項個に対して上記の線形写像を行列累乗で(mod Mを気にしつつ)適用し、第1成分を出力してAC。項数パートと行列累乗パートともにで、全体としても。
拙解 (C++14, コンテスト後): Submission #5862559 - AtCoder Beginner Contest 129
まとめ
F問題はなんていう中途半端に巨大な制約だったら行列累乗で行くべきでした、項数パートまで解けてただけに残念です
それ以前にA問題の凡々ミスで黄パフォ取り損ねたのはとてもくやしい
でも青くなれたのでよし(よくないが)
やっと青色になりました!!!!
— Ganmodokix (@AprilGanmo) June 9, 2019
ganmodokixさんのAtCoder Beginner Contest 129での成績:218位
パフォーマンス:1953相当
レーティング:1556→1605 (+49) :)
Highestを更新し、2 級になりました!#AtCoder https://t.co/ty9qOOX54J pic.twitter.com/vo1BVfg9Oc
*1:うまく実装すると同じマスを丁度2回走査するのでにはならずに済む