SHIINBLOG

AtCoder Beginner Contest 128

はい. AtCoder Beginner Contest 128 です

f:id:zeronosu77108:20190527000245p:plain f:id:zeronosu77108:20190527000304p:plain

今回は酷い. AC になったのは, A と B だけでした(:3」∠)
とりあえず,この2つをまとめておきます.

C以降は勉強して解けたら追記していきます.


A - Apple Pie

問題文
リンゴが 3 つの欠片になるのだから,足して割るだけ.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main(void) {
    int a,p;
    cin >> a >> p;
    cout << (a*3+p)/2 << endl;
}



B - Guidebook

問題文
index 置いてソートするだけ.

#include <iostream>
#include <vector>
#include <utility>
#include <string>
#include <numeric>
#include <algorithm>

using namespace std;


int main(void) {
    long n;
    vector< pair<string, int> > ass;
    cin >> n;

    for (long i=0; i<n; i++) {
        pair<string, int> tmp;
        cin >> tmp.first >> tmp.second;
        ass.push_back(tmp);
    }

    vector<int> index(ass.size());
    iota(index.begin(), index.end(), 0);


    sort(index.begin(),
         index.end(),
             [&](long x, long y){if( ass[x].first != ass[y].first) return ass[x].first<ass[y].first; return ass[x].second>ass[y].second;}
    );

    sort(ass.begin(), ass.end());

    for(auto i: index){
        cout << i+1 << endl;
    }
}





C問題以上は,明日以降にちゃんと考えて解いたら追記します.

AtCoder Beginner Contest 127

はい. AtCoder Beginner Contest 127 です

今回は縛りプレイじゃないです(だからといって順位は高くないです).

f:id:zeronosu77108:20190525231129p:plain


f:id:zeronosu77108:20190525231148p:plain

A - Ferris Wheel

問題文
はい.問題文の通りに実装しました.

#include <iostream>

using namespace std;

int main() {
    int a,b;
    cin >> a >> b;
    if ( a <= 5 ) {
        b = 0;
    } else if ( a <= 12 ) {
        b /= 2;
    }

    cout << b << endl;
}



B - Algae

問題文
for文ぶん回すだけ…?

#include <iostream>

using namespace std;

int main() {
    long long r,d,x;
    cin >> r >> d >> x;
    
    for(long long i=0; i<10; i++) {
        cout << (x=r*x-d) << endl;
    }
}



C - Prison

問題文
Lの最大値と Rの最小値を求めれば良いだろ〜って感じで書いた.
これ,LとRすれ違うこともあるよなぁとか思いつつもそのまま出してしまって WA
即 if文を書き足して AC

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    long long n,m;
    cin >> n >> m;
    long long nmax=-1;
    long long nmin=9999999999;
    for(long long i=0; i<m; i++) {
        long long l,r;
        cin >> l >> r;
        nmax = max(nmax, l);
        nmin = min(nmin, r);
    }

    long long ans = abs(nmin - nmax) + 1;
    if ( nmin < nmax ) {
        ans = 0;
    }
    cout << ans << endl;
}



D - Integer Cards

問題文
ソートして小さい方から書き換えて行けば良いのでは?という感じ.
入れ子vector のソート慣れてなくて時間がかかった.

#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>

using namespace std;

bool compare(vector<long long> i1, vector<long long> i2) 
{ 
    return (i1[1] > i2[1]); 
} 

int main() {
    long long n,m;
    vector<long long> a;
    vector<vector<long long> > bc;
    cin >> n >> m;

    for(long long i=0; i<n; i++) {
        long long tmp;
        cin >> tmp;
        a.push_back(tmp);
    }

    for(long long i=0; i<m; i++) {
        long long tmp;
        vector<long long> vtmp;
        cin >> tmp;
        vtmp.push_back(tmp);
        cin >> tmp;
        vtmp.push_back(tmp);
        bc.push_back(vtmp);
    }
    
    sort(a.begin(), a.end());
    sort(bc.begin(), bc.end(), compare);

    long long i,j;
    i = j = 0;

    while( a[i] < bc[j][1] ) {
        if( bc[j][0] > 0 ) {
            a[i] = bc[j][1];
            i++;
            if( i > n-1 ) {
                break;
            }
            bc[j][0]--;
        } else {
            j++;
            if( j > m-1 ) {
                break;
            }
        }
    }
    long long ans = 0;
    for(long long i=0; i<n; i++) ans += a[i];
    cout << ans << endl;
}



E - Cell Distance

問題文
最初 4C2 とか組み合わせ使うのかな〜って考えてたけど,思いつかなくて一旦 F問題へ.
戻ってきて雑に総当たり書いてみたけど,よく分からず…

#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>

using namespace std;

long long mod = 1000000007;

long long calc(long, long, long, long, long, long );

