ABC094 C問題解けた

投稿者: | 2018年8月12日

いろいろとやってたら、気がつけばプログラムを書くという動作を1ヶ月ぐらいしてないことに気が付きました。

はっきり言ってマジでやべーです。配列が0スタートなのを忘れてバグ出しまくりました。

今回解いた問題は次の問題です。解法はバイト中に思いつきました。

[blogcard url=”https://beta.atcoder.jp/contests/abc094/tasks/arc095_a”]

中央値とは

私がまず躓いたのが「中央値って何だっけ?」ってことです。電流や電力と戯れてたら忘れました。

中央値とは

中央値(ちゅうおうち、英: median)とは、代表値の一つで、有限個のデータを小さい順に並べたとき中央に位置する値。たとえば5人の人がいるとき、その5人の年齢の中央値は3番目に年寄りな人の年齢である。ただし、データが偶数個の場合は、中央に近い2つの値の算術平均をとる。

wikipedia

sortした配列のど真ん中取ればいいということですね。

解法

まず元の配列をsortし、sortした配列の中央値を取ります。この時nは偶数ということが問題で保証されているので、中央値は2つ取ります。

次に元の配列を前から取り出し、先程の中央値と比較します。この時、比較する中央値は小さい方、大きい方どちらでもいいですが、それぞれ条件がちょっとだけ変わるので注意です。

最後に、中央値と元の配列の値を比較し、大きければ小さい方の中央値、小さければ大きい方の中央値を出力します。

以上のことをプログラムすると、次のようになります。

[cpp]

#include <iostream>
#include <algorithm>
using namespace std;
int main(int argc, char const *argv[]) {
int n;
cin>>n;
int a[n],b[n];
for(int i=0;i<n;i++){
int tmp;
cin>>tmp;
a[i]=tmp;
b[i]=tmp;
}
sort(b,b+n);
// for(int i=0;i<n;i++){
// cout<<b[i]<<",";
// }
// cout<<endl;
int med1=b[n/2-1],med2=b[n/2];
// cout<<med1<<","<<med2<<endl;
for(int i=0;i<n;i++){
cout<<((a[i]<med2)?med2:med1)<<endl;
}
return 0;
}

[/cpp]

バイト中にこれを思いついた時、自分のバカさ加減に呆れてました。「なんでこれをすぐに思いつけなかったのか・・・」と。

まず中央値ってなんだっけ?ってあたりからやばいです。ちゃんと勉強しよう・・・。

コメントを残す

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください