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分ほど遅れてスタートした割りには良い方なんじゃないだろうか.

初めての競プロ

本日初めて AtCoder Grand Contest 029 に参加しました.

なんだかんだで初めての競プロです.

大学入ってすぐに,何ヶ所か競プロのサイトに登録していたのに
1回も参加した事が無かった…

気付いたときには始まっててちょっと焦った


結果は惨敗でした.
Grand じゃなくて Beginners に参加したかった…


不慣れということと,1回目でタイムアウトが出てしまってとても焦ってしまった.
結局時間内に1問も解けなかった.



落ち込んでいても仕方が無いので,
次のためのお勉強をし(他の人が出した物を読み解き)ます.



A - Irreversible operation

問題文はこちら

「黒白 の並びならひっくり返す」を繰り返して何回ひっくり返せるかという問題.

最初は,1週 「黒白」 をひっくり返しつつ探して,というのを繰り返すプログラムを書いた.
(時間制限が 2sec だったから無理な気はしていた)


次に, string.h の strstr を使ったら早いんじゃないかと使ってみた.
結果は タイムアウト 変わらず…


最後らへんに 「黒白」を見つけたときに,その前の黒を数えたら良いのではないかと考えた.
「黒黒白」 なら 2回ひっくり返せるみたいな.

これ実装して提出したら,いくつか不正解に. タイムアウト ではなくなったものの,何が間違ってるのか分からなくて,
悩んでる間に終了してしまった.


ということで,一番最初に解いていた方のソースコードを参考にする.

まず,準備具合が違いますね.

#define sqr(x) ((x)*(x))

とか

#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)

とか用意している.

求解のアルゴリズム的には, 黒 ならカウントの変数をインクリメントして,白が来たらそれを解用の変数に足すもの.

僕のアルゴリズムの上位互換みたいな感じがする…


確かに 黒 が連続の後に 白 が来た場合,1つずれるだけなので,ひっくり返せる回数は増えていく.


僕が最後に考えていたアルゴリズムは,
黒 を数えつつ 白 に 変えていったけど,最後の 黒 1つだけを 白 にすれば良くて,
ルールを表現できていなかったみたい.



ということで書き直してみたのだけど,これを提出しても タイムアウト

#include <stdlib.h>
#include <stdio.h>

#define BUF_SIZE 200010
int main(void){
    unsigned long long count = 0;
    char s[BUF_SIZE];
    int i;
    int j;
    fgets(s, BUF_SIZE, stdin);
    for(i=0; i<BUF_SIZE; i++) {
        if( s[i] == '\n' || s[i] == '\0') {
            break;
        }
        
        if( s[i] == 'B' && s[i+1] ==  'W' ){
            count++;
            
            for( j = 1;  (i-j) >= 0; j++) {
                if( s[i-j] == 'B') {
                    count++;
                } else {
                    s[i-j+1] = 'W';
                    break;
                }
            }
            
            if( j == 1) {
                s[i] = 'W';
            }
            s[i+1] = 'B';
        }
    }
    printf("%llu",count);
}

やっぱり,こっちアルゴリズムを考えつく必要がありそうだ


次までに,今回の AGC029 の別な問題とか,前の大会の問題を解いて高速に求解できるようにならないといけないなぁと実感した.

親知らず4本 一気に抜歯した

人生初めての入院・全身麻酔が親知らずの抜歯だった.

9/6 くらいに歯茎が腫れて?
噛み合わせると歯に挟まれて痛い状態に…

歯肉炎…?

歯医者さんに行ってみると,

「親知らずのせいで歯茎が腫れてますね〜
 ここでは抜けないので口腔外科行ってくださいね」
とのこと.

3本抜いた方が良いかもと言われた.

口腔外科に行ってみると
「4本ありますが全部抜きますか?」
って言われて,3本じゃ無いのか…って思った.


上下左右に1本ずつ.
下の歯が水平に生えていて,神経もわりと近いらしい
さらに上の歯の片方は上顎洞に貫通しているみたい.

相談した結果
入院して全身麻酔で抜くことになった.
「時間あるなら一気に行った方が楽ですよ〜
 難易度高いので抜く方も全身麻酔の方が気が楽ですし」
って

手術日が 9/26 に決まり,
前日から入院した.


