ABC125 C GCD on BalckBoard

i 番目の要素だけを除いた全体のGCDを求めるという愚直な案を書いて当然TLEだったので供養。

def gcd(x, y):
    xx = 0; yy = 0
    if x >= y:
        xx = x; yy = y
    else:
        xx = y; yy = x
    while yy > 0:
        xx, yy = yy, xx%yy
    return xx


def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    ans = 1
    for i in range(n):
        tmp = -1
        for j in range(n):
            if j == i:
                continue
            if tmp == -1:
                tmp = a[j]
            tmp = gcd(tmp, a[j])
        ans = max(ans, tmp)
    print(ans)


if __name__ == '__main__':
    main()

ユークリッドの互除法の計算量がO(log(min(A,B))なので、これだとO(n2log(min(A,B))となってTLE。

解答を見ると、結合則を使って、左右のを求めて、最後に計算。といった具合だろうか。

def gcd(x, y):
    xx = 0; yy = 0
    if x >= y:
        xx = x; yy = y
    else:
        xx = y; yy = x
    while yy > 0:
        xx, yy = yy, xx%yy
    return xx


def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    ans = 1
    # gcd の結合則を利用する(X, Y, Zがありgcd(gcd(x,y),z)==gcd(x,gcd(x, y)))
    l = [0 for i in range(n)]
    r = [0 for i in range(n+1)]
    for i in range(n-1):
        l[i+1] = gcd(l[i], a[i])
    for i in range(n-1, -1, -1):
        r[i] = gcd(r[i+1],a[i])
    for i in range(n):
        ans = max(ans, gcd(l[i], r[i+1]))
    print(ans)


if __name__ == '__main__':
    main()

これでAC出た。 結合則を用いて左右から計算していく発想は出なかったなぁ。

vue cli と webpack

vueの勉強。

バージョン

% vue -V                                                                             
3.7.0

vue create で作ったプロジェクトにvue-routerのサンプルを入れたらうごかねぇ。

エラーメッセージ

[Vue warn]: You are using the runtime-only build of Vue where the template compiler is not available. Either pre-compile the templates into render functions, or use the compiler-included build.

ドキュメントでいう完全(コンパイラ+ランタイム)のがビルドされていないらしい。

公式にはどこに書けばいいのか書いてなかった。

正解は、ルートのvue.config.jsに以下を追加。

module.exports = {
    configureWebpack: {
      resolve: {
        alias: {
          'vue$': 'vue/dist/vue.esm.js'
        }
      }
    }
}

webpack.config.jsに書いてもダメだったし、色々ダメだった。githubのissueに書いてあった。

ディレクトリ構成は以下

% tree -I node_modules
.
├── README.md
├── babel.config.js
├── package-lock.json
├── package.json
├── public
│   ├── favicon.ico
│   └── index.html
├── src
│   ├── App.vue
│   ├── assets
│   │   └── logo.png
│   ├── components
│   │   └── HelloWorld.vue
│   └── main.js
└── vue.config.js

tkinterのTextのサンプル

もう平成も終わって令和になりますね。平和な世界になってくれるといいです。 tkinterの本読んでます。

www.amazon.co.jp

これですね。

tkinterのTextのサンプルです。無かったので書いてみました。

from tkinter import *
from tkinter import ttk


root = Tk()

"""
wrapはデフォはNone、選択肢は'char', 'word'です。日本語だとやっぱcharを多用しそうですね。
gridで自動拡張してるので、width, heightはあまり意味ないですね。
TextはStringVarと強調して動けません(仕様)普通に使いにくいですね。改善の余地がありそうです。
getの他に,insert, index, stringで修正、取り出すことができるようです。
"""
text = Text(root, wrap='char', width=10, height=4)
scroll = Scrollbar(root, orient=VERTICAL, command=text.yview)
text['yscrollcommand'] = scroll.set
text.grid(row=0, column=0, sticky=(N, W, E, S))
scroll.grid(row=0, column=1, sticky=(N, W, E, S))
button = Button(root, text='print', command=lambda x=None: print(text.get(1.0, 'end')))
button.grid(row=1, column=1)
# weightの設定
root.grid_columnconfigure(0, weight=1)
root.grid_rowconfigure(0, weight=1)
root.mainloop()

そもそもTextで日本語使えないっていうねw ワロタ

追記

import tkinter.font as tkFont

root = Tk()
customFont = tkFont.Font(family='arial', size=17)
content_text = Text(root, font=customFont, width=20, height=4)

これでフォント設定すればいける✋

スタートゥインクルプリキュア

最近、ブログの更新がなかったので、書こうかなって思いました。

最近は、tkinterとか、競プロとか、ディスクリートトランジスタアンプとか勉強してるんですけど、集中してるからか、ブログ書く気力がないんですよね。今まで、集中してなかったかって聞かれると、あれなんですけど。

閑話休題的に記事書きます💪

スタートゥインクルプリキュア、今年のプリキュアですね。前作のハグっとプリキュアに、負けず劣らず、面白いと思っています、僕は。

コンセプトがしっかりしてると思うので、大人な人が見ても、ふふって笑いながら観れると思います。

個人的に、対象年齢層が上がっているように感じます。コンセプトが宇宙・科学なので、しょうがない気がしますが、これはいい傾向だと思います。

少女アニメの難しさって、言い回し(単語)や、言動な部分があると思います。

スタプリは、言い回しが明らかに幼稚園児とか小学校低学年向けじゃないなと感じます。一方、言動は、謝る、感謝を述べるという動作などにしっかり演出があってとてもいいと感じています。
基本的な礼儀を抑えつつ、新しい知識を与えるきっかけを作るアニメこそ、少年少女向けのあるべきアニメの姿だと思います。

けもフレ(1期)とかもそんなイメージがあって、娘や息子がいたら、一緒に観たいなと思いました。いませんけど。できる予定もできる予兆もありませんけど。

あとは、僕が好きな分野がっていうのは、ありますね。勉強とか、物理化学分野好きですし、SFものの小説とかも結構好きなんですよね。

スタートゥインクルプリキュア、今後の展開に期待してます。

カリー化された関数

qiitaの週間ランキング?の上位に、カリー化された関数の話が出ていたけど、分かりにくいなぁと思ったので、自分なりに記事を書いてみる。

ちなみにカリー化された関数は英語訳するとcurried functionになる。

Standard ML of New Jersey という言語がある。その言語は、メジャーな言語と比べるとなんか癖が強いと思うけど、言語として、いろんな特徴が実装されているように思える。その 1 つにカリー化がある。

smlnjをインストールすると、インタープリタが実行できるようになる。

% sml
Standard ML of New Jersey v110.85 [built: Sat Dec 22 16:51:02 2018]
- val a: int = 2 + 3;
val a = 5 : int

例えばこんな風に。

関数の定義は、

- fun add a b: int = a + b;

こういう構文になる。

呼び出しはこう。

- add 2 4;
val it = 6 : int

ところで、smlnjは、静的な型付言語で、関数を定義すると、型が出力される。

- fun increment (a:int) : int = a+1;
val increment = fn : int -> int

この場合、incrementという変数に、ラムダ式を代入したような、表記が出力されており、int型の引数を渡すとint型の値が帰ってくるようなのが書かれているのがわかると思う。

引数が増えると、どうなるのか予想して見て欲しい。 最初、僕は

- fun add a b: int = a + b;
val add = fn : int, int -> int

こうかと思ってた。でも、違った。

- fun add a b: int = a + b;
val add = fn : int -> int -> int

実際はこうだった。 int -> int -> int は、わかりやすく書くと、int -> (int -> int)のことで、これは、実際に、1 つの引数でも呼べることを意味している。

- val add2 = add 3;
val add2 = fn : int -> int

これを宣言しておくと、

- add2 5;
val it = 8 : int
- add2 19;
val it = 22 : int

こんな風な呼び出しができるようになる。つまり、部分適用ができるようになる。

もちろん、僕が最初に思ったような書き方もできる。

- fun add (a,b) = a+b;
val add = fn : int * int -> int

タプル(tuple)を使用すると最初に思ったような関数を宣言することができる。

こんな風に、部分的な動作をする関数を返すことができる関数をキャリー化された関数というらしい。

正確には、wikiとかをみると、写像とかの詳しい話が出ていて、部分適用が行いやすくなるという程度にとどまっている。

wikiを読むと、カリー化と部分適用を混同するなよって書いてある。

部分適用は、あくまで、add(3)でも呼べるようにすることで、カリー化は、add(x)とした時の動作を規定することって書いてある(ように感じた)。

pythonでのファイルサイズの取得

os.path.getsize(path)を使えばいいらしい。

ファイルサイズ出力のスクリプト作った。

""" print_size.py """
import os
import sys

if __name__ == '__main__':
    try:
        size = os.path.getsize(sys.argv[1])
        f = ""
        if 10**3 <= size < 10**6:
            f = f"{size//10**3: 4} kB"
        elif 10**6 <= size < 10**9:
            f = f"{size//10**6: 4} MB"
        elif 10**9 <= size < 10**12:
            f = f"{size//10**9: 4} GB"
        elif 10**12 <= size < 10**15:
            f = f"{size//10**12: 4} TB"
        else:
            f = f"{size: 4} B"
        print(f)
    except OSError:
        print("The file doesn't exit.", file=sys.stderr)
    except:
        print("USAGE: print_size.py path", file=sys.stderr)
% for i in `ls`;                                                                      
for> python ../print_size.py ${i}
 640 B
  47 B
  79 B
  11 kB
  21 kB
   1 MB
   1 MB
   1 MB
  31 kB
   3 MB
  22 kB
   1 MB
   3 MB
   6 MB
 597 kB

すぐ作った割に使えるので、載せずにはいられなかったw

smlnjの中値演算子のやつ

タイガーブックやってたら、中値演算子を定義するものが見つかったので、試してみた。

Standard ML of New Jersey v110.85 [built: Sat Dec 22 16:51:02 2018]
- (* 演算子 plus を定義 *)
- infix 6 plus;
infix 6 plus
- (* 演算子 plus2 を定義 *)
- infix 8 plus2;
infix 8 plus2
- (* 演算子の振る舞いの定義 *)
- fun x plus y = x + y;
val plus = fn : int * int -> int
- fun x plus2 y = x + y;
val plus2 = fn : int * int -> int
- 2 * 3 plus 4;
val it = 10 : int
- 2 * 3 plus2 4;
val it = 14 : int

plus2は*(結合度6)よりも高く設定してあるので、2 * 3 plus2 4 は2 * (3 + 4)として計算される。infixは左結合の演算子の定義らしいので、右結合の場合は、infixrを使えばいいみたい。右結合というのは、例えば、a = b = c;という文があった場合、多くの言語でb = cが先に実行されるでしょう?それ。

- (* 仮の代入演算子 equal の設定 *);
- infixr 4 equal;
infixr 4 equal
- fun a equal b = (
= print (a^"に"^b^"を代入したとする\n");
= b);
- "a" equal "b" equal "c" equal "3";
cに3を代入したとする
bに3を代入したとする
aに3を代入したとする
val it = "3" : string
- (* 左結合バージョン *)
- infix 4 equal2;
infix 4 equal2
- fun x equal2 y = (
= print (x^"から"^y^"\n");
= x);
val equal2 = fn : string * string -> string
- "2" equal2 "a" equal2 "b";
2からa
2からb
val it = "2" : string

ということになる。