いろいろな記録

大学院生やってます

2020/08/15

diary

映画を見た。

競プロ

C - 最高のトッピングにしような

解説AC 45分

いい問題だった。DPの状態量が減らせずに答えを見たが、結局スペシャルチケットを1枚ずつ使うことで最大X個分のトッピングがもらえるので、チケットの種類は無視した上で、今までにとったトッピングの値がXを超えないように考えれば良いという話。

こういう系の状態量を落とせない系のDPは、部分的に貪欲っぽい発想をすれば良いことが多いので記憶しておく。

 

2020/08/14

diary

競プロ

C - 増築王高橋君

黄diffとあるがただ決め打ち二分探索するだけ。解法はすぐわかったものの、オーバーフローとコーナーケースの沼にはまってしまって大変だった。

とにかくノートに細かいケースを書くこと。

long longのオーバーフローは、何かしらの判定の掛け算をするときに出ることが多いというのも記憶しておくこと。

2020/07/17

diary

競プロ

C - 積み木

解説AC : 20分

ネタバレを見てしまった。ちゃんと考えればよかった。

最近作ったBITが活きる問題。一点加算と区間和計算ができると、配列のある成分の左右の成分の和などを O(\log N)で計算できること自体を覚えておいて良さそう。

D - トレジャーハント

解説AC : 30分

何か色々考えていたが、結局ある一点でチャージした方がお得ということに気づけなかった。その上で次のステップとして、矢印を逆向きにしたダイクストラを使うというのは面白い発想だなと思った。（願わくば2ステップ目を考察したかった）

F - Interval Running

自力AC : 15分

diff高めに出すぎ？ダイヤグラム書いたらできる。 T_1+T_2の間で、2回クロスするのか1回だけ交わるのかのチェックがミソ。

T_1時点とt_1+T_2時点での両者の差分が片方プラス片方マイナスになることが条件となるが、ここの判定に差分の積が負になるという条件を利用したら、積が1e19を越えてオーバーフローしてしまった。long longでも上限には注意。

E - Smart Infants

解説AC : 30分

multisetを理解したのでほとんど自力でかけたが、一箇所ステップがバグっていた。分岐が多いところはフローチャートをメモして、個数など変化すべきでないところが変化していないかなどをチェックすること。

2020/07/11

diary

外食がうまかった。家事がはかどった。

競プロ

エイシングは3完で厳しい感じでした。参加記最近サボりがちだから明日書く。

C - ロミオとジュリエット

自力AC : 20分

木の直径を探すとき、適当なノードを根として一番深いものが直径の端点となる法則。それで見つけた候補を根としてもう一回探索して最深部を探せばokです。

 

---

明日も頑張りましょう。

2020/07/02

diary

色々捗った。

研究

  • 5h

競プロ

F - XOR Matching

解説AC : 30分

あさかつで解けず。20分くらい適当に実験して何もわからなかったので解説を見たが、言われてみれば簡単だった。

こういう構築系の問題は、とにかく手を動かして可能なパターンがあるかどうかを生成するしかない。 1から2^{M-1}のXORが0になるということもちゃんと記憶しておく。

D - Static Sushi

自力AC : 45分

どちらかの方向にだけ進むか、行って戻って反対側へ行くか。パターン分けをして、前計算で配列を計算しておくと、折り返す地点を決めれば得られるカロリーの最大値がO(1)で求まる。

自力ACできて嬉しい。

F - Playing Tag on Tree

解説AC : 40分

結局移動コストに落とし込むところを解説読んで知ってしまった。考えれば出そうだっただけに勿体無い。

B - AtCoderでじゃんけんを

自力AC : 25分

最初、 O(N^2)解法を O(N\sqrt{N})と勘違いしていてTLEを出した。いまだにこんなミスする？

 

最近、明らかな考察不足や軽率な解説ACが目立つので、ほぼ解説見ずに毎日水青4ACを目指したいです。

 

---

明日も頑張りましょう。

2020/06/26

diary

競プロ

B - こだわりの名前

自力AC : 40分

一箇所いじる系は、いじるところ以外の前情報を持っておけば楽という定石。

何気に時間がかかった。

D - Axis-Parallel Rectangle

自力AC : 40分

緑〜水下位あるあるのよく見たら全探索いけるやつ。上下で抑え込むという判断、k=2, 3のときの例外処理に手間取って時間がかかってしまった。

D - Iroha and a Grid

自力AC : 20分

x\leqq bの部分を切り取って数えあげるだけ。 

 

2020/06/25

diary

競プロ

E - Second Sum

解説AC : 30分

おもろい。数字の位置をメモしておいて、降順に入れながらその数字が二番目となる領域を足していく。

各L,\,Rに対してX_{L,R}を求めているとN^2回見ることになって間に合わないので、Pの各要素が何回全体に寄与するかを考えれば良い、という発想は典型っぽい。

実装はsetとその中でのにぶたんを使うと楽ですね。prevとnextというイテレータいじるやつ初めて知った。setもそれなりに慣れてきた。

B - Minimum Sum

自力AC : 20分

上の問題の下位互換。