ABC129
ABC129に参加しました。Ratedのコンテストは2か月ぶりでした。
言語はJava8です。
A問題
a+b, b+c, c+aの中から最小値を出力する問題。
他の人の解答も見てみましたが、Javaの場合、意外にも3つの数字の中から最小のものを出力する気軽な方法はないく、Math.minを2回実行するやり方が多かったです。
https://atcoder.jp/contests/abc129/submissions/5837288
4分でAC。
B問題
問題のいう、S1とS2の差の絶対値は、「合計ーS1*2」の絶対値で求められるのでそれで解きました。
https://atcoder.jp/contests/abc129/submissions/5841491
8分でAC。
なんか冗長だなと書きながら思っていた以下のコードは、やはり改良の余地がありました。
if (Math.abs(sum - calc - calc) < minDifference){
minDifference = Math.abs(sum - calc - calc);
}
改良後は以下
minDifference = Math.min(minDifference, Math.abs(sum - calc - calc));
C問題
パッと思いついた基本的な方針は以下の通りです。
- ある段のわたり方は、「1つ前の段のわたり方」＋「2つ前の段のわたり方」で表される。
- 穴が開いていた場合、その段のわたり方は0通り。
最初の1.2段だけ気を付ければいいかな、と思いましたが、一点気を付けないところがありました。*1
ArrayList.contains()は遅い
それは、上記の通り、ArrayList.contains()は時間がかかるということです。
以下はTLEになった提出です。ある段が穴が開いているかの判別をしているところで、contains()を使っています。
https://atcoder.jp/contests/abc129/submissions/5846757
対応法は2つあります。
- HashSetを使う
https://atcoder.jp/contests/abc129/submissions/5864593
- 検索不要にする
例えば、自分の場合は穴の段数を下から順に取り出して*2、その段数の処理が終わったら次の穴の段数を取り出す、というようにやっていました。
他の人の解答例を見ると、すべての段について、穴が開いているか否かの配列をあらかじめ用意しているものもありました。
https://atcoder.jp/contests/abc129/submissions/5849100
37分でACしましたが、4回誤答しました。
D問題
本番中は解法が思いつきませんでしたが、解説を読むとそこまでひねったやり方ではないなと思いました。
for文を2000 * 2000 回しても結構速いんですね。
https://atcoder.jp/contests/abc129/submissions/5863198
結果
パフォーマンス：899
レーティング：588 → 636 (+48)
またがんばります。
