とても久しぶりにABCに参加しました。1年ぶりです。そのため、ひっっどいミスをしました。それも書いていきます。本当にひどいミスだった。
私の頭で理解できそうなのはD問題までなので、解いて解説を読んだあとの感想戦を書いていきます。
目次
A問題
楽勝。if文書ければ誰でも書ける。A問題で一番めんどくさかったのは、文字列の最後の文字を削って新しい文字を加える問題。
B問題
問題の理解に戸惑った。というより、入力の仕方が最初よくわからなかった。結局、入力例を見て理解しました。
1行目が人数とお菓子の種類。2行目以降は2行ずつ読むとわかりやすくて、2行目にあるお菓子を持っている人数、3行目に持っている人。この2行で1セット。以下まで同じ。最後にお菓子を持っていない、つまり入力例奇数行目(1行目を除く)で出てこなかった番号の数を出力させればOKです。
解説はresize()とか使ってますが、そこまでしなくても書けはします。
やることは、出てこなかった人を探せばいいので、最悪bool型の配列を人数分用意して、出てきた数字-1番目の要素をtrueにして、最後に配列内のfalseになっている要素数を出力するだけでACします。
C問題
ある高さの展望台があり、道がつながっている。ある展望台から道でつながっている全ての展望台より、その展望台が高ければ”よい展望台”とする。この数を出力せよ、という問題です。
ぱっと見てグラフの問題だと思いました。私は今までグラフの問題をろくに解いて来なかったので、今回はちゃんとやろうと思ってググりながらやりました。
その結果、この問題は隣接リストを使えば実装できそうだとわかりました。
次に問題となったのは、道でつながっていない展望台。これは孤高の存在なので”よい展望台”扱いです。
隣接リストには入っていないので、扱いに困ります。私はB問題と同じく、出てこなかった番号をbool型の配列で管理して最後に足し合わせてました。しかし、終わったあとに他の人の解答を見ているとそんなことをしなくてもいいことを知りました。
最初は次のように実装していました。
for(int i = 0; i < n; i++){
bool good = false;
for(int j = 0; j < graph[i].size(); j++){
int c = graph[i][j];
if(h[i] > h[c]){
good = true;
}else{
good = false;
break;
}
}
if(good) ans++;
}
しかし、2行目の初期値をtrueにすれば、処理されなかった、つまり隣接リストにない番号の場合はそのまま下へ通って答えに1が加算されます。私の参考にしたコードは、道の情報が昇順で与えられること前提で書かれていたので、一応そうでなくても対応できるように、なにかの比較でfalseになったらループを抜けて、答えに加算されないようにしています。
最終的な自分の解法
最終的に次のようなコードになりました。
解説の解法
解説では、「隣接リストでも書けますが、隣接リストを使わなくても書ける」とあります。
コード自体は解説を見てもらえば良いのですが、シンプルに解決しててなるほどなって思いました。
まず、maという名前の配列を作ります。それを0で初期化します。そして、道の情報を入力する時に、ma内の値と道でつながっている先の展望台に高さを比較し、大きい方をmaに代入します。逆も同様のことを行います。
これによって、道でつながっている先の展望台の高さの最大値の情報を、ma内に保持することになります。
最後に、自身の高さと比較して、自分のほうが高くなればカウントを一つ増やします。
これの良いところは、道のつながっていない展望台を特別な実装をせずに処理できることです。maの値は0のままなので、自分の高さと比較すれば、当然自分のほうが高くなるので、勝手にカウントが1増えます。
やらかした点
結局私はC問題をACすることはできませんでした。REでした。
実行時エラーなので、コンパイル時のオプションなどで調べたりしましたが何も検出せず。それもそのはず、最初に取った配列の大きさの桁を一つ少なくしていたのですから。
最大値がなので、その値よりも大きい配列を確保すべきですが、私は"10010"と書いていました。これでは約です。そりゃ、結果でNの値が大きいテストケースは全部REでますわ。
0一個ミスったせいでC問題を落とすという馬鹿なことをやりました。今度からpow()使っておこうか・・・？
D問題
解説に書いてるのは、となる場合に、となるが制約条件を超えるときのとを求めています。
最終的には愚直に求めるようですが、制約条件を超える直前の値を算出することで探索範囲を絞るというのは初めて見たので目から鱗が落ちました。
私は次のように実装しました。
愚直に求めるだけです。最悪約57600回の計算なので、今のCPUならチョロです。
まとめ
1年ぶりぐらいのABCでした。M1になってB4の頃にサボりまくったツケが回ってきてます。本当にやばい。
研究テーマ的にもアルゴリズムがすごく重要なので、ちゃんと勉強しようと思いました。
参考文献