AtCoder Regular Contest 052

4月30日に行われたARC052に参加しました。
結果はA,B問題を通しての200点で順位は158位でした。D問題で10点部分点を取れれば100位以内に入れたのでなんとかしたかったですね。やはりコード書くのが遅すぎるのが問題だと感じます。
以下各問振り返り
（今回解説放送をほとんど真面目に聞いていなかったのであまりちゃんとした反省になっていません……）

A問題『何期生？』

受け取った文字列を頭から見ていって数字があったらひとつ次まで調べればいいのだろうと考えました。この程度のプログラムにも16分かかるのが今の実力という感じです。

int main(){
    string s;
    int ans=0;
    cin>>s;
    REP(i,s.size()){
        if('1'<=s[i]&&s[i]<='9'){
            if('0'<=s[i+1]&&s[i+1]<='9'){
                ans = (s[i] - '0')*10 + s[i+1] - '0';
                break;
            }else{
                ans = s[i] - '0';
                break;
            }
        }
    }
    cout<<ans<<endl;
}

B問題『円錐』

各円錐について、の領域に一部分でもあるかを判定して、あったら計算すればいいのだろうと。nが小さいからたぶんこういう愚直なやりかたでいけるんだろうなぁと思いました。
piを整数で宣言してしまったり、返り値で整数を宣言していたりで計算が合わず四苦八苦してしまいました。なにも考えずint書くのほんとダメ。ここの実装でものすごく時間使ってしまったのが反省点です（今提出時刻確認したら1時間以上も使ってしまったいた……）。
でも近くの順位の人を見るとだいたいそんな感じなのでこれはそういう問題なのでしょうね。 [a,b]内にある部分の体積計算は同じようなコード書きまくってるし、もっとうまくやれそうな気もしますが、具体的にどうというのは思い浮かびませんね。

const double pi = 3.1415926535;

class cone{
    public:
        double x,r,h;
        bool isIn(double a,double b){
            if(x<=a&&a<=x+h||a<=x&&x<=b){
                return true;
            }else{
                return false;
            }
        }
        double V(){
            return pi*r*r*h/3.0;
        }
        double Vab(double a,double b){
            if(x<=a&&x+h<=b){
                cone small;
                small.h=x+h-a;
                small.r=r*small.h/h;
                return small.V();
            }else if(x<=a&&b<x+h){
                cone small,large;
                small.h=x+h-b;
                small.r=r*small.h/h;
                large.h=x+h-a;
                large.r=r*large.h/h;
                return large.V()-small.V();
            }else if(a<=x&&b<x+h){
                cone small;
                small.h=x+h-b;
                small.r=r*small.h/h;
                return V()-small.V();
            }else{
                return V();
            }
        }
};

int main()
{
    int n,q;
    cin>>n>>q;
    vector<cone> c(n);
    double a,b;
    REP(i,n){
        cin >> c[i].x >> c[i].r >> c[i].h;
    }
    REP(i,q){
        cin>>a>>b;
        double sum=0;
        REP(j,n){
            if(c[j].isIn(a,b)){
                sum+=c[j].Vab(a,b);
            }
        }
        printf("%4f\n",sum);
    }
}

C問題『高橋くんと不思議な道』

問題文を見た瞬間、これはできないやつだと悟りました（時間も少なかったし）。ノードとエッジが出てくる経路系の問題に慣れていなさすぎてちょっと苦手意識を持っているのはよくないですね。DPも含めて意識的に訓練しないとできるようにならなさそうな分野だと思っています。

D問題『9』

問題文開いた時点で残り10分くらいしか時間がなく、部分点だけを狙いにいきましたが失敗。 以下がその時書いたコード

#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
using namespace std;
int main()
{
    long long int k,m;
    cin>>k>>m;
    int c=0;
    REP(i,m){
        int isum=0;
        int j=i;
        while(1){
            isum+=j%10;
            j/=10;
            if(j==0)break;
        }
        if(i%k==isum%k)c++;
    }
    printf("%d\n",c);
}

これREPで書いてしまっているので0スタートになってて間違いだったようです。（forで書いたら10点分は取れました）
マクロ使うのが悪いわけではないと思うのですが、こういうミスをしてしまうとちょっと考えてしまいますね。

ニコニコ超会議の将棋企画

