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

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

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

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

中央値とは

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

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

解法

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

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

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

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

[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]

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

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

久しぶりにABCのC問題を真面目に解けたのでメモ。私のようなプログラム書けない馬鹿でもたま〜にちょっと整理すれば数学的に解ける問題あるから楽しい。私がまともに解けた問題は以下の問題。
[blogcard url=”https://beta.atcoder.jp/contests/abc100/tasks/abc100_c” title=”C – *3 or /2″]
問題を整理すれば、

• • “すべて”の数列の要素に対して
  • 2で割る
  • 3掛ける(ただし全て3を掛けてはいけない)

最初問題読んだ時、”すべて”というのを見落として、「これ無限に終わらなくね？」ってなりました。問題文はちゃんと読もう。
さて、ちゃんと問題を理解したところで、問題を解いていきましょう。

1,とりあえず偶数だけ考えれば良い

2と3は互いに素なので、3はいくらかけても2で割るという行為には影響しません。また、2で割れない奇数は3掛ける操作しかできない為、偶数のみ考えればいいということがわかります。
そこで最初に考えたことが、「2で割れる回数の最大回数じゃね？」ということですが、サンプル1でそれはおかしいことがわかります。しかし、2で割る回数という方針は正しかったです。
最初に考えた解法がコードを書いてサンプル1を通した瞬間に間違えてることがわかって落胆したので、次の解法を考えます。

2,とりあえず2で割ってしまう

「2で割れる回数」という方針は正しいはずです。でなければ、問題にがわざわざ「２で割る」という操作をさせるはずがありません。なので、この方針はそのままに真面目に考えました。
さて、「2で割る」ですが、どこまで「２で割る」のでしょうか。これは、「すべての要素に対して3倍できない」というところから考えられます。つまり、「すべての要素が2で割れなくなった」ところまで要素を割り続けます。
では、どのようにして「2で割り」ましょうか。求める解は「最大回数」ですので、2で割れる要素を同時に2で割ると、2で割るという操作が1回分回数が節約されます。これだと最大回数にならないので、考えるべきは「各要素を一個ずつ2で割っていく」という操作だとわかります。
また、複数の偶数に対して2で割れる最大回数を求める時、ある偶数を2で割り切れなくなるまで2で割り続け、2で割り切れなくなったら次の偶数を2で割り続けると考えればうまくいきます。また、2で割れきれなくなった偶数はその後考えませんが、思考の外では、これらは3を掛け続けている状態となっています。
まとめると、「各要素１個ずつ、その要素が2で割れなくなるまで2で割り続け、最終的にそのそれぞれの2で割った回数を足し合わせればいい」となります。
このあたりは、簡単な図をかいてみるとわかりやすかったです。
以上のことをプログラムで書くと次のようになりました。

[cpp]
        #include <iostream>
                using namespace std;
                int counter(int);
                int main(int argc, char const *argv[]) {
                  int n;
                  cin>>n;
                  int ans=0;
                  for(int i=0;i<n;i++){
                    int tmp;
                    cin>>tmp;
                    if(tmp%2==0)  ans+=counter(tmp);
                  }
                  cout<<ans<<endl;
                  return 0;
                }
                int counter(int a){
                  int count=0;
                  while(1){
                    if(a%2==0){
                      count++;
                      a=a/2;
                    }else{
                      break;
                    }
                  }
                  return  count;
                }
        [/cpp]

これを実行した結果、実行時間は7msでした。結果一覧を見てみると、こういう書き方をした場合7msのようです。しかし、実行時間2msの人もいるので、もっと高速化できるんだと思いました。
とは言っても、「２で割りまくる」というのは同じです。しかし、私がどうやって書いても2msにならなかったので諦めます。また、上のコードは無駄ばっかだったので、もっと短く書き直しました。

[cpp]

#include <iostream>
using namespace std;
int main(int argc, char const *argv[]) {
int n;
cin>>n;
int ans=0;
for(int i=0;i<n;i++){
int a;
cin>>a;
while(a%2==0) a/=2,ans++;
}
cout<<ans<<endl;
return 0;
}

[/cpp]

最初からこれで書けばよかった・・・。