そらのの空の色

プログラミング、アニメの雑記ブログ

【0から始める競プロ活動!】2020/05/07(木) 精進備忘録

600ACにのった!

精進グラフだけが伸びてく

AC

 自分で考えてTLEも出さずに一発ACできた

まじうれしい

atcoder.jp

 

始発より早く着いたら始発まで待ち、発射してたら余りをとって次の定刻まで待つ

atcoder.jp

 

WA

最初O(1)解でやろうと思ったけどWA出した

制約が十分小さいから愚直で通した

O(1)解は全然違った、最小個数とか見るときは最大値を基準に考える

atcoder.jp

 

累積和扱うってわかってたけどバグらした

本番でやりそうなのマジで嫌

atcoder.jp

 

解説AC

 難しかった

最初、数列に含まれる最小因数によって作成可能か決まると思ったが、最大公約数だった

倍数とかが絡んだら最大公約数を視野に入れていきたい

atcoder.jp

 

 

【0から始める競プロ活動!】2020/05/06(水) 精進備忘録

 緑diffを解くのにバチバチアルゴリズム必要だと思ってたけど、実はそんなでもないかも

処理を書き出してちゃんと考察すればある程度は解ける感じがする 

AC

atcoderチュートリアルで見た問題

あの時は全く分からなかったけど一発ACできた 

atcoder.jp

 

最大値を2で割った値に一番近い値をとればいい

最大値が奇数の場合の処理わけもしたが値同じになるかた必要なかったっぽい

処理を分ける考え方できてるので成長

atcoder.jp

 

DFSでワンパンできた

グラフ問題解くとき、少し余裕が出てきた

atcoder.jp

WA

 複雑な(分岐が発生する)処理については分けて処理させたほうがいいかもしれない

atcoder.jp

 

解説AC

 コーナーケースにやられた

アプローチは間違ってないので境界値とかに気を付ける

atcoder.jp

【0から始める競プロ活動!】2020/05/05(火) 精進備忘録

緑diff解けない

茶色との違いはアルゴリズムというよりか考察力な気がする

 

AC

 ちゃんと考察して解けた

想定解ほどではなかったけど十分簡潔なコード書けたとおもう

atcoder.jp

 

島にいる人数が島にいてほしい人数になるまで橋を架ける

すぱっといけてよかった

atcoder.jp

 

隣り合った次の要素の符号を反転できる

0がなく、負の数が奇数のときだけ負の要素は消すことができない

全て正で入力してソートした最も小さい値をマイナスにすればおk

これきれいに溶けてうれしかった

atcoder.jp

 

ちゃんと考察できた

最頻値をとればいいが、要素をちょうど二つにしたいので最頻値とその次点を保持する必要があった

atcoder.jp

 

WA

 あほなので最大値閾値間違えた

考え方と実装は想定解と同じだったのでok

atcoder.jp

 

問題文読み違えて制約ミスってたやつ

考察はちゃんとできていたのでおk

atcoder.jp

 

解説AC

約数の数え上げを高速に実装しないといけない

まず、約数を数え上げるってことをおもいつかなかった

高速化アルゴリズムはためになった

atcoder.jp

 

priority queueを使う問題

処理方法は間違っていなかったけどデータ構造を知らずに愚直でやった

atcoder.jp

 

 

 doubleで二分探索をする問題

収束には十分な回数を回させればいい

atcoder.jp

 

想定解が天才的

二つの状態があるときは無理に一緒に処理するのではなく、個別で処理したほうがいい時もある

(わりとそっちのが典型?)

atcoder.jp

【0から始める競プロ活動!/ABC】#8, #9 AtCoder Beginner Contest 165 166 A~D問題

unratedになったコンテストの詫びコンで二日連続のABCでした
詫びコンのABC165で危うくunratedになりそうだったのはびっくりでしたね

atcoder.jp atcoder.jp

続きを読む