SHIINBLOG

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

初めての競プロ

本日初めて 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 の別な問題とか,前の大会の問題を解いて高速に求解できるようにならないといけないなぁと実感した.

楽しい楽しい SAT符号化

琉大情報工学科(知能情報コース) Advent Calendar 2018 10日目の記事です.

SAT 符号化についてまとめているところが無くて,とても苦労したのでまとめておく.

SAT符号化とは,制約充足問題や制約最適化問題などを SAT 問題(充足可能性問題:Satisfiability Problem)に変換することである.

近年, SAT問題を解く SATソルバーは高速になっている.
そのため,制約充足問題専用のソルバーを使用するより, SAT符号化を行い SATソルバー*1を使用した方が高速に解くことができる場合がある.
まず, SAT問題について説明する.

SAT問題

SAT問題(Satisfiability)は,与えられた命題論理式または関数が充足可能(SAT)であえるか,充足不能(UNSAT)であるかを判定する問題である.

充足可能とは,命題論理式の命題変数に対し,T または F を割り当てて,式全体が T となる割り当てが少なくとも1つ存在することを言う.

例えば,f=( A ∨ B) ∧ (¬ A ∨ B) ∧ (A ∨ ¬ B) という関数は,以下に示すように A = TB = T の時に関数f が真となる.つまり,関数f は充足可能である.

A B f
T T T
T F F
F T F
F F F

充足不能な例は, A ∧ ¬A などである.A ∧ ¬A は,A に T,F どちらを割り当てても式全体は F となる.


ハードウェアやソフトウェアの検証,制約充足問題,スケジューリング問題などの問題を SAT問題に置き換えることができる.そのため, SAT問題を解くアルゴリズムが研究されてきた. それにより,近年 SATソルバーの性能が向上し非常に高速に SAT問題が解けるようになった.

そこで,制約充足問題などを SAT問題へ符号化し, SATソルバーで解を求める SAT符号化の研究もされるようになった.

SAT問題は,連言標準形(Conjunctive Normal Form: CNF)の論理式を与えられることが多い. CNF は,節の連言(∧)であり,節はリテラル(命題変数またはその否定)の選言(∨)である. 具体例としては,上で出てくる ( A ∨ B) ∧ (¬ A ∨ B) ∧ (A ∨ ¬ B) などである.

これ以降は,連言を省略して節を並べて表記する.


SAT符号化

SAT符号化は,直接符号化法順序符号化法,対数符号化法 などが提案されている*2



直接符号化法

x = 0 を表す命題変数p(x=0) を導入する.

x が 0 から 4 の範囲を取る場合(x ∈ [0,4]),
p(x=0) から p(x=4) までを導入する. x は 0 から 4 のどれかの値を取るため,次のような式をたてる.

p(x=0) ∨ p(x=1) ∨ p(x=2) ∨ p(x=3) ∨ p(x=4)

これで,0 から 4 のどれかであるという命題変数が真となる必要がある. at-least-one 節と呼ばれるもの.少なくとも1つを満たす必要がある.

また,0 から 4 が同時に成り立つことは無いため,排他になるようにする.

¬p(x=0) ∨ ¬p(x=1)
¬p(x=0) ∨ ¬p(x=2)
¬p(x=0) ∨ ¬p(x=3)
        ⋮
¬p(x=2) ∨ ¬p(x=3)
¬p(x=2) ∨ ¬p(x=4)
¬p(x=3) ∨ ¬p(x=4)

こんな感じ これは,A → B(A ならば B) の変形 ¬A ∨ B と考えることができる. p(x=0) ならば ¬p(x=1) である.
これが, at-most-one 節と呼ばれるもの.最大で1つのみが真となる.


他に x ≦ 2 などの制約がある場合,その制約に違反する点をあげる.

¬p(x=3)
¬p(x=4)

となる.

x ∈ [0,4] と x ≦ 2 を符号化したものを全て SATソルバーに与えると, SAT であるという答えと一緒に

p(x=0) ¬p(x=1) ¬p(x=2) ¬p(x=3) ¬p(x=4)

など SAT な解の1つを返してくれる.

x+1 ≦ y なども,違反点をあげていけば符号化できる.

¬p(y=1) ∨ ¬p(x=1)
¬p(y=1) ∨ ¬p(x=2)
       ⋮

という感じ. p(y=1) ならば ¬p(x=1) (y=1 のとき, x=1 なら x+1 ≦ y が成り立たないので) y=2 のときなども全部違反点を上げるため節がとても多くなる…



順序符号化法

x ≦ 0 を表す命題変数p(x≦0) を導入する.

同じように x ∈ [0,4] を表すと,

¬p(x≦0) ∨ p(x≦1)
¬p(x≦1) ∨ p(x≦2)
¬p(x≦2) ∨ p(x≦3)

という感じ. p(x≦4) は常に真となるので,不要.

この命題変数の真理値表を書くと,数が表現できていることが分かる.

p(x≦0) p(x≦1) p(x≦2) p(x≦3) x
F F F F 4
F F F T 3
F F T T 2
F T T T 1
T T T T 0

命題変数の組み合わせは上の表しかなく, x の値を判断できる.

こちらは,直接符号化法の at-least-one 節や, at-most-one 節は,不要で, 節数も少なく表現できる.


x ≦ 2 などは違反する範囲をあげれば良い.

¬p(x≦3)

直接符号化法は違反点をあげるのに対し,順序符号化法は違反範囲をあげるため, 線形制約は簡単に符号化ができる.


x+1 ≦ y は少しだけ複雑になる.

y=1 のとき,p(y≦0) が偽,p(y≦1) が真となるので,
y=1 は, ¬p(y≦0) ∧ p(y≦1) である.

つまり,(¬p(y≦0) ∧ p(y≦1))→ p(x≦0)(y=1 ならば, x は 0 以下である)という形になって,
A→B = ¬A ∨ B の変形とド・モルガンを適用して変形すると,p(y≦0) ∨ ¬p(y≦1) ∨ p(x≦0) となる.

y=1 のときは,恩恵が微妙だけど, y=3 のときなどは,
p(y≦2) ∨ ¬p(y≦3) ∨ p(x≦2) だけで違反する範囲をあげることができるので,
少ない節数で表現できる.



対数符号化法

x や y などの変数を2進表記で考える符号化である.
{ \displaystyle
x = (x_2, x_1,x_0)_2
} として表現する.

x ∈ [0,4] は,違反するビットを否定する.
¬{ \displaystyle x_2} ∨ ¬{ \displaystyle x_0}
¬{ \displaystyle x_2} ∨ ¬{ \displaystyle x_1}

こんな感じで, 5(101)や6(110),7(111)が現れないようにする.

全て偽の場合は,0 となるので,こちらも at-least-one 節や, at-most-one 節と呼ばれるものはない.


x ≦ 2 なんかは,上と同じように違反するビットを否定すれば良い.
¬{ \displaystyle x_2}
¬{ \displaystyle x_1} ∨ ¬{ \displaystyle x_0}



この程度なら良いのだけど,
( x+5 ≦ y ) ∨ ( y+8 ≦ x) みたいなやつがたくさんあると,
対数符号化法 上手くいかない…
辛い…


誰かこの記事見て面白いと思った人一緒に考えてくれ〜〜〜 @e145755 リプライ待ってます_(:3」∠)_

論理学も勉強中なので,一緒に勉強してくれる人居たら声かけて_(:3」∠)_

親知らず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 という流れで自動で体重入力できるようになった.

 

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