ferinの競プロ帳

競プロについてのメモ

ABC047を解いてみた

abc047.contest.atcoder.jp

A問題

 それぞれの数が他の2つの和と等しいかどうか確認してどれか1つでも真であれば"Yes"を出力します。特につまずくこともなく成功でした。

B問題

 白と黒のどちらで塗りつぶされているかを0と1として管理する変数を用意し、n回ループして法則にしたがって書き換えていきます。n, w, h等の制約から考えて計算量は最大でも100*100*100=10^6程度で問題無いと思い実装! ですが、配列が[x][y]なのか[y][x]なのか等で時間がかかってしまったので反省… 2次元のlistの扱いにはある程度慣れることができたので次からはこんな時間はかからない(はず)です。

C問題

 入出力例を見ていてBとWが切り替わるタイミングを数えればいいのでは?と気付き実装しました。これは10分くらいで解けました!

D問題

 A, B, Cを解き終わるのに85分かかってしまい解いてる途中で100分経ってしまいました… 最大の利益を出せる場所が何箇所あるのかを求めればいいということはわかったのですが、すべての組み合わせを総当りで考えると計算量がn^2で実行時間が確実に足りません。
 解説を読んでアルゴリズムを理解するのに30分、実装に30分かかったあげくWAを2回出してしまいもっと頑張らなければという感じです…

全体の雑感

 今回はC問題のほうがB問題よりも早く解けたので全ての問題文を先に見てから解く問題を決めたほうがいいかなと感じました。