　今日はニコニコ超会議なるものの将棋放送を観ました。斎藤慎太郎六段とAperyがタッグを組んでponanza、nozomi、大樹の枝連合軍と指すという企画から見始めましたが、多数決による合議制がponanza単体よりも強いのかというのは微妙な感じでしたね。興行としては強そうに見せながらほどほどの強さに抑えることができるのでうまい手法なんだろうなと思いました。そうは言っても尋常じゃない強さであろう将棋ソフト連合軍を打ち負かした斎藤六段はやはりプロ棋士、異次元の強さを誇るのだということを改めて感じました。僕自身の棋力は将棋ウォーズでも初段になれないくらいのものなのですが、将棋ソフトが好きなせいでどうしてもプロ棋士の強さを過小評価してしまいがちであるようです。プロ棋士の方々というのは将棋が強いという一点で飯を食っていける恐ろしい人たちなわけで、わざわざ「プロ棋士へのリスペクトを忘れてはならない」と戒めるまでもなく本来ならばその強さを見ただけで自然と尊敬してしまうべきなのでしょう。僕がそうならないのは棋力が低すぎてプロ棋士たちの力を適切に理解できていないからなのだろうなと思います。勝負事が嫌いなので対人戦はあまりしないのですが、プロの凄さをより理解できるようになるという意味で棋力を高めたいですね。

　午前中には飛車と角はどちらが強いのかという企画を行っていたと後になってから知り、悔しさを感じながら番組のページを開いてみたら一般会員で予約してなくてもタイムシフトが見れるらしく、夜も遅くなってから見始めました。もともとはプロパンゴリラさんという人がニコニコ動画に投稿した動画がきっかけとなっていて、僕も氏の動画はほとんどすべて見たことがあるものですから、とうとう竜王と共演するまでになったかと驚きました。（芸のある）一般人が有名な人と同じステージに立てるというのは何かしら素敵なことであるように思います。夢がある時代だと思いますし、それをうまく活かせていない自分がちょっと嫌になったりします。ニコニコ及びニコニコ超会議が良いことばかりとは思いませんが、利用できるものは利用するのが正しいあり方なんでしょうね。企画内容そのものはやはり飛車が自由に動けるのが大きくて、駒組が制限されてしまう角側に対して縦歩取りを見せる急戦、堅く囲える持久戦のどちらでも飛車側が有利なのでしょう。竜王の切れ味鋭い発言が効いていて良い番組でした。

AtCoder Regular Contest 050に参加しました

昨日行われたAtCoder Regular Contest 050に参加しました。
結果はA問題しか解けず、100点の259位でした。200点取れると順位がふた桁以内になるようなので頑張りたいところですね。
以下各問感想

A問題 大文字と小文字

最初A-Zとa-zは数字が続いているものと思っていたので入力をAとaで受け取ったとすると A - a == 26 とすれば判定できるのではないかとか考えていました。やってみると全然違う数字が出てきてしまったので、しばらく悩んだあと諦めて小文字の方にtoupper()を適用して比較しました。解説放送であったとおり A - 'A' == a - 'a' と比較すればスマートにやれたのですね。解説放送のコメントでXORを使うとかもありましたが、よくわからないですしまだそんなことを気にするレベルではないかなという感じもします。

B問題 花束

入力がとあって、の束を個、の束を個作るとすると、できる花束の総数は個となるのでこのを最大化すれば解けるのではないかと考えました。このとき、赤い花による条件は , 青い花による条件はとなり、からを消去すれば


という不等式を両方満たせば良いことになるので、つまりが定まったとき
ということになります。 から まで変化させたときのの最大値を返せばいいのではないかと考えましたが、最大とする を三分探索で求めようと実装していたところで時間が尽きました。この方針でいけるのかわかりませんが実装を速くしないと試せるアイデアが少なくてもどかしいですね。 解説では花束の数を与えれば二分探索で解けるとのこと。二分探索は数式に使える条件が増やせるし関数の返り値はbool型で良いしで、ぜひとも適用できるかどうかを見極める力を身につけたいテクニックですね。

C問題　LCM 111

愚直に処理をプログラム化しただけでは絶対通らないんだろうと思いつつも、ユークリッドの互除法の実装をしたことがなかったのでその練習も兼ねてということで小さいサンプルだけ通るようなものを書いて提出もせずに終了。ユークリッドの互除法は引数の2整数の大小関係を気にしない書き方ができるらしいのですが、いちいち大小関係見てスワップさせながらみたいな実装をしました。こういうところもなんとかしたいですね。書いたコードを他のコンテストで再利用するってどういう方法が最適なのかわからず、とりあえず今は手を動かすことを再優先にやっています。 解説を聞いたあとでも、多分うまく大きい数を関数でバラしていくあたりが実装できないんだろうなと思いました。まぁ慣れればなんとかできるんじゃないかと思いますが。

D問題 Suffix Concat

コンテスト中は問題文を読みすらしてなかったのですが、解説を聞く限りとても難しそうでまだ手の届くものではなさそうだなという感じです。

A問題のタイムアタックみたいな状況からは一歩抜け出したいですね。