こんにちは、鬱太郎です。数あるプログラミングコンテストの中の一つAtCoder。今日はAtCoderの過去問のABC（初心者向け問題）を解いてみたのでそれを記事にしたいと思います。プログラミングに興味のない方はごめんなさいm( _ _ )m
はじめに
私はプログラムやプログラミングコンテストに対して何ら知識はありません。私が書くコードは、性能的にも優れているものではありません。私自身が考え、学んでいく過程でできたコードです。無駄がありますが、お許しください。また、改善等の指導があればコメント欄に記入していただけると助かります。
公式URL
abc001.contest.atcoder.jp
使用したもの等
ほとんどの人がc++でjava使っている人あんまりいないのが悲しい( ;∀;)
プラグインのおかげでスムーズにプログラムができました。お勧めです。
A - 積雪深差
見出しをクリックすると開きます。↓↓
問題
問題文
ある時刻の積雪深 H1 と その 1 時間前の積雪深 H2 が与えられます。この時、この 1 時間の積雪深差 H1 − H2 の値を計算して出力してください。
A問題では、提出した結果、全てのテストに対する判定がWAまたはREになってしまった場合のみ、質問タブにて可能な限りのトラブルシューティングを受け付けます。
提出結果のURLを添えて、お気軽にご質問ください。
また、ページ下部、「よくある質問」も、併せてご活用ください。
入力
入力は以下の形式で標準入力から与えられる。
H1
H2
- 1 行目には、整数で、ある時刻の積雪深 H1 (0≦H1≦2,000) が与えられる。
- 2 行目には、整数で、1 時間前の積雪深 H2 (0≦H2≦2,000) が与えられる。
出力
積雪深差 H1 − H2 の値を 1 行で出力せよ。
また、出力の末尾には改行を入れること。
ここをクリックで閉じます
回答
簡単な問題ですね！H1-H2を求めるだけです。自分の開発環境や自分が使うプログラミング言語の入出力の手法を確認しましょう。
ポイント1 BufferedReaderを使って入出力をする
私は、ABC（ビギナー）をやる前にARCに挑戦してしまいました。そこでScannerクラスの読み込みが遅いことを知ったため、基本的にBufferedReaderを使うようにしています。
AtCorderの問題も1行にたくさんの要素が入力されず、複数行にわたって入力されるため、br.readLine()との相性もいいと思います。
ポイント2 Integer.ParseIntで文字列からintに変換
BufferedReader::br.readLine()はString型で返されるため、Integer.parseInt()にて整数値にする必要があります。
成績
提出したプログラムの実行時間・メモリ使用量をまとめました
| 実行時間 |
メモリ使用量 |
| 72 ms |
21460 KB |
ここをクリックで閉じます
B - 視程の通報
見出しをクリックすると開きます。↓↓
問題
問題文
気象情報は、世界中に様々な形で流れています。そのひとつの地上実況気象通報式 (SYNOP) では、視程 (肉眼で物体がはっきりと確認できる最大の距離) を、次の規則に従って、VVという値 (通報式) に変換して報じます。
- 0.1km 未満： VVの値は 00 とする。
- 0.1km 以上 5km 以下：距離 (km) を 10 倍した値とする。1 桁の場合は上位に 0 を付す。
- 例えば、2,000m =2.0km ならば、VVは 20 である。同じく、200mの場合VVは 02 である。
- 6km 以上 30km 以下：距離 (km) に 50 を足した値とする。
- 例えば、15,000m =15km ならば、VVは 65 である。
- 35km 以上 70km 以下：距離 (km) から 30 を引いて 5 で割った後、80 を足した値とする。
- 例えば、40,000m =40km ならば、VVは 82 である。
- 70km より大きい：VVの値は 89 とする。
いま、あなたに視程の距離をメートルで与えるので、上記のルールに従って計算されるVVを出力するプログラムを作成してください。
なお、VVは必ず（上位の 0 を含めて）2桁の整数であり、上記のルールに従って計算した時に整数にならないような入力や、上記の範囲に入らない入力 (例：5km より大きく 6km 未満) などはありません。
入力
入力は以下の形式で標準入力から与えられる。
m
- 1 行目には、距離を表す整数 m (0≦m≦100,000) が与えられる。単位はメートル (m) である。
出力
VVの値を 1 行で出力せよ。
また、出力の末尾には改行を入れること。
出力例 1
- 65
- 入力は15,000m =15km であり、6km 以上 30km 以下なので、「km での値に 50 を足してVVとする。」というルールに従う。
- そのため、15+50=65が正解である。
出力例 2
- 89
- 70km より大きい場合は、VVは 89 である。
ここをクリックで閉じます
回答
これも簡単な問題です。以上以下より大きい未満という条件に気を付けながらif文を駆使してプログラミングしましょう。
ポイント1 メソッドを使うことでif-else文をなくす
getVV(int m)といメソッドを作ることで、if-else文をなくして無駄なコードを減らしました。
ポイント2 問題文をよく読み、無駄な条件式をなくす
問題文をよく読むと次のような記述があります。
なお、VVは必ず（上位の 0 を含めて）2桁の整数であり、上記のルールに従って計算した時に整数にならないような入力や、上記の範囲に入らない入力 (例：5km より大きく 6km 未満) などはありません。
これを考慮すると、if(m<=5000)の次にif(6000<=m&&m<=30000)などとしなくてよくif(m<=30000)と書け、無駄が省けます。
ポイント3 比較する単位を合わせて整数同士の比較をする
今回は与えられた数値が整数のメートル(m)ですね。問題文の比較の条件ではkmの単位が使われていますが、コードを書くときは単位をmに直します。つまり、1000倍して単位を合わせます。そうすることで、整数同士を比較させることができます。
ポイント4 String.formatを使い2桁の数値で出力する
問題文の出力のところに次のような記述があります。
なお、VVは必ず（上位の 0 を含めて）2桁の整数であり...中略...VVの値を 1 行で出力せよ。
また、出力の末尾には改行を入れること。
Java言語ではString.formatを使うことで、C言語のような%02dといった表記を使うことができます。これを使い、2桁（1桁の場合は10の位に0を付ける）で表示できます。
他にもいろいろな表記方法がありますので下のリンクから確認してみてください。おそらくプログラミングコンテストではこのString.formatをよく使うと思います。
参考:Formatter
成績
提出したプログラムの実行時間・メモリ使用量をまとめました
| 実行時間 |
メモリ使用量 |
| 85 ms |
23252 KB |
ここをクリックで閉じます
C - 風力観測
見出しをクリックすると開きます。↓↓
問題
問題文
ある風向風速計は、風向の角度と風程を 1 分毎に自動で記録してくれます。
風向の角度というのは真北を 0 度とし、そこから時計回りに風の吹いてくる方向を定めたものです。気象観測等では全体を等しく 16 分割した 16 方位が用いられます。16 方位と角度は、以下の表のように対応します。
風向と角度の関係
| 方位 | 角度 |
方位 | 角度 |
| N (北) | 他のいずれにも当てはまらない |
S (南) | 168.75 度以上 191.25 度未満 |
| NNE (北北東) | 11.25 度以上 33.75 度未満 |
SSW (南南西) | 191.25 度以上 213.75 度未満 |
| NE (北東) | 33.75 度以上 56.25 度未満 |
SW (南西) | 213.75 度以上 236.25 度未満 |
| ENE (東北東) | 56.25 度以上 78.75 度未満 |
WSW (西南西) | 236.25 度以上 258.75 度未満 |
| E (東) | 78.75 度以上 101.25 度未満 |
W (西) | 258.75 度以上 281.25 度未満 |
| ESE (東南東) | 101.25 度以上 123.75 度未満 |
WNW (西北西) | 281.25 度以上 303.75 度未満 |
| SE (南東) | 123.75 度以上 146.25 度未満 |
NW (北西) | 303.75 度以上 326.25 度未満 |
| SSE (南南東) | 146.25 度以上 168.75 度未満 |
NNW (北北西) | 326.25 度以上 348.75 度未満 |
風程というのは、風向風速計の風車が、ある一定の時間に風によって回った量を距離によって表したものです。
例えば、1 分間の風程が 300m というのは、1 分間に吹いた風によって風車が 300m 回ったという事です。この時、この 1 分間の平均風速は 300m を 60 秒で割って、5m⁄s と求められます。
与えられたデータを、ラジオ等で流れる「気象通報」と同様の形式に直そうと思います。
気象通報では、16 方位での風向と、風力 (ビューフォート風力階級) が伝えられます。
風向は、先の表の 16 方位です。
ただし、風力 0 の場合、実際には「風弱く」と伝えられるため、風向は 16 方位ではなく、特別な向きであるCとします。
風力は、風速を計算し、小数第 2 位を四捨五入して、以下の対応により風力に変換します。
風力と風速の関係 (ビューフォート風力階級)
| 風力 | 風速 |
風力 | 風速 |
風力 | 風速 |
| 風力0 | 0.0m⁄s 以上 0.2m⁄s 以下 |
風力5 | 8.0m⁄s 以上 10.7m⁄s 以下 |
風力10 | 24.5m⁄s 以上 28.4m⁄s 以下 |
| 風力1 | 0.3m⁄s 以上 1.5m⁄s 以下 |
風力6 | 10.8m⁄s 以上 13.8m⁄s 以下 |
風力11 | 28.5m⁄s 以上 32.6m⁄s 以下 |
| 風力2 | 1.6m⁄s 以上 3.3m⁄s 以下 |
風力7 | 13.9m⁄s 以上 17.1m⁄s 以下 |
風力12 | 32.7m⁄s 以上 |
| 風力3 | 3.4m⁄s 以上 5.4m⁄s 以下 |
風力8 | 17.2m⁄s 以上 20.7m⁄s 以下 |
|
| 風力4 | 5.5m⁄s 以上 7.9m⁄s 以下 |
風力9 | 20.8m⁄s 以上 24.4m⁄s 以下 |
|
風向 (角度) と 1 分間の風程が入力されるとき、それを気象通報の形式に直して出力するプログラムを作成してください。
入力
入力は以下の形式の 1 行からなる。
Deg Dis
- Degは風向を示し、本来の角度を 10 倍した整数で与えられる (例えば、90 度なら 900、137.5 度なら1375と与えられる) 。
-
Disは 1 分間の風程を示す整数である。単位はメートル (m) である。
出力
出力は以下の形式の 1 行とする。
Dir W
-
Dirは風向を示し、
C, N, E, W, S からなる 1〜3 文字の文字列である。
-
Wは風力を示し、0 以上 12 以下の整数である。
また、出力の末尾には改行を入れること。
入力例 1
- 2750 628
- この場合、風向は 275 度、風程は 1 分あたり 628m である。
出力例 1
- W 5
- 275 度は西向きなので、
Wと出力する。
- 1 分で628mということは、10.46m⁄sなので、小数第 2 位を四捨五入して10.5m⁄sとなり、風力 5 に相当する。
出力例 2
- C 0
- 風向は本来
NNEだが、風力 0 であるためCとする。
出力例 3
- NNW 1
- 浮動小数点数型での計算は、誤差が発生する恐れがあります。
- 環境によって計算結果が変わることもありますので、誤差には十分注意しましょう。
ここをクリックで閉じます
回答
少しずつ難しくなってきましたね。ですがこれもやることは今までと変わりません。if文を問題文の条件を読み取って記述するだけです。
少し長くなってしまいましたね。もう少しきれいに書けたかもしれません。
ポイント1 先に風力を求める
問題文に
ただし、風力 0 の場合、実際には「風弱く」と伝えられるため、風向は 16 方位ではなく、特別な向きであるCとします。
とあります。先に風力を求めることで、風力0の場合に無駄な処理をしなくてよくなります。
getWindPowerという関数を使い風力を求めています。
ポイント2 四捨五入にMath.roundを使う
Java言語では四捨五入にMath.roundを使います。
ポイント3 問題文を読み取り比較時は整数同士で比較する
問題文では小数点の数値の比較をするようにしています。しかし、比較数値をそれぞれ10倍することで浮動小数点型の計算をしなくてよくなります。
問題文では風力を60秒で割ると書かれていますが、int ms = (int) Math.round(dis / 6.0);このように6で割り、比較する風速を10倍にすることで小数点を使わないようにしています。
風向きも入力の説明文にこのような記述があります。
風向を示し、本来の角度を 10 倍した整数で与えられる (例えば、90 度なら 900、137.5 度なら1375と与えられる) 。
このことから比較に使われている角度の小数点以下第2位は関係ないことが分かります。問題文に書かれている比較角度を10倍して四捨五入した値を使うことで小数点の計算をしないようにできます。33.75 度未満は338 未満と書き替えることができます。
ポイント4 割り算をするときには割る数を浮動小数点表記にする
この問題では風力を計算するときに60で割った数を四捨五入するとあります。（そんなのなければ、単に比較対象を60倍するだけでよかったのに）
ですから、比較対象を10倍して風程を6で割った四捨五入を求めています。
int ms = (int) Math.round(dis / 6.0);
この1行ですね。その時に気を付ける必要があるのはint/intの結果はintに切り捨てされてしまうという事です。たとえば3/5は本来は0.6ですが、プログラムはint型を返すので0になります。四捨五入しなくてはいけないのに、切り捨てになってしまうのでそれを回避する必要があります。
回避するには割る数をdouble型等の浮動小数点表記で記述することです。5.0などですね。そうするとプログラムは浮動小数点で返します。3/5.0は0.6と返します。
その結果をMath.roundで四捨五入しています。
成績
提出したプログラムの実行時間・メモリ使用量をまとめました
| 実行時間 |
メモリ使用量 |
| 80 ms |
23252 KB |
ここをクリックで閉じます
改善
公式の解説を読むと、if文をできるだけ削るようにというアドバイスがありました。
でも、if文を大量に書くような実装をしてはいけません！ - 通るけれども、面倒だし、バグも出やすい
さらに、
16方位の間隔は全て一定 - 全部のif文を書かずに、繰り返しで処理できる！ 全ての間隔は22.5度間隔なので、22.5度ずつ増やし て判定する
を考慮して、プログラムを作り直してみました。
ポイント1 if文の閾値を配列で用意する
風力は0から順に1ずつ増えていきます。それを利用して、for文の中でif文を書くことができます。各条件文の閾値を配列に入れることで、条件文もスマートにしました。
if(ms<=THRESHOLD[i])のように書けます。
ポイント2 風向きの文字列を配列で用意する
風向きの文字列を配列で用意することで、条件文を次のように書くことができます。
if (deg < 113 + 225 * i) return WIND_DIR_NAME[i];
成績
作り直したプログラムの成績をまとめました。
速度は遅くなってしまいましたが、可読性は向上しました。
ここをクリックで閉じます
D - 感雨時刻の整理
見出しをクリックすると開きます。↓↓
問題
問題文
雨の降っていた時刻というのは、降水量と並んで重要です。今、ある 1 日の、雨が降っていた時刻に関するメモが見つかったので、これを整理して、雨の降っていた時刻を調べたいと思います。
整理は、以下の規則に従って行います。
-
感雨時間のメモから、その日 1 日の雨の降っていた時刻を時系列順に出す。日付を超えて降っている雨は、 00:00 降り始めや 24:00 降り終わりとして扱われるものとし、日付をまたぐようなメモは入力されない。
-
雨の降り始め・降り終わりはそれぞれ直前・直後の 5 分単位の時刻に丸める。例えば、13:23 に降り始めて 14:01 にやんだ雨は、13:20 から 14:05 まで降っていたということにする。
-
丸めた後の結果において、2 つ以上のメモに書かれていた感雨時刻が重複した場合、1 つの連続した雨とみなす。例えば、11:06 に降り始めて 11:23 にやんだ雨、11:29 に降り始めて 12:03 にやんだ雨、11:48 に降り始めて 12:10 にやんだ雨の 3 つがあった場合、11:05〜11:25、11:25〜12:05、11:45〜12:10 の 3 つの雨であるが、時間がかぶっているところをくっつけて 11:05 から 12:10 まで降っていた、1 つの連続した雨ということにする。
メモの内容が入力される時、雨の降っていた時刻を、この規則に合致するよう整理して出力するプログラムを作成してください。
入力
入力は以下の形式で標準入力から与えられる。
N
S1-E1
S2-E2
:
SN-EN
- 1 行目には、連続して雨の降っていた時刻の数を表す整数 N (1≦N≦30,000) が与えられる。
- 2 行目から N+1 行目までの N 行で、雨の降り始めの時刻と降り終わりの時刻が与えられる。
- この中の i (1≦i≦N) 行目において、雨が降り始めた時刻 Si と雨が降り終わった時刻 Ei がハイフンで区切られて与えられる。
- 時刻 Si と Ei において
- 時刻は必ず 4 桁の非負整数で与えられる。
- 時刻の上 2 桁が時間 (hour) 、下 2 桁が分 (minute) を表す。
- 時刻は 0000 から 2400 まで取り得る。ただし下 2 桁の部分が 59 を超えることはない。
- Si が Ei より前の時刻であることが保証されている。
出力
雨が降っていた時刻を整理して、降り始めの時刻の早い順番に、降り始めた時刻と降り終わりの時刻をハイフンで区切って出力せよ。
その際、連続した 1 つの雨を 1 行に出力し、時刻の形式は入力と同じ形式を用いること。
また、出力の末尾には改行を入れること。
入力例 1
- 4
- 1148-1210
- 1323-1401
- 1106-1123
- 1129-1203
- 11:48〜12:10 の間、雨が降っていた。
- 13:23〜14:01 の間、雨が降っていた。
- 11:06〜11:23 の間、雨が降っていた。
- 11:29〜12:03 の間、雨が降っていた。
出力例 1
- 1105-1210
- 1320-1405
- 入力を 5 分単位に丸めると、順に 1145-1210、1320-1405、1105-1125、1125-1205となる。
- これを降り始めの時刻の早い順に直すと、1105-1125、1125-1205、1145-1210、1320-1405となる。
- 1105-1125、1125-1205の 2 つは、前者の降り終わりの時刻と後者の降り始めの時刻が一致するので、くっついて 1105-1205 となる。
- さらに、1105-1205 と、1145-1210 は、後者の降り始めの時刻が前者の降っている時刻の間に入るので、くっついて 1105-1210 となる。
- そのため、結局この例のような出力となる。
- なお、出力は雨の降った時刻の早い順でなければならない。
入力例 3
- 6
- 1157-1306
- 1159-1307
- 1158-1259
- 1230-1240
- 1157-1306
- 1315-1317
ここをクリックで閉じます
回答
難問です（メモリ的に）
ABCやARCともに設問Dはメモリの使用量に気を付けなくてはいけないようですね。特にjavaは普段からメモリ使用量が高いため、注意が必要です。
時刻が入力された場合これまでに入力された時刻を検索し、時刻がつながった場合はつながった時刻を今の時刻とします。その時、既に入力された時刻を削除する必要があります。
もし時刻がつながらなかった場合はそのまま時刻を保存します。
for(int i=0;i<n;i++){
//時刻を取得
while(has.next()){
//今までの時刻とつながれば、つなげたものを時刻とし、記録されていた時刻を削除する
}
//時刻を追加
}
大まかなアルゴリズムはこんなです。
ポイント1 メモリ使用量を考慮して、読み込み次第逐次的に処理をする
私が下手なだけなのかもしれませんが、データをすべて読み込んでから処理しようとするとメモリエラーが起きてしまいます。ですのでbr.readLine()から次のbr.readLine()の間に処理をしなくてはいけません。
ポイント2 与えられた文字列から時と分を分ける
読み込んだデータをintに変える前に時と分に分けましょう。Javaではsubstringを使うことで文字列を指定した範囲で切り抜くことができます。それを使い、時と分に分けました。
ポイント3 時を60倍して分に変換する
与えられた数値のままだと直感的に考えることができないため時単位を60倍して分単位にしました。そうすると比較時に直感的に大きいかがすぐわかります。また、下2桁が60までという制限も考えなくてよくなります。すべてを分単位で計算し、最期の出力の時に時分形式で出力すればいいのです。
私の回答の29行目startHour * 60 + startMinuteFloorやendHour * 60 + endMinuteCeilのところを指します。
ポイント4 Rangeクラスを使ってオブジェクト指向で解く
私、詳しくないです。これがオブジェクト指向といえるのかがわからないですが、クラス使ってるからそうだと思いますw せっかくJava使ってるんですからオブジェクト指向にしよう！
Rangeクラスに以下の要素を付けました。
- 降雨開始時刻（分単位）
- 降雨終了時刻（分単位）
- 時刻範囲を文字列で表示する機能toString()
- 他の時刻範囲がこの時刻範囲とつながるかを判断する機能isContain()
- 他の時刻範囲とこの時刻範囲を合体させ、一つの時刻範囲として返す機能combine()
- Comparableを実装することで、標準機能でRange同士の比較が可能（ソートが可能）
こうすることで、br.readLine()から次のbr.readLine()までの間のコード量が減り、多分可読性が上がったと思います。
ポイント5 Iteratorを使う
ループの中でListの要素を削除する際に普通にやってはいけません。Iteratorを使うことで安全に要素を削除できるようにしました。
悪い例
for(int i=0;i<size;i++){
list.remove(i);//してはいけません！
}
良い例
Iterator<Range> it = list.iterator();
while(it.hasNext()){
it.remove();
}
ポイント6 Comparableを実装することで、sorted()が使える
RangeクラスにComparableを実装することで、ranges.stream().sorted()という風に標準機能のソートを自動で使うことができるようにしました。
成績
提出したプログラムの実行時間・メモリ使用量をまとめました
| 実行時間 |
メモリ使用量 |
| 421 ms |
44320 KB |
結構ぎりぎりだと思います。
ここをクリックで閉じます
改善
おしい！
ところはできていました。ただ、時間軸の配列を使うなんて思ってもみなかったので勉強になりました。
時間軸の配列を使う
分に単位を統一した時間軸の配列を用意します。
table[0]...table[60*24]まで使えるようにします。ただし私のプログラムでは最後の配列の次の要素にダミー要素を入れておかないと正常に機能しないため、new boolean[TIME_MAX +1 + 1]としました。
時間軸の配列を用意する利点はNが増大してもこの配列のサイズは変わらないという事です。また、要素を読み込むたびに比較しなくてもよく、単に一致している時間軸の要素をtrueするだけでよいという事も利点です。
成績
改善したプログラムの成績をまとめました
| 実行時間 |
メモリ使用量 |
| 271 ms |
41856 KB |
実行時間が0.1秒以上も早くなり、メモリ使用量も減少しました。
ここをクリックで閉じます
まとめ
AtCoderの過去問を初心者クラスですが、すべて解くことができました！実際は2時間で解く必要があるタイムアタックなのですが、過去問の場合はその制限がありません。じっくりと考えることができました。問題をすべて解くのに3時間ちょっとかかったので、本番でしたら半分ほどしか解けていなかったことになります。練習を重ねて2時間ですべて解けるようになりたいです。
また、Dの設問ではメモリの使用量を考慮する必要があったため、ただ解くだけではなくそういった問題も考慮して常にプログラムを書く必要があるのだなと実感しました。
なけなし程度ですがJava8の要素も使えてよかったです。満足です！
終わりに
ここまで読んでくださってありがとうございます。ほとんどの方が興味のないものだったと思いますが、少しでもプログラミングに興味を持ってくださる方がいれば幸いです。
読者登録ありがとうございます。励みになっています。
今回は記事中にクリックしたら開閉するシステムを導入してみました。HTMLやjsの勉強にもなっていい感じです。
記事の文字数60000オーバーｗHTMLでも記述したりしているのでそりゃそうなりますか。もしかしたらはてなブログ書いてる人の中で一番多い文字数書いたかも？ｗ(*'ω'*)
今日ぎりぎりに記事にできてよかったです。おやすみなさい。_(:3」∠)_
またね('ω')ノ
