読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

ABC#001

NitCoder内で使ったもの。
D問題で一度間違えているので反省。

- A問題「積雪深差」

(http://abc001.contest.atcoder.jp/tasks/abc001_1)

問題概要:
積雪深とは積雪量のことらしいです。1時間の間の積雪量の差を調べる問題。

解法:
入力される二つの整数の差をとるだけ。2000以下なのでintで大丈夫。

ソースコード:
http://abc001.contest.atcoder.jp/submissions/338233
なんのひねりもないソースコードです。入出力の参考にでも。


- B問題「視程の通報」

(http://abc001.contest.atcoder.jp/tasks/abc001_2)

問題概要:
VVという視程の表現方法が存在するのかggってみたら一番上にヴィレッジヴァンガードが出ました。正しい訳はVertical Visibilityで本当に存在するみたいです。

解法:
条件が色々面倒なのだけれど基本的にif文の列挙。入力がメートルなのでキロに変換する必要があるがintで処理する場合は100m単位での操作も必要になるので注意。
基本方針としてv1,v2にそれぞれ出力する値を計算して最後に出力しています。

ソースコード:
http://abc001.contest.atcoder.jp/submissions/338266
問題文に逆らわずに解いたため割と汚いソースになってます。


- C問題「風力観測」

(http://abc001.contest.atcoder.jp/tasks/abc001_3)

問題概要:
風向きと風速の二つを求める問題です。風力に用いられているビューフォート風力階級について調べてみたところ、提唱したのはイギリス海軍らしいです。日本の気象庁もこの表を使っているみたいです。

解法:
1,風向きの求め方
角度が10倍された整数で入力に与えられます。16方位は360/16=22.5度ごとに均等に変化することを利用して解きます。NNEの角度が0から始まるように入力の値をずらし、225で割ることであらかじめ用意しておいた文字列配列へのアクセスができます。
2,風力の求め方
B問題と似たような解法でif文の列挙です。注意点として「風力が0のときは風向きを'C'と表示しなければならない」という文を読み飛ばさないこと。「小数点第二位を四捨五入して0.2以下」は「0.25未満」と置き換えればOKです。

ソースコード:
http://abc001.contest.atcoder.jp/submissions/338296
if文で比較するときにdouble型の変数を使っていますがこれをfloatにするとWA食らうみたいです。一番正確なのは風速の基準値に60をかけて整数にすることっていうのを解いた後に気づきました。浮動小数点はどうしても誤差が出ちゃいますからね。


- D問題「感雨時刻の管理」

(http://abc001.contest.atcoder.jp/tasks/abc001_4)

問題概要:
数値の丸め、区間の連結をする問題です。ほかの問題よりは競技プログラミングらしい問題といっていいと思います。入力が文字列であることにも注目。

解法:
1,入力で与えられる区間を始点と終点バラバラにして配列に格納(数値丸め済み、始点、終点かは分かるように各値にフラグをつける)
2,配列をソート,O(nlogn)
3,交わりのない区間に分割
区間の始点をs,終点をtとするとソートされた配列はssstttstsststtみたいな形になる。
このとき、一つの区間はsから始まりtで終わる。さらに区間内のsとtは同じ個数になる。
すなわち上の例は[sssttt][st][sststt]というように交わりのない区間に分割できる。
4,区間の連結
最後のtと次の区間の最初のsが一緒の値の時は二つの区間を合体させる。
交わりのない区間に修正してから連結処理を行うのがポイント。
配列を逐次操作すればよいのでO(n)

ソースコード:
http://abc001.contest.atcoder.jp/submissions/338595
最初解いたとき区間内のsとtは同じ数という条件をつけずにオートマトンで処理していたため事故りました。変数名hはスタック動作を意識。文字列から数値への変換はatoi、区間の終点側の数値の丸めは4を足してから100で割って100かけなおせばOK。60になったときに補正をかけるのを忘れないように。
注意点として、同じ値の始点、終点が存在した場合は始点があとにくるようにソートしないと事故が起こります。