ABC119 ただの感想

どーもーーー昨日はABCでした。

待機。３完したいけど、今日はCを解ける自信がない。根拠のない自信のなさ

— 寺/django,vuejs (@mktrdbg) 2019年2月24日

開始前のツイートですが、見事に不安が的中し、ABのみの2完となってしまいました。。

勉強が全然足りてない！

Cはすごい悔しかったなぁ。。

てなわけで各問題感想文

A:
日付は文字列のまま比較できるとのこと。
でも普通にsplitして月と日を比べましたw
4月は31がないらしいので、月だけ比べれば良いものの、語呂合わせ覚えてなかったのもあったし不安だったので一応日も比べるというアホさw

全く関係ない話ですが、なんたら侍の語呂合わせを覚えたのは、中3で通っていた塾でした。
かなり遅いですね。。

B:
いつも思うのですが、コンテストに参加したら最後に解いていた問題以外記憶から削除されてますw
このデータ構造は？

問題自体は範囲も狭いので普通に足しました。

C:
涙のC。

決しててんで分からないというわけではなかった。しかし解けない。これが恐ろしい。

まず、範囲が3から8ということで、適当に全パターン探れば行けるだろうというところまでは分かった。

しかし、あまり全探索になれていないのもあり、ちょっとほかの方法を探してしまった。

そしてたどり着いたのが、目指す値の一つ目に、全組み合わせを試して一番消費MPが低いものを選ぶ。それを2つめ、3つめにも繰り返し行う、
という謎のアルゴリズム。

実際にはもう少しぐちゃぐちゃした実装をしましたが、通らず。

で、結局模範解答はdfsとかで全探索しているものの、これって8重ループが正義では？と思い以下になりました。

（モバイルなのでインデントが糞）

N, A, B, C = map(int, input().split())
takes = []
for i in range(N):
takes.append(int(input()))
takes = takes+[0,0,0,0,0,0,0]
takes = takes[:8]
g = [A, B, C]
combis = []
for i in range(4):
for j in range(4):
for k in range(4):
for l in range(4):
for m in range(4):
for n in range(4):
for o in range(4):
for p in range(4):
combis.append([i,j,k,l,m,n,o,p])
min_diff = 10**10
for combi in combis:
A,B,C = 0,0,0
for idx, el in enumerate(combi):
if el == 0:
A += takes[idx]
elif el == 1:
B += takes[idx]
elif el == 2:
C += takes[idx]
if A == 0 or B == 0 or C == 0:
continue
A_diff = abs(g[0] - A) + (len([_ for _ in combi if _ == 0]) - 1)*10
B_diff = abs(g[1] - B) + (len([_ for _ in combi if _ == 1]) - 1)*10
C_diff = abs(g[2] - C) + (len([_ for _ in combi if _ == 2]) - 1)*10
diff = A_diff + B_diff + C_diff
min_diff = min(diff, min_diff)
print(min_diff)

教訓は、値が小さければとにかく全探索を考える。
そのためにdfsになれる。
さもなくば、forをめっちゃ書こう、ということ。

D:
Cやってる途中に、もしやこれDが簡単なパターンでは？と思い見てみたら、おお、これは行けそう、と思い手をつけるも途中でやっぱ俺に解けるはずない、と思いやめるという愚行。

こちらはまた解いてみたいと思います。

とにかく、レーティングは上がりました。

レーティング更新された。なぜかBまでしか解けなかったのにCまで解いた前回よりパフォーマンスが高く、518->623まで上がった。

救われた気持ちで一杯です。

もう７回も参加したのか。。早い。。#AtCoder pic.twitter.com/LCosCcZNqK

— 寺/django,vuejs (@mktrdbg) 2019年2月24日

次回までにもっと勉強したい。

蟻本のデータ構造のところ、さっぱり分からん。問題がなさすぎて。。

ABC114 C問題感想を述べるだけ

どうもーーーーーー

皆様におかれましてはこの乾燥の季節、肌も鼻もカサカサのことと存じ上げます。

鼻がマジで死んでます。

おそらく次ぐらいでAtCoderの問題で、鼻に石を詰める問題が出てくる予感がします。

そんなことはさておき、とりあえず解いた問題の感想を書きたいと思います。

今回のターゲットはABC114
atcoder.jp

A:
単純に実装

B:
こちらも制限が非常に狭い値なので、普通に見ていけば良いと思いました。
以下解答です。
（ちなみに上のテンプレ部分は初めてコンテストが終わった後、入力とかみんなどうやっとんー、って思って
pythonで一番強そうな人のを拝借して以降、毎回使わせていただいてます。。）

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools


sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]


def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    S = input()

    # 10文字までしかないので、一個ずつ見ていっても良いのでは
    result = 10**10
    for i in range(0, len(S) - 2):
        result = min(abs(753 - int(S[i:i+3])), result)

    print(result)


main()

C:

この回のCはちょっと難しかったですねー。
普通にリアルタイムでやってたら時間足りなかっただろうなー。
怖いこわい。

まず値がでかい。
Nが10**10まである。
試しに実直にやろうと思って、
[i for i in range(10**10)]
とかやると全然無理で、10**7ぐらいでようやく処理できるレベルでした（たしか

というわけで、一筋縄ではいかないと思い、別の策を考えました。

重複組合せがー、とか、一旦7にしてみよう？とか、さまよったあげく、
結果、桁数に着目しようと思いました。
10桁の場合に、各桁で3 or 5 or 7を選んで入れて、3 and 5 and 7が入っていなければそれを引くというイメージでした。
場合の数としては3**10なので、60000程度。
全然大丈夫そうです。

問題はどうやって全桁分回すか。

こういうのはループでは意外に思ったように回せず。

そこで初めて競プロらしいことをできました。

蟻本で最初に出てくるdfs。

再帰本当に嫌いなのですが、なんとか自力でdfsを作ることができ、見事解答することができました。

こちらは何回かやってきれいにした解答

def main():
    global result, S
    S = int(input())
    result = 0
    bfs(0, '')
    print(result)


def bfs(i, s):
    global result, S
    if s != '' and int(s) <= S and len(set(s)) == 3:
        result += 1
    if i == len(str(S)):
        return
    i += 1
    bfs(i, s + '3')
    bfs(i, s + '5')
    bfs(i, s + '7')


if __name__ == '__main__':
    main()

あー、学んだことをようやく実践できた、という喜び。

とか言って今頃これ深さ優先探索なのに関数名がbfsってことに気づきましたw
てかこれちゃんとdfsと呼べる代物なのか？

生兵法は大怪我のもと
悪貨は良貨を駆逐する
毒を食らわば皿まで

気をつけたいですね。

最近競プロを始めました & ABC 118(2/16)の感想

どうもーーーーー

最近は日中はpythonとjsをカタカタしながら、一方で自分のプロダクトをリリースすべく、家でカタカタして引きこもりまくっていたのですが、
最近競プロをはじめました。（引きこもり促進）

atcoder.jp

まあ今さらこんなCとかもやったことないクソ雑魚文系出のエンジニアがアルゴリズムとかなんとかをやるのもナーと思ったのですが、
少しでも強くなるために、勉強中でございます。

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

これが有名な蟻本

さて、１月に始めて６回コンテストに参加し、茶色コーダーになることができました。

今年中に緑かその上の水色までは行く所存！

まあ自分の実力を上げるという意味もあるし、測るという意味もあるし、趣味という意味もある。

工学部系の学生さんも多く、さすがだなーと思います。

最近本当に自分の老けを感じる。
関わったり見たりする人の年齢層が低いというのもあるかもしれない。
そして体重が半年前52付近->60まで上がったのもあるかもしれない。
25歳にして老害の雰囲気を醸し出し始めている。

新元号は老で良いよもう。
超絶高齢化社会だしちょうどいいでしょう。

てか体重急に増え過ぎだろ。
今までクソ雑魚ガリヒョロ非力エンジニアだったのが
クソ雑魚ガリ非力エンジニアになったわ。

とりあえず、昨日のコンテストの感想でも書くか。
（競プロerがtwitterでA:-, B:-みたいなのをやってるのに憧れた）
とりあえずABCの3完でした。
Dは勉強中のdpということで、全然歯が立たず1時間を費やしました。

atcoder.jp

A: 実直に実装
B: カツサンドくんはオムライスが好きです（混乱）

result = 0
for i in KA[0][1:]:
 if all([i in j[1:] for j in KA]):
   result += 1

全員が好きと言っている食べ物をカウントしたいとのことなので、一人目が好きだと言った食べ物の中で、他の人全員が好きだと言っているものをカウントしました。

好きな食べ物が一番少ない人の食べ物についてループとかにしたほうがいいのか？
まあ、N, M<= 30だし、これも実直に実装すればできますね。