手術自体は,気付いたら終わっていた.

手術室からベッドごと病室に運ばれて,
顔も上がらないし周りも見えない状況で
「抜いた歯こんな感じですよ」って見せられた

僕は「(いや,見えないし…なんなら少し顔上げるのも辛いんだけど…)」って感じだった.

その後は,ひたすら寝ていた.


次の日の朝食は,お粥とか柔らかいものが出てきたけど,
痛い…

血は出ていなかったので,我慢して食べた…

そして,そのままお昼後に退院
状態が悪ければ延びたかもしれないけど, 2泊3日で退院することができた.


家では,お粥とか白和えとか,茶碗蒸しとか食べて生活した.

今日10/6 手術の10日後抜糸をした.


順調に回復しているようで一安心.

だけど,(削ったであろう)アゴがとても痛いので,
しばらくは堅めなもの食べられ無さそうだ…

Julia の勉強をした

The Julia Language を勉強した.

なぜ Julia を作ったか Why We Created Julia

Twitter でこのリンクを見かけて変態な人達がいるな〜と思って
勉強してみた.

We want the speed of C with the dynamism of Ruby.

We want a language that’s homoiconic, with true macros like Lisp, but with obvious, familiar mathematical notation like Matlab.

We want something as usable for general programming as Python, as easy for statistics as R, as natural for string processing as Perl, as powerful for linear algebra as Matlab, as good at gluing programs together as the shell.

って,凄いよね.



早いし書きやすいから,
機械学習とかに使われてたりするみたい
どこ見ても Jupyter Notebook で動かすとか書いててうーん…って思った

とりあえず,

brew install julia

でインストールしてやってみた




最初に読みやすそうな Julia By Example を読んだ

f(x) = x + 1

みたいに関数が定義できたり,

3x
x^2

のように数学記号みたいに書けたりする.
他にも,配列の中に配列が入っているものと,2次元以上の配列(行列?)が区別されていたり,
良さげな感じがした.


これを読んだ後に v1.0.0 が出ていることに気がついた.
ということで, v1.0.0 をインストールして,

github.com を読んでみた.

基本的なことは, Julia By Example とほぼ同じだったかな


09. Julia is fast で他の言語と比べてるけど,とても早い!!

Julia hand-written simd.....3.2
Python numpy................3.5
Julia built-in..............3.5
C...........................9.4
Julia hand-written..........9.5
Python built-in...........673.0
Python hand-written.......791.8



round(value, 1)round(value, digits=1) って書かないといけないけど.


Python の関数を呼び出したりできるのも良さげ.
他の言語も呼び出せるのかな?



後は, 10. Multiple dispatch にあるけど

foo(x::String, y::String) = println("My inputs x and y are both strings!")
foo(x::Int, y::Int) = println("My inputs x and y are both integers!")

みたい書いて,引数・型の異なる同名の関数が定義できるのは良いと思う.
さらに,

foo(x, y) = println("I accept inputs of any type!")

って書いて,その他を受けることができるのもとても良いと思った.




String の replace

Julia By Example では,

relipace(string, pattern, replacement)

という感じで書かれていたけど,実際に書いてみると