int main() {
    long n,m,k;
    cin >> n >> m >> k;
    long sum = 0;

    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++ ) {
            sum += calc(n,m,i,j,k,1);
        }
    }
    cout << sum << endl;
}

long long calc(long n, long m, long i, long j, long k, long l) {
    if ( l == k ) {
        return 0;
    }

    long sum = 0;
    for (int ii=i; ii<i; ii++) {
        for (int jj=j+1; jj<j; jj++) {
            sum = (sum + calc(n,m,ii,jj,k,l+1) + abs(ii-jj)) % mod;
            //cout << "sum " << sum << " ";
        }
    }
    //cout << endl;
    //cout << "(" << i << "," << j << ") " << "l : " << l << endl;
    //cout << "sum " << sum << endl;
    //cout << endl;
    return sum;
}



F - Absolute Minima

問題文
何だこの問題は…
a の最小値と a を vector に溜めておいて, 2 が来たら全部絶対値取って足せば良いかな〜とか思ってた.
ダメみたいです.

#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>

using namespace std;


int main() {
    vector<long long> a;
    long amin = 9999999999;
    long n;
    long b = 0;
    cin >> n;
    for (int i=0; i<n; i++) {
        long q;
        cin >> q;
        // cout << "q : " << q << endl;
        if( q == 2 ) {
            long sum = 0;
            for (auto it : a ) {
                sum += abs(amin - it);
            }
            cout << amin << " " << sum + b << endl;
        } else {
            long ta,tb;
            cin >> ta >> tb;
            // cout << "a b : " << ta << " " << tb << endl;
            a.push_back(ta);
            amin = min(amin, ta);
            b += tb;
        }
    }
}





E問題と F問題は解けなかったので,次回までに(と言っても明日なんだけど…)勉強したい(:3」∠)

AtCoder Beginner Contest 126

はい. AtCoder Beginner Contest 126 です

22:00から始めるという縛りプレイでした.

タイムはそんなに悪くないかな… f:id:zeronosu77108:20190519232304p:plain

A - Changing a Character

問題文
k番目の文字を小文字にするやつ.
char型に1文字ずつ読み込んでいって,k番目なら tolower するだけでできた.

#include <iostream>

using namespace std;

int main(void) {
    int n,k;
    char c;
    cin >> n >> k;

    for (int i=1; i<=n; i++) {
        cin >> c;
        if ( k == i ) {
            c = tolower(c);
        }
        cout << c;
    }
    cout << endl;
}



B - YYMM or MMYY

問題文
日付の表記判断.
2桁ずつに別けて, 1 ≦ x ≦ 12 か判断するだけ.

#include <iostream>

using namespace std;


int main(void) {
    string str;
    int i,j;
    cin >> str;
    bool i_f, j_f;
    i_f = j_f = false;

    i = stoi( str.substr(0,2) );
    j = stoi( str.substr(2,2) );

    if ( 0<i && i<=12 ) {
        i_f = true;
    }
    if ( 0<j && j<=12 ) {
        j_f = true;
    }

    if (i_f && j_f) {
        cout << "AMBIGUOUS" << endl;
    } else if ( i_f ) {
        cout << "MMYY" << endl;
    } else if ( j_f ) {
        cout << "YYMM" << endl;
    } else {
        cout << "NA" << endl;
    }
}



C - Dice and Coin

問題文
確率の計算していくだけ.テキトーでいけるかなと思って書いた.

#include <iostream>

using namespace std;

int main(void) {
    long long n,k;
    double ans = 0.0;
    cin >> n >> k;

    for (long long i=1; i<=n; i++) {
        double sum = i;
        double tmp = n;

        while( sum <= k-1 ) {
            sum *= 2.0;
            tmp *= 2.0;
        }
        ans += (1.0 / tmp);
    }

    printf("%.16f\n", ans);
}

すると,サンプルの2と何故か微妙に違う…
時間も無かったので,とりあえずそのまま提出しました.


解説を見るとほぼ同じプログラム…
なんと確率の分母を全部取って割り算ではなく,逐次で /=2 していた.

うーん,そんなに差が出るんか…?

#include <iostream>

using namespace std;

int main(void) {
    long long n,k;
    double ans = 0.0;
    cin >> n >> k;

    for (long long i=1; i<=n; i++) {
        double sum = i;
        double tmp = 1.0 / n;

        while( sum <= k-1 ) {
            sum *= 2.0;
            tmp /= 2.0;
        }
        ans += tmp;
    }

    // cout << ans << endl;
    printf("%.16f\n", ans);
}

2019-05-20 追記
doublelong double にしたら 誤差が 1*10^{-9} 以下になりました.




D - Even Relation

問題文
はい.時間が無くて超雑に書きました.
通るわけ無いですよね.

#include <iostream>

using namespace std;