C: 最大公約数？考えてもなかった。。
まず、モンスターの体力を降順にソートしました。
最初は単純に体力最大のモンスターからその次に体力が大きいモンスターの体力を引き、
引けなくなるまで繰り返し、それを最後の要素まで繰り返そうかと思ったのですが、10000体のモンスターで、しかも体力が10億まであるとのことで、
到底時間制限におさまらないということで、引くのではなく余りを求めようと思いました。
まず、同じ体力のモンスターは2体いても変わらないということで、set()をしました。
例えば
10 10 10 3 3 2
という体力の組み合わせがあった場合、10の体力の3匹のモンスターを戦わせると最終的に1匹だけ残ります。
ですから、setで余計なモンスターを抹殺します。

そうするとモンスターは
10 3 2
というようになります。
ここから最大から最小を引いてを繰り返すと
10 3 2
7 3 2
4 3 2
1 3 2
というふうに遷移します。
これは引き算をせずとも、余りを利用すれば一度で計算できそうだと思いました。

ですので、各要素を一つ次の要素で割った余りにしていこうと考えました。
すると
1 1 2（最後の要素はそのままにした）
となり
さらにset()してsortすると
2 1
になり、同じく余りを求めると
1 1になり
set() & sort()で
1になります。
（リスト内に1が出た瞬間解答は1になるか）

リスト内のモンスターが1匹になったら、そのモンスターの体力を出力して終了としました。
あと、ループするたびに0の要素は取り除かないと、0除算のエラーが出てしまいます。
set() & sort()しているので、リストの一番最後のモンスターが0かどうかを調べ、取り除くことにしました。

python3でやりましたが、set()しないと計算が間に合いませんでした。（これで1ペナ）

まあこんなような感じで実直に解いたので、解説やtwitterで最大公約数がどうたらというのを見て得も言われぬ気持ちになりました。
正攻法ではないので、計算時間とかは悪いのでしょう。

atcoder.jp
今回の解答は、whileループを使い、毎回全要素を次の要素で割った余りを求めてかつset()しているので、いまいち計算時間がわかりません。
てか、蟻本難しすぎだろｗ（唐突）
計算時間の出し方、いつも困ります。

まあまだまだアルゴリズムに関して勉強が足りていないので、どうしても実直な解答ばかりになってしまい競プロ感が出ないのですが、
そのうちデータ構造などもしっかり勉強して、ヒープがどうの木構造がどうの云々言いながら競プロをしていきたいと思います。

atcoderなどは情報系や少なくとも理系の方が多いと思いますが、（今更文理の分別など意味もないのですが）
私のようなアルゴリズムとかをあんまりやってきていない系エンジニアなら、大体実直に解けるCまで解ければいいのではと個人的に思いました。
（実直に解けるとかいいつつ解説を無視した解答を提出しまくっているのは置いておいて）
Dとかは、DPなど解法を知らぬと解けない問題が多い感じがするためです。
ABCのCまではプログラムを書く力を、Dはアルゴリズムの力を測られていることが多いような気がします。

もっと勉強して、いつかABC全完してみたいものです。

初心者向けjavascriptのPromise, await, async等の使い方

 どうもーーー

たまに投稿すると見せかけて急に技術的なことを適当に書きます。

その前に、最近といえば、9月に転職し、辞めて10月からなんちゃってフリーランスとしてdjangoやvuejsなどをやらせてもらっております。

プログラミングを始めたのが、2年ちょっと前で、今までchatbotの開発がメインでしたが、なんとかwebの開発にも貢献できています。（もちろん至らぬ所だらけ）

pythonはchatbot開発に使用していたので、djangoは文法という意味では苦労しなかったですが、フレームワークの仕組みになれるのはちょっと難しかったです。

jsは今までフロントを一切作ってこなかったため、本当に初めての状態で現場に入らせてもらいましたが、vuejsを含めだいぶ扱えるようになってきました。（もちろん至らぬ所だらけ）

さて、今回は、非同期処理を実装する上でわかりやすい記事が少なかったため、自分なりにまとめてみようと思います。

そもそも非同期処理とは？

非同期とは、英語で言えばasynchronousですが（意味はないが英語にしてみる）、 つまりは複数の処理があるときに、それぞれの処理が完了してから次の処理を行うのではなく、 １つの処理を始めたら終わる前に次の処理をやるようなイメージです。 まあ詳しい定義とかは省きます。 使用したいタイミングとしては、例えばどこかから天気を取得するために通信を行うとして、その間に他の処理を行いたい場合です。 通信に関しては時間がかかりますから、いちいち天気情報の取得が完了してから処理を行っていてはスピードが遅くなってしまいます。 そこで、天気を取得するAPIを呼んだあとに、結果が取得できるまでに他のAPIをまた呼んだりするということです。 具体例を見てみましょう。(はてなにコード埋め込むのが初めてで見にくい)

