ABC187の感想
AtCoder Beginner Contest187に参加しました。問題はこちらから。
結果はこんな感じでした。
abcdeの5完(0wa)
順位：945/7239
パフォーマンス：1496
なんか思った以上に良い結果で驚いています。
今回初めてE問題を解くことができました。純粋に嬉しいです。なぜ解くことができたかは明白です。過去問で似たような問題を見たからです。過去問って大切ですね。大学の授業では過去問の入手に一苦労してましたが、非常に簡単に手にいれることができる、AtCoder様には頭が上がりません。
あとは、レーティングが緑になるまでに難易度緑以上の問題をコンテスト中に解くことを目標としていましたので、それが達成できて一安心です（たぶんeはdiff800以上はあるはず、、）。
では感想を書いていきます。
A問題
いつものa問題よりは難しく若干悩みました。入力をどっちもstringでとって、各文字ごと「-'0'」で数値に直して計算しました。おそらくだいぶシンプルな方法を選べたと思っていますが、どうなんでしょうか。
でも、入力、文字列、int変換、総和、maxと手順は多いですね。どうなんでしょうか。
B問題
傾きを比べます。制約が小さいので愚直にやれば答えが求まります。
ただし、傾きを求めるときって割り算をしないといけないので、doubleの誤差におびえてました。そのため、式をちょっと変形して
abs(y1-y2) <= abs(x1-x2)
としました。このとき、符号やら絶対値に結構悩みました。
こういう場合に大切なのは数のイメージですね。傾きの絶対値が1以下なのですから、グラフの傾きは急ではなく緩やかになります。それって、坂の傾斜が緩くて、自転車でなんなく登れる、もしくは緩やかに下れるということです。そのため、xの差が大きくて、yの差が小さくなりそうじゃないですか。そういうことですね。
C問題
文字列の問題です。
setとかで重複を消して、みたいなことをはじめは考えてました。ただ、!が先頭にあると「ソートしてもなー」などと思った時に、じゃあ文字列をリバースしようとなりました。それがとっても効果的でして、リバースしたものをソートしたら、いい感じになりました。重複はありますが、できるかどうかの判定でしたので、
s[i] + '!' == s[i+1]
こんな感じの判定式に一つでも引っかかればOKです。出力の際には勝手にリバースしたものを元に戻すことを忘れないようにしましょう。
D問題
選挙の問題です。演説を行うと票を得ることができます。現実でもこのくらい簡単に票が獲得できると楽ですね。
ぱっと思いついたのは
高橋君の票をたくさん得ることができる街に演説に行く。
青木君の票をたくさん削れる街に行く。
でした、どちらに重きを置けばいいのかなと考えてました。でも、結局「いっぱい票を得て、いっぱい票を削れる街が最強だ。」という結論になりまして、
2*a[i]+b[i]
の大きい順に演説を行うことにしました。どうやらこれで正しかったみたいです。
E問題
木の問題です。これに関しては完全に過去問で見たことがあったのでそれに準じて考えていきました。
過去問はこちらです。
クエリごとに全ノードに加算していくと間に合わないのは明白なので、最後に上の方から加算していこう、っていうのは過去問と同じでした。
違いが2点ほど、
根が固定されていない
親と子に関する２種のクエリがある
1つ目に関しては自分で決めてしまいました。番号1が根です。1を根と決めましたので前処理として幅優先探索で、各ノードの深さを調べておきました。
2つ目は1つ目を使って解決しました。最後に加算するという目的があるので、親子関係を明白にしておく必要がありました。クエリ1とか2とかは無視しまして、、、
子に加算：そのノードに+xする
親に加算：そのノードの子に-xをして、最後に全部に+xする。
こんな感じですかね。親子関係は幅優先で求めた深さが小さいほうが親となります。
あとは、上の方から累積和を取る感じで足し合わせていきましょう。全部終わったら、全部に+xってやつを全部にしましょう。おわりです。
F問題
ちょっとだけ問題文を眺めました。
この記事が気に入ったらサポートをしてみませんか？