int main(void) {
    int n;
    int ans[100010];
    bool f[100010];
    for (int i=0; i<10000; i++) {
        f[i] = false; ans[i] = 1;
    }

    int u[100010],v[100010],w[100010];
    
    cin >> n;
    
    for (int i=0; i<n-1; i++) {
        cin >> u[i] >> v[i] >> w[i];
        if (w[i]%2 == 0) {
            f[u[i]-1] = true;
            f[v[i]-1] = true;
        } else {
            if ( ans[u[i]-1] != -1 && ans[v[i]-1] != -1 ) {
                if ( ! f[u[i]-1] ) {
                    ans[u[i]-1] = 0;
                } else if ( ! f[v[i]-1] ) {
                    ans[v[i]-1] = 0;
                } 
            }
        }

    }

    for (int i=0; i<n; i++) {
        cout << ans[i] << endl;
    }
}

とりあえず2点間が偶数なら良いじゃん!っていうアレで書いたんだけど,
雑過ぎました.
しかも,未定義を -1 とした名残の if文が残っている…



圧倒的時間不足により問題文把握,プログラムが雑になってしまった感があります…
次はちゃんと時間作るぞ〜

あ, E問題 と F問題は解けたら上げます.

エンジニアを説明上手にする本を読んだ

エンジニアを説明上手にする本 を読んだ.

わかりやすく説明するために,
分類してラベルをつけて説明する.
使う用語や関心についてターゲットを分析することなどが説明されていた.

プレゼンテーションについても触れており,
ジェスチャーは3秒キープすることや間についての説明などもある.

情報を構造化するパターンについても説明があった.

言っていることはとても分かる.凄く説明が上手くいきそうだと思った.
悪くない.悪くないんだけど…
日本語が頭に入ってこない…

3度くらい読むの挫折しそうになった.

YAPC::Tokyo に参加しました!

目次

  1. なぜ参加しようと思ったか
  2. 当日
    1. 2019年冬のPerl
    2. Perl to Go
    3. ランチ
    4. Perl5の静的解析入門 機械と人間双方の歩み寄りによる平和編
    5. PerlプログラムでPerlプログラムを修正する方法
    6. レガシーPerlビルド 〜現代に蘇るPerl[1..5].0とPerl6〜
  3. その後

なぜ参加しようと思ったか

実は Perl ほとんど知りませんでした.

Perl 入学式に参加したノリでそのまま行ってみるか〜って気分になったのが理由ですね.
Perl 入学式の記事は こちら




当日

寝坊してしまって,オープニングを見逃してしまいました…
着いたのは, 11:40 を超えていたので, 2019年冬のPerl から見始めました.


2019年冬のPerl

Comma IDE の辺りから聞きました.
Perl 6用の IDE が開発進んでるんですね.
Perl 知らないけど, Perl 6 面白そうだなぁとか思っています.

最後の方しか聞けなかったのが残念だったんですが,
紹介にあった Learning Perl 6 を読んでみたいなと思っています.

次は何を見るか迷ったんですが, Golang ほんの少し触った事があったので,
そのまま Perl to Go を見ることにしました.



Perl to Go

Golang は書いたことがあったのですが,
Web API を書いたこともなかったので,あんまり追いつけなかったのが正直なところです…

net/http が便利そうだなぁと思ったので,今度触ってみたいなぁと

「ここにコードを書く と書いてますが書いてませんね」とかあったり,結構笑いました.



ランチ

ランチは,学生支援ということで企業の方の発表を聞き,お話しさせていただきました.
県外の大学生の方ともお話できたので,楽しかったです.



Perl5の静的解析入門 機械と人間双方の歩み寄りによる平和編

静的解析という言葉に惹かれて見に行きました.
Perl 5 での,静的解析ツールはいくつかあるそうなんですが,
Pattern-based Perl Recognizer の紹介をしていました.

なるほど完全に理解したって感じでした.
Perl を書いてみて,使ってみたいなぁという気分になりました.

「これだから Perl は!」 からの
コードの迷いは思考の迷い 一呼吸おいて,もう少し考えようというのは,
面白かったです.



PerlプログラムでPerlプログラムを修正する方法

次もタイトルに惹かれて,このお話を聞きました.
が,当日かなり体調が悪くあまり覚えていません…

「会社にはクソコードいっぱいある」というセリフだけは覚えています.



レガシーPerlビルド 〜現代に蘇るPerl[1..5].0とPerl6〜

学校の後輩ということもありましたが,体調不良の惰性でそのまま聞きました.
Perl って古い方がビルドしやすいのかぁって感じでした.

なぜか Perl 1.0 がメンテされていて,テスト通過率 100% のバージョンが存在するという事実に笑いました.

Perl 1.0 のソース見てみたいなぁと.




その後