function asyncFunc() {
  return new Promise(resolve => {
    setTimeout(function() {
      console.log('resolving')
      resolve()
    }, 1000) 
  })
}

function callAsyncFunc() {
  console.log('start')
  asyncFunc()
  .then(() => {
    console.log('after resolving')
  })
  console.log('after calling asyncFunc')
}

callAsyncFunc()
    

こちら、上のasyncFunc()が時間のかかる処理です。 callAsyncFunc()内で時間のかかる処理を呼び出し、終わったらconsole出力をしています。 こちらの出力は以下になります。

start
after calling asyncFunc
resolving
after resolving

  

ポイントとしては、時間のかかる処理にPromiseを使うことです。（一説によるとPromiseという命名には某消費者金融機関からの圧力があったとかなかったとか) まあこいつが初めてだとなんじゃこいつはああああってなりますよね。 上の関数asyncFunc()では、

return new Promise()

というように、ただPromiseクラスのインスタンスを返しているだけです。 要は以下のような書き方のほうがわかりやすいかもしれません。

function hoge() {
  let promise = new Promise(resolve => {
    setTimeout(function() {
      console.log('resolving')
      resolve()
    }, 1000)
  })
  return promise
}

このようにpromiseクラスのインスタンスを返す関数は、非同期処理となります。 Promiseオブジェクトのインスタンスを作成する際に、引数に行いたい処理を記述します。 天気の例だと、ここで天気情報を取得するAPIを呼び出したりです。 今回の例では、単に1秒待ってからconsoleに出力をしています。 そしてまた気持ち悪いのがこのresolve()というやつですよね。 このresolve()は、まあ英語で言ったら解決という意味ですから、非同期処理が解決したということを示す役割でしょう。 つまり、非同期処理をPromiseを使用して作成した場合、resolveで終わりましたよ〜ということを示してやらないといけません そうでなければ、天気情報を取得し終わったら画面に表示したい、といったことが実現できません。 さて、ダラダラと書いていますが（そもそも人にわかってもらおうとも思っていませんから）、

asyncFunc()
  .then(() => {
    console.log('after resolving')
  })

こちらのthenについてです。 このthenというのは、Promiseのインスタンスがresolveしたときに呼び出されます。 つまり、この場合、わかりやすく書くとこうなります。（最初からわかりやすく書け）

function callAsyncFunc() {
  console.log('start')
  let promise = asyncFunc()
  promise.then(()=>{
    console.log('inside then')
  })
  console.log('after calling asyncFunc')
}

このように、promiseのインスタンスにthenをつければまあいとも簡単に、非同期処理が終わってから何かの処理をするということができます。

これ以上の説明もそんなに必要ないと思うので、あとは何パターンかpromiseの使い方を載せておきます。(説明がめんどくなった)

function getRandomInt(max) {
  return Math.floor(Math.random() * Math.floor(max));
}

function asyncFunc() {
  return new Promise(resolve => {
    let interval = 1000*getRandomInt(3)
    setTimeout(function() {
      console.log('resolving')
      resolve()
    }, interval) 
  })
}

function callAsyncFunc() {
  console.log('start')
  let promises = []
  let promise1 = asyncFunc()
  promises.push(promise1)
  let promise2 = asyncFunc()
  promises.push(promise2)
  Promise.all(promises)
    .then(()=>{
    console.log('inside then')
  })
  console.log('after calling asyncFunc')
}

callAsyncFunc()

出力

start
after calling asyncFunc
resolving
resolving
inside then

こちらは、２つの非同期処理を開始し、２つともが終わった時点で処理を行うようなものです。 もちろん、それぞれが終わったタイミングで呼び出したい処理があれば、それをpromise1.then()のような形で書いておけばどちらも実行されます。

forループで何回も呼び出したいとき

function getRandomInt(max) {
  return Math.floor(Math.random() * Math.floor(max));
}

function asyncFunc() {
  return new Promise(resolve => {
    let interval = getRandomInt(3)
    setTimeout(function() {
      console.log('resolving')
      resolve()
    }, 1000*interval) 
  })
}

function callAsyncFunc() {
  console.log('start')
  let promises = []
  for (i=0; i<=5; i++) {
           let promise = asyncFunc()
           promises.push(promise)
           }
           Promise.all(promises)
           .then(()=>{
    console.log('inside then')
  })
  console.log('after calling asyncFunc')
}

callAsyncFunc()

出力

start
after calling asyncFunc
resolving
resolving
resolving
resolving
resolving
resolving
inside then

こちらは、for文でpromiseを作りまくって、全部終わったら何かの処理をしたい、みたいな感じです。

