だらだら競プロ適当解説：AtCoder Beginner Contest 001
だらだら問題を埋めていこうと思ったので適当にやってく。
どうせだから解説もして資産として残そうみたいな。
総評
古い問題なので問題文に記載されているようにあまりお勧めしない。
他のABCの問題のほうが良質であると思われるので初めに着手する問題ではないかなと思う。
配信中にC問題を解いてるときに怒りのあまりクソクソ叫んでいた。
アルゴリズム的な勉強になるのはD問題だけかと思われる。
C問題は苦痛を伴ったため、初心者バイバイ感があるのでお勧めしないが、まったく知見が得られないわけではない。
A - 積雪深差
問題文に記載のある通り「積雪深差 H1 − H2」するだけ。
標準入出力ができれば解ける問題。
略解
int H1, H2;
cin >> H1 >> H2;
cout << H1 - H2 << endl;
ポイント
特にない。それぞれの言語の入出力を勉強してください。
B - 視程の通報
やたらとだらだらとif分岐してくださいみたいな問題文がある。
if分岐ができることと入出力データの加工ができればいいという問題。
略解
int m; int ret; cin >> m; if (m < 100)//1 { ret = 0; } else if (m <= 5000)//2 { ret = m / 100; } else if (m <=30000) { ret = m / 1000 + 50; } else if (m <= 70000) { ret = (m / 1000 -30 ) / 5 + 80; } else { ret = 89; } cout << setfill('0') << setw(2) << ret << endl;
ポイント
if分岐は愚直に下限と上限を書いてもいいが、必ず範囲内にあるという説明があるので、上記のように上限だけを定めてもうまくいく。
出力に関しては幅指定と0埋めの併用で解決した。
こういった機能がない場合は、文字列として処理するか、10で割った結果が0かどうかで桁数を判断し、0を足せばいいはず。
C - 風力観測
配信中クソクソのクソと叫んでいた問題。
いやらしい部分がたくさんある。
略解
//略式 //Degで分岐して. if (Deg <= 112) { Dir = "N"; } else if (Deg <= 337) { Dir = "NNE"; } else if ... //Disの分岐もする. //小数点第二の四捨五入がちょっといやらしい. tmp = Dis / 6.0f; tmp = round(tmp); //あとはif文か...ひたすら面倒. if (tmp <= 2) { W = 0; Dir = "C"; } else if (tmp <= 15) { W = 1; } else if ... cout << Dir << " " << W << endl;
ポイント
Dir を愚直にifで解いたが以下のようにすると簡略化できる。
string Dir[15]={"N", "NNE", .. .}; //Nの半分(1125)をオフセットしたうえで1方位分で割る. int ID = (Dis * 10 + 1125) / 2250 % 16; //16であまりを出すのはDisが348.75を超えたときに16になるため. Dir[ID];//これで方位が得られるね.
浮動小数点の扱いに気を付ける。
小数点第二の四捨五入だが、これは愚直に解くと以下の形になる。
tmp = Dis / 60.0f //言われた通りの60 tmp = round(tmp * 10.0f) /10.0f; //ex. A=123.45 round(A * 10.0f) = 1235.0f
１０倍した後、関数で小数点第一位を四捨五入しまた１０で割れば結果的に小数点第二位が四捨五入されたことになる。
だが、これをやると浮動小数点の丸め誤差で数値に微妙に変化が起きることがあり、単純にはいかない。(例えば0.2が0.19999999になったり)
今回の場合でもDis / 60.0fの際に丸まる可能性があり、実際に誤差を含んでしまいWAを食らった。
起きるか起きないかは理論的に説明もできるが、いちいち考えてられないので運みたいなものだと思ったらいい。
上記の略解では10倍して計算して回避したが、それでうまくいくかどうかは運なので、しっかりやるなら以下のようにする。
//今回は２ケタで丸めるのでここは影響がないはず. double eps =0.001f; //誤差で微妙に減ってしまった値に足す. 0.2499999→0.259999 tmp = Dis / 60.0f+eps; //これマイナス符号の時は引く感じになるね tmp = round(tmp * 10.0f) /10.0f; //うまくいくはず.
あるいは小数をそもそも使わないで風程のままで処理する。
if (Dis < 15) //15=0.25f * 60.0f { W = 0; Dir = "C"; } else if (Dis < 93) { W = 1; } else if ...
ここで「0.20f * 60.0f」ではなく、「0.25f * 60.0f」としているのは小数第二位の四捨五入を読み替えによるもの。
小数第二位の四捨五入とは要するに0.05より小さいかどうかなのでこの値を判定値側に足すことで解決できる。
直値でコードに書きたくない場合は25*60/100とかが適当な気がしますね。
D - 感雨時刻の整理
解法さえ思いつけばCより楽。というか苦痛ではない問題。
雨の降った区間をくっつけて、くっつかなかったすべての区間を出力する問題。
略解
int N; pair<int, int> Data[30000]; //ペアで持つとソートが楽. // Input cin >> N; for (int i = 0; i < N; i++) { cin >> Data[i].first >> Data[i].second; //ハイフンはマイナス扱いで入ってくるので打ち消す. Data[i].second *= -1 } //Do // Sort sort(Data, Data + N); //降り始め時間が小さい順で並ぶよ. //Output int Scount= -1; //初期値.初めに通りさえすればよい. for (int i = 0; i < N; i++) { int S = Data[i].first - Data[i].first % 5; //まるめ. if (S <= Scount) { continue; } cout << setfill('0') << setw(4) << S << "-"; int E = (Data[i].second % 5 == 0) ? Data[i].second : Data[i].second + (5 - Data[i].second % 5); //まるめ. if (E % 100 == 60) //丸めた結果60になったら繰り上げ. { E += 40; //要するに+100して-60する. } //End calc for (int j = i + 1; j < N; j++) { int S2 = Data[j].first - Data[j].first % 5; int E2 = (Data[j].second % 5 == 0) ? Data[j].second : Data[j].second + (5 - Data[j].second % 5); if (E2 % 100 == 60) { E2 += 40; } if (E < S2) { //end; break; } if (E < E2) { E = E2; } } cout << setfill('0') << setw(4) << E << endl; Scount = E;// until E
ポイント
入力は文字列で受け取ってハイフンで区切って加工してもいいが、適当に読んでも結構なんとかなる。
時間と分をわけて保存して解くこともできるが、ソートやらなにやらで面倒になることが予想されたので、ここではそのまま利用してしまう。
この手の問題は前から順に作業したほうがコードが複雑にならずに計算時間もかからないため、まずソートしてしまう。
SとEを別々の変数に定義するとソートの際に面倒なことになるので、pairとかクラスとかを用いるといいと思う。
丸め方は上記の通り、余りを利用すれば比較的素直に解ける。分が60になった時の繰上りを忘れずに。
考え方は次のもののスタートが自分のエンドより前なら結合が可能で、その場合はエンドを見比べて大きいほうにするという処理を順次やる。
既に計算済みのものを飛ばすために、出力後はScountを出力したEにしておく。
iを直接j-1番目まで移動させるという方法もある。(breakの前にi=j-1 for終了後にi++されるため先に引いておくのでj-1である)
出力はB問題と同様に0埋めと幅指定で対応できる。