本当は懇親会まで参加するつもりだったんですが,
座っているのも辛かったので,帰ってしまいました…

ホテルに戻って体温計を借りたら, 39度近くあったので,そのまま寝ました.

本当に残念だったので,次回にはちゃんと参加したい!
まずは,普段のスクリプトPerl で書いてみようかなぁと思っています.

最後になりますが, YAPC::Tokyo の運営ありがとうございました.
また,学生支援本当にありがとうございました.

次回までには YAPC を 100% 楽しめるように勉強します.

Perl入学式 に 中途入学しました

Perl入学式in沖縄 第4回 〜サブルーチン/正規表現編〜 に参加しました.


あるツールのインターフェースが Perl で書かれていて,読めなかったのと,
いろいろあって少し興味があったので参加してみました.


一応,1回〜3回までの資料を見ながら復習(?)はして行きました.


第4回は,ちょうど分からなかった,@_ の説明とかがあって, 良かったです.


メモ程度にまとめておく(:3」∠)

  • @_ は,サブルーチンの引数がまとめて入った配列
  • $x = shift @_ とか ($x, $y) = @_ したら取り出せる
  • ($x, $y, @array) = @_ とかして 2つはスカラー,後は配列みたいにできる

全体としてはこんな感じ…?

sub func {
    my $x = shift @_;
    print "$x\n";
}

func(10);


これでインターフェースの Perl スクリプト読めるぞ〜

CADDi 2018 for Beginners

CADDi 2018 for Beginners に参加しました.

またもや気付いたら始まっていた…
まぁ,言い訳は置いといて,



結果的には全部解けました.
A → B → D → C の順で解いた.

A - 12/22

問題文はこちら

4桁の整数が与えられて, '2' が何個現れるか求めるもの.

C++ で解いたので, string で受けて,単純に'2'の数を数えた.

#include <iostream>
#include <string>

using namespace std;

int count_char(string s,char x) {
    int count;
    for (auto c : s) {
        if ( c == x ) {
            count++;
        }
    }
    return count;
}

int main(){
    string s;
    cin >> s;
    cout << count_char(s,'2') << endl;
}



B - AtCoder Alloy

問題文
hight と width が与えられて,それ以上の金属板はいくつあるかみたいな問題.

これもすぐに書き終わったかな.

#include <iostream>

using namespace std;

int main(void) {
    int n,h,w;
    int count;

    cin >> n;  cin >> h;  cin >> w;
    for(int i=0; i<n; i++) {
        int a,b;
        cin >> a; cin >> b;
        if( h <= a && w <= b ) {
            count++;
        }
    }
    cout << count << endl;
}



D - Harlequin

一応解いた順番にD問題から.
問題文

交互にリンゴを食べていって,最後のリンゴを食べるのはどちらかっていう問題.


問題を眺めながら紙に書いてたら何か神が降りてきて,

2 で割った余りが全部 0 なら second の人が勝つのでは?
と思って実装してみたら合ってた.

#include <iostream>
#include <string>

using namespace std;

int main(void) {
    int n;
    string winner = "second";
    cin >> n;
    

    for(int i=0; i<n; i++) {
        int a;
        cin >> a;
        if ( a % 2 != 0 ) {
            winner = "first";
        }
    }
    cout << winner << endl;
} 

よく見たら, winner = "first" としている部分で break した方が良いのでは…?



C - Product and GCD

問題文

D 問題解く前に1度見て,ぱっと見思いつかなかったので,一旦放置した問題.

なんとなく素因数分解使えそうだな〜と考えていて,

n個に分解するんだから,素因数分解したときの素数がn個以上あれば,それが最大公約数に含まれるじゃん!
と気付いた.


それで,最初書いたのだけれど,
2*n個以上ある場合を考えていなかったので,
問題によっては,WA(間違い)になってしまった.

全然間違っている理由が分からなくて,
いろいろ変えて提出したので間違いだらけになってしまった.
intlong long にしてみたりとか)

#include <iostream>
#include <unordered_map> 

using namespace std;

std::unordered_map<long long,long long> c;

void decompositPrime(long long n)
{
    long long a = 2;
    while (n >= a * a) {
        if (n % a == 0) {
            n /= a;
            c[a] += 1;
        } else {
            a++;
        }
    }
    c[n]++;
}

int main(void) {
    long long n;
    long long p;
    long long ans=1;
    cin >> n;  cin >> p;
    decompositPrime(p);
    
    for (auto itr = c.begin(); itr != c.end(); itr++) {
        // if ( itr->second >= n ) {
        while ( itr->second >= n ) {
            itr->second -= n;
            ans *= itr->first;
        }
    }
    cout << ans << endl;
}



今回は, Beginners だけど, 267位だったので,
40分ほど遅れてスタートした割りには良い方なんじゃないだろうか.