function asyncFunc() {
  return new Promise(resolve => {
    setTimeout(function() {
      console.log('resolving')
      resolve()
    }, 1000) 
  })
}

async function callAsyncFunc() {
  console.log('start')
  await asyncFunc()
  .then(()=>{
    console.log('inside then')
  })
  console.log('after calling asyncFunc')
}

callAsyncFunc()

出力

start
resolving
inside then
after calling asyncFunc

こちらはawaitというものを使用しています。 awaitは、promiseを返す関数の呼び出しにつけると、その関数が返すpromiseがresolveするまであとの処理を待ってくれます。 awaitを使う場合は、awaitを使う関数の定義時にasyncをつける必要があります。 まあこれはつけてなかったら例外が飛んでくるので気にしなくてもいいでしょう。

awaitで各ループを待ちたい場合は以下のようにします。

function getRandomInt(max) {
  return Math.floor(Math.random() * Math.floor(max));
}

function asyncFunc() {
  return new Promise(resolve => {
    let interval = getRandomInt(3)
    setTimeout(function() {
      console.log('resolving')
      resolve()
    }, 1000*interval) 
  })
}

async function callAsyncFunc() {
  console.log('start')
   for (i=0; i<=5; i++) {
    await asyncFunc()
      console.log('looping', i)
    }
    console.log('after calling asyncFunc')
  }

callAsyncFunc()

出力

start
resolving
looping 0
resolving
looping 1
resolving
looping 2
resolving
looping 3
resolving
looping 4
resolving
looping 5
after calling asyncFunc

疲れました。以上です。

Prott プロトタイピング モバイルアプリ開発

モバイルプロトタイピングの救世主
Prott
を使用しはじめました！

prottapp.com

みなさんご存知の通りラフなどをとりこみ画面遷移などを組み込むことができるアプリです。

そのProttの中でも今回は
Wireframe
作成機能を使用してみました！

この機能は通常使う手書きのラフをGUIで簡単にデータとして作成できる機能です。

使い方としては
1. 要素
2. 配置
を決めることで画面の役割、機能を明確にすることが考えられます！

そしてこのワイヤーフレームをもとに詳しいデザインにとりかかるといった流れですね！

プロトタイプ開発においてこのワイヤーフレームの手順を踏まずにいきなりデザインに入るとこうなります。

1. デザイナーに要件を伝える。
2. デザイナーが要件にそって自分で解釈しながらデザインを完成させる。（時間かかる）
3. 要件が変更になったのでこの画面はいりません。こっちの新規画面を作成よろです。
4. デザイナーあぼーん
5. でも言われたとおり作る
6. やっぱりいｒ...（以下繰り返し）

でプロトタイピングにそんなに重要じゃないデザインに異常な時間（と外注している場合はお金も）がかかります。

これはプロトタイプ開発が要件定義の変更を柔軟に許容するアジャイル開発で行われることが多いことに起因します。

スタートアップの場合はこうやってとりあえず大枠からやり、細かいところは後からやることが肝要です！

Prottは意外にお高めです。
ワイヤーフレームは月4000円のクラスから利用可能。

とまあ当たり前のことをつらつらと書きましたが是非皆さんもPrott試してみてください！！

prottapp.com

droidkaigi 2017 ２日目 参加レポート

droidkaigi2017 ２日目！！

雑魚エンジニアですが懲りずに参加してまいりました。 

下は２日目の配給の昼ごはん。コロッケ目玉焼きバーガー的な。
ありがたいです。。 

さて肝心の内容の方ですが

1. １１個の個人アプリ作ってみた
2. Android6.0対応について
3. 音声認識を使いこなす

を聞かせていただきました。

まずなにより

LTしてるエンジニアかっこええ・・・

いつか私も晴れ舞台に立ちたいものです。

そのために早く基礎は一通りみにつけつつ長期スパンでのスキルも伸ばしておく。

なかなか気の長い話ですが楽しんでやっていきます。

明日はJAWSなのでまたゆっくりできたらdroidkaigiのほうのレポートを詳しく書きたいと思います。

では良い週末を！

droidkaigi2017 参加レポート！！

参加してきました！

初の参加でしたがおもしろいイベントですね！

参加させていただいたのは

1. Androidセキュリティ最前線！
2. Android Shortcuts in Android Nougat 7.0
3. Android Resources Refactoring

以上の３つです。

下２つは英語のセッションで、話を聞いてみた所海外からこのイベントのために来てる人もまあまあいるとか。
私がお話したのはデンマークの開発者さんでした！
おもしろい！

あとモンストの中の人に会えたのも嬉しかったですね！

是非明日２日目も面白い出会いに期待です！