AtCoder Regular Contest #004 C: 平均値太郎の憂鬱

問題

ここ参照。

方針

本番中は二分探索をしていた。ほとんどのケースは通っていたのだけれど、いくつかのケースで落ちていた。分数が既約分数だと思い込んでいたけど、そうじゃない場合もあるようだ。おそらく落ちた原因はそれだと思う。
二分探索よりスマートでシンプルな解法があって、以下の2次不等式をiについて解けばよい。

平方根とか出てくるけど、マージンを取るような方向の近い整数に丸めるとよい。

ソースコード

view plainprint?

1. using namespace std;  
2.   
3. #define REP(i, n) for(int i=0; i<(int)(n); i++)  
4. #define FOR(i, s, e) for (int i = (int)(s); i < (int)(e); i++)  
5.   
6. long long gcd(long long a, long long b) {  
7.     if (!b)  
8.         return a;  
9.     return gcd(b, a%b);  
10. }  
11.   
12.   
13. int main() {  
14.     long long x, y;  
15.     char c;  
16.   
17.     cin >> x >> c >> y;  
18.     long long g = gcd(x, y);  
19.     x /= g;  
20.     y /= g;  
21.       
22.     bool res = false;  
23.     for (long long i = (2*x-y)/y/y; i <= (2*x+y)/y/y+1; i++) {  
24.         long long n = i*y;  
25.         long long sum = n*(n+1)/2;  
26.         long long m = sum - i*x;  
27.         if (1 <= m && m <= n) {  
28.             res = true;  
29.             cout << n << " " << m << endl;  
30.         }  
31.     }  
32.   
33.     if (!res)  
34.         puts("Impossible");  
35.     return 0;  
36. }  

using namespace std;

#define REP(i, n) for(int i=0; i<(int)(n); i++)
#define FOR(i, s, e) for (int i = (int)(s); i < (int)(e); i++)

long long gcd(long long a, long long b) {
    if (!b)
        return a;
    return gcd(b, a%b);
}


int main() {
    long long x, y;
    char c;

    cin >> x >> c >> y;
    long long g = gcd(x, y);
    x /= g;
    y /= g;
    
    bool res = false;
    for (long long i = (2*x-y)/y/y; i <= (2*x+y)/y/y+1; i++) {
        long long n = i*y;
        long long sum = n*(n+1)/2;
        long long m = sum - i*x;
        if (1 <= m && m <= n) {
            res = true;
            cout << n << " " << m << endl;
        }
    }

    if (!res)
        puts("Impossible");
    return 0;
}

サーバー奮闘記（21） CakePHPの設定

しばらく仕事では開発をしていなくて、要件定義とかオフショアメンバーの成果物・タスク管理とかミーティングとかミーティングとかミーティングとかを専門にやっていたのだが、最近フレームワークについてがっつりと勉強できそうなプロジェクトメンバーに採用された。

せっかくなので、家でもフレームワーク使ってなにかwebサービス作ってみようかなと思ってCakePHPを導入した。なんかしょっぱなからつまってしまった。『SampleControllerを作ろう！』のサンプルコードが動かない。

Apacheの設定上書き機能がOFFになっていたことが原因だったらしい。CookbookのAdvanced Installationのページを参考にして、以下を実施したら解決した。

1. /etc/apache2/sites-available/defaultの「AllowOverride」の部分をNoneからAllにする。

2. Apacheを再起動する

動いたのはいいけど、そもそもこれって何なのかよく理解できていないので、『Apache の基本的な設定』を参考にちょっと調べてみた。

まず、「.htaccess」ファイルについて。このファイルはこれが置かれたディレクトリとそのサブディレクトリについてのアクセス設定を行うファイル。
次に/etc/apache2/sites-available/defaultのAllowOverrideの項目について。この項目は、defaultファイルで設定した一般的な設定を、ドキュメントルート配下のサブディレクトリで上書きできるかどうかを設定するもの。この項目をNoneとしていれば、上書きを許可しないので、「.htaccess」でアプリケーション固有のアクセス設定を書いたとしても無視される。この設定をAllとすれば、各アプリケーションの「.htaccess」で定義した設定が、defaultの設定を上書きアクティブになる。

読書「ノルウェイの森」

  ノルウェイの森を読んだ。人の死、家族、性の描写というのは文学の共通テーマなのかなと思った。最後の方は電車の中で泣きそうになるのを堪えて読んでいた。

  登場人物の中では永沢という男が好きだ。あのストイックさと精神的な強靭さはすごいなと。彼が語る「労働と努力の違い」が印象的だった。曰く、世の中の大半の人間は努力をしていない。彼らは労働はしているが、努力はしていない。努力というのは主体的に目的的になされるものだと。

  加えて、「誰にも理解されたいとは思っていない」という部分は自分も共感できた。人は人で、自分は自分。人がどう評価するかよりも、自分が自分の行動をどう評価するかを大切にする。人からの評価はあまり気にしない。もちろん尊敬する人や、信頼している人の評価や助言は聞き入れるが、それ以外は自分の信条と異なっていれば相手にしない。とか言いつつも、それは自分の中の理想像であって実は周りの同僚や上司の評価をしてしまうときもある。彼のように強い人間になるためには、やはり彼自身がやっているような日々の反復的な努力・自分磨きが必要だと思う。

  主人公のワタナベが愛読している「グレート・ギャツビー」が気になるので、これ読んでみようと思う。あと「ライ麦畑」も。この辺は社会人の嗜みとして抑えておくべきだと思う。

来た、来た、来た、来たーー！！

  来た、来た、来た、来たーーー！！！
ついにSRMでyellow coderになりました。MarathonもYellowなので、これでDouble Yellow Coderです。

  昨日のSRMでは、不要なチャレンジをして100位くらい順位を落としたのですがそれでもなんとか黄色くなれました。次の目標はMediumの問題を確実に解けるようになるということです。感覚的には500を見てもそれほど難しいとは思わなくなってきていて、あとは時間内に解けるようになるように日々反復的に練習していけば何とかなりそうかなと思っています。

  せっかく黄色くなれたので、Ratingについて最近考えていたことについて書こうと思います。というのも時間をかけて練習しているのになかなかRatingが上がらなくて苦しんだ時期があったからです。そのとき自分がRatingとどういうふうに向きあったかということを、同じように結果が出なくて苦しんでいるCoderの方々に共有したいと思います。

  Ratingというのは相対評価なので、それほど意識しない方がいいと思います。みんなの出来が悪かったときに自分の調子がよければ上がるし、みんなの出来がいいときにやらかしてしまうと下がる。まあその程度のものかなと思っています。もっと大切なことは、今までに自分が解けなかった問題が解けるようになったかどうかであり、TopCoderの問題を通して新しい数学の知識や論理的思考能力がついたかどうかであって、そういう意味では自分との戦いであって、人と比べてどうこうというのは気にしすぎないようにした方がいいと思います。Ratingの増減に敏感になりすぎたら、競技に参加すること自体が楽しくなくなってしまうので、ダメなときはダメでいいさ、ダメだったときは学習するチャンスを神様から与えられたのだ、と考えるようにしています。逆にうまくいったときは、今まで自分がやってきたことは正しかったんだ、この調子で続けていこう。という風に考えます。

  おそらく、誰でもがんばれば黄色にはなれるのかなと思っていて、ようやくスタート地点に立てたのかなという感覚です。ここから赤色になるまでに、これまで以上の苦難や高い壁があるということは分かっています。もしかしたらライフワークになるかもしれませんが、赤色になるまでは、--いや敢えてここではターゲットになるまではと言わせてください-- 挑戦し続けたいと思います。