ERROR: MethodError: no method matching replace(::String, ::String, ::String)
Closest candidates are:
  replace(::String, ::Pair{#s55,B} where B where #s55<:AbstractChar; count) at strings/util.jl:414
  replace(::String, ::Pair{#s52,B} where B where #s52<:Union{Tuple{Vararg{AbstractChar,N} where N}, Set{#s49} where #s49<:AbstractChar, AbstractArray{#s50,1} where #s50<:AbstractChar}; count) at strings/util.jl:419
  replace(::String, ::Pair; count) at strings/util.jl:423
  ...
Stacktrace:
 [1] top-level scope at none:0

とかエラーが吐かれた.

ドキュメント を読むと
Strings · The Julia Language

replace(s::AbstractString, pat=>r; [count::Integer])

変わってるじゃん!

v1.0.0 で String の置換は,

replace("The Ruby Programming Language", "Ruby" => "Julia")

って書くみたい.

割りと書きやすそうだし,早いみたいだし
普段軽く書くときに使っても良いかもしれない.

Google Fit と Samsung Health を同期する

体重計が壊れたので,どうせなら自動で記録してくれるものが良いと

普段使っているフィットネスアプリ Samsung Health に自動で送れる体重計を探した.

 

 

そうしたらこれが見つかった. 

Xiaomi Mi Smart Scale

思ったよりは安い.

 

いろいろ見ているともっと良さげな RENPHO  が見つかった.

iOS の Health とか Google Fit にデータを送ることができるみたい.

 

だけど, S Health とは連携できないみたい.

Google Fit → S Health はできそうな感じがしたので

 

RENPHO の体重計 を買った.

割りとカッコいい.

f:id:zeronosu77108:20180909141555j:plain

 

充電式だから電池も買う必要が無いし,乗ったら電源が入って,

精度もまぁまぁ良さそう.

 

 

S Health と Google Fit の同期は,

 

Health Sync というアプリがあって,

S Health と Google Fit の同期ができるみたい.

play.google.com

 

S Health はPCから見られないけど

双方向の同期ができるため,歩数とかも同期しておけば

PC から Google Fit を見ることで確認出来そう.

(たぶん PC からは見ないけど)

 

 

RENPHO →  Google Fit → S Health という流れで自動で体重入力できるようになった.

 

これで毎朝手動で入力する必要がなくなった!

 

学びを結果に変えるアウトプット大全 を読んだ

学びを結果に変えるアウトプット大全|サンクチュアリ出版 を読んだ.

 

今までビジネス書とか自己啓発みたいな本は読んでこなかった.

理由はそういう話って「それはあなただったからできたのでは?」

って思う事が多かった.

 

 

この本はタイトルからなんとなく気になった.

 

IT系の人は何かとアウトプットしているイメージがあったし,

今まで僕はアウトプットしてこなかった.

というか避けていた.

 

なんとなく「アウトプットしたい」とは考えていた.

それもあって即決で購入した.

 

読み始めると面白くて,半分くらいは時間を忘れて一気に読んでしまった.

 

至極真っ当なことが書かれていて,共感できることが多かった.

きちんと引用元,参考が書かれていて情報を確かめられるのも良い.

 

 

アウトプットする気満々で,

こんな感じでブックダーツを大量に挟みながら読んでいた.

f:id:zeronosu77108:20180909001628j:plain

 

 

アウトプットするための時間を作る方法から書いており,

心の中でとてもうなずきながら読んでいた.

 

 

CHAPTER4 で「圧倒的に結果を出す人の行動力」について書かれている.

その中で「やる気が出たら始めよう」 はいつまでもやる気が出ないとあった.

 

まず始める.5分やってみる.

をやってみようと思う.

 

 

後は,30点を目指して原稿を書くと言うのも良いと思った.

とりあえず完成させる,それから完成度を上げる.

初心者は,完成と直し を 8:2 くらいにしがちだが,

熟練者はまずは完成させて,直しに十分時間を使う. その比率は 5:5 くらい.

 

確かに,自分が書いた文章などは見直す度にミスが見つかる.

1回で完璧に書き上げるようとするよりも,直しに時間をかけた方が良さそうだ.

 

 

 

また,1回1時間,週2回の有酸素運動が脳を活性化させるらしい.

最近は,よく1時間くらいの散歩をする.

 

これを続けていきたいと思う.

 

 

 

毎日朝にTODOリストを作ることで,1日の流れが確認できるとあったが

TODOリストとして書き出す利点がまだよく分からない.

 

期限付きの課題ややるべき事は Reminders で管理している.

 

朝に作る時間が取れるか微妙だと思った.

作れなかったときに,そのまま辞めてしまいそう.

 

TODOリストを実践するかは,もう少し検討しようと思った.

 

 

全体として,とても良い本だったと思った.

続けることが大切ともあったので,これからアウトプットを続けたいと思う.

Python で ナップサック問題 を 総当たりで解く

Python3 でナップサック問題を総当たりで解くプログラムを書く機会があったので.

ナップサック問題総当たり

ナップサックに入れるか入れないかを2進数で判断している. 入れるなら 1 , 入れないなら 0 となる.

品物が15だとしたら,15ビットの2進数だと考えられる.
そこで,10進数の「0〜32767」 までを調べる.
2進数では 000000000000000 〜 111111111111111

それで,全ての組み合わせを求めることができる.