7K12 blog

猫でも分かるアルゴリズム解説

ABC158の感想

f:id:tkr987:20200308130948p:plain

https://atcoder.jp/contests/abc158/submissions?f.User=tkr987


 A - Station and Bus

f:id:tkr987:20200308131245p:plain

https://atcoder.jp/contests/abc158/submissions/10589804

難問。問題文の意味が分からなかったのでサンプルからエスパーした。


 B - Count Balls

f:id:tkr987:20200308131408p:plain

https://atcoder.jp/contests/abc158/submissions/10595105

う 笑


 C - Tax Increase

f:id:tkr987:20200308131525p:plain

https://atcoder.jp/contests/abc158/submissions/10606821

if ((ll)((ld)xa * 0.08) == (ll)a && (ll)((ld)xa * 0.1) == (ll)b) cout << xa;
else if ((ll)((ld)(xa+1) * 0.08) == (ll)a && (ll)((ld)(xa+1) * 0.1) == (ll)b) cout << xa+1;
else if ((ll)((ld)(xa-1) * 0.08) == (ll)a && (ll)((ld)(xa-1) * 0.1) == (ll)b) cout << xa-1;
else if ((ll)((ld)(xb) * 0.08) == (ll)a && (ll)((ld)xb * 0.1) == (ll)b) cout << xb;
else if ((ll)((ld)(xb+1) * 0.08) == (ll)a && (ll)((ld)(xb+1) * 0.1) == (ll)b) cout << xb+1;
else if ((ll)((ld)(xb-1) * 0.08) == (ll)a && (ll)((ld)(xb-1) * 0.1) == (ll)b) cout << xb-1;
else cout << -1;

型変換での丸め誤差がありそうなので、6個全部計算すればどれかが答え(笑)

よくよく考えたら制約を見ると100 / 0.08 = 1250なので全探索するのが正しい(^^;


 D - String Formation

f:id:tkr987:20200308132311p:plain

https://atcoder.jp/contests/abc158/submissions/10622041

素直に実装すると先頭への追加は O(N)なので、dequeを使うことで O(1)にする。

今までdequeを使ったことなかったので良い勉強になった。