ひらめの日常

プログラミングと読書と

Scalaで累積和

scanLeftはfoldLeftの途中経過の値を保持するような関数。 これを使えば、累積和の計算が簡単にできる。

初期値が一番最初に挿入されるので、元の配列より大きさが+1されていることに注意する。

val a = Array(1, 2, 3)
val d = a.scanLeft(0L)(_ + _)

println(d.mkString("Array(", ", ", ")"))
// Array(0, 1, 3, 6)

Visual Scala Reference はコレクションメソッドを図でわかりやすく解説していておすすめ。 superruzafa.github.io

Scalaで競技プログラミング ABC114-C 755

始めに

今までC++競技プログラミングをしてきたのですが、業務でScalaを書いていることもあり、ScalaAtCoderを解いてみようと思います。大半が解いたことある問題かつ、目的はScalaに慣れることなので、解説は省いています。
勉強途中であることもあり、より良い書き方とかあれば是非是非コメントにアドバイスお願いします!

問題はこちら

atcoder.jp

解答

最初はdfsの外に var ans = 0 を持って、dfsのなかでインクリメントする処理を書いていたが、なるべくvalを使いたいのでdfsが答えを返すように書き直した。割と綺麗に書けて満足。

import scala.io.StdIn

// https://atcoder.jp/contests/abc114/submissions/17722890
object Main extends App {
  val n = StdIn.readLong

  def dfs(now: Long, use7: Boolean, use5: Boolean, use3: Boolean): Int = {
    if (now > n) 0
    else {
      (if (use3 && use5 && use7) 1 else 0) +
        dfs(now * 10 + 3, use7, use5, use3 = true) +
        dfs(now * 10 + 5, use7, use5 = true, use3) +
        dfs(now * 10 + 7, use7 = true, use5, use3)
    }
  }

  println(dfs(0, use7 = false, use5 = false, use3 = false))
}

Submission #17722890 - AtCoder Beginner Contest 114

Scalaで競技プログラミング ATC001-A 深さ優先探索

始めに

今までC++競技プログラミングをしてきたのですが、業務でScalaを書いていることもあり、ScalaAtCoderを解いてみようと思います。大半が解いたことある問題かつ、目的はScalaに慣れることなので、解説は省いています。
勉強途中であることもあり、より良い書き方とかあれば是非是非コメントにアドバイスお願いします!

問題はこちら

atcoder.jp

解答

再帰関数でTLEにとっても悩まされた...末尾再帰で書ければもう少し早くなったのかもしれないが、どうやればいいかわからなかった。

さらに、再帰の中で PartialFunction を呼び出していると TLE になって、PartialFunction を回避するだけで1秒近く早くなる事象に遭遇した。確かに部分関数値を生成しているのでそのコストはかかるだろうけど、こんなにかかるのか?と疑問に思った。特にコップ本などに言及はなかったので、もう少し調べてみたい。
変更前:Submission #17676971 - AtCoder Typical Contest 001
変更後:Submission #17677294 - AtCoder Typical Contest 001

他には、初心者なのでArray型の初期化方法をこちらを見て知った。

qiita.com

val a = Array.fill(n)(sc.nextInt) // n要素標準入力で受け取る
val a = Array.ofDim[Int](3, 3) // 3*3の二次元配列

最終的な解答はこちら。

import java.io.PrintWriter
import java.util.Scanner

object Main extends App {
  val pw = new PrintWriter(System.out)
  val sc = new Scanner(System.in)

  val h, w = sc.nextInt()
  val c = Array.fill(h)(sc.next())
  val seen = Array.ofDim[Boolean](h, w)
  val s = for {
    i <- 0 until h
    j <- 0 until w
    if c(i)(j) == 's'
  } yield (i, j)
  
  val dis = Array(1, 0, -1, 0)
  val djs = Array(0, 1, 0, -1)

  def dfs(i: Int, j: Int): Boolean = {
    var ret = false
    (0 until 4).foreach { idx =>
      val ni = i + dis(idx)
      val nj = j + djs(idx)
      if (0 <= ni && ni <= h - 1 && 0 <= nj && nj <= w - 1 && !seen(ni)(nj)) {
        seen(ni)(nj) = true
        if (c(ni)(nj) == '.') ret = ret || dfs(ni, nj)
        else if (c(ni)(nj) == 'g') ret = true
      }
    }
    ret
  }

  val (si, sj) = s.head
  seen(si)(sj) = true
  val ans = if (dfs(si, sj)) "Yes" else "No"
  pw.println(ans)
  pw.flush()
}

Submission #17677400 - AtCoder Typical Contest 001

Scalaで競技プログラミング ABC167-C Skill Up

始めに

今までC++競技プログラミングをしてきたのですが、業務でScalaを書いていることもあり、ScalaAtCoderを解いてみようと思います。大半が解いたことある問題かつ、目的はScalaに慣れることなので、解説は省いています。
勉強途中であることもあり、より良い書き方とかあれば是非是非コメントにアドバイスお願いします!

問題はこちら

atcoder.jp

解答

C++で解いたときはbit全探索をしたが、今回パッと思いつかなかったので、再帰関数で実装した。各種類の参考書を購入するかしないかで分岐するようにして、全ての場合を調べる。

本来なら Array の要素を書き換えるような方法で入力を受け取りたくないが、Scalaっぽく受け取るとしたらどうなるのだろうか...?(そもそも ArrayScalaであまり使わない印象があるが...)

import java.io.PrintWriter
import java.util.Scanner

object Main extends App {
  val pw = new PrintWriter(System.out)
  val sc = new Scanner(System.in)

  val n, m, x = sc.nextInt()
  val aArr = new Array[Array[Int]](n)
  val cArr = new Array[Int](n)

  (0 until n).foreach { i =>
    cArr(i) = sc.nextInt()
    aArr(i) = (0 until m).map(_ => sc.nextInt()).toArray
  }
  val default = 1e9.toInt

  def dfs(idx: Int, sum: Int, willBuy: Boolean, skills: Array[Int]): Int = {
    if (idx > n - 1) {
      if (!skills.exists(_ < x)) sum
      else default
    } else {
      if (willBuy) {
        val nxt = aArr(idx).zip(skills).map { case (a, skill) => a + skill }
        val nxtSum = sum + cArr(idx)
        dfs(idx + 1, nxtSum, willBuy = true, nxt) min dfs(idx + 1, nxtSum, willBuy = false, nxt)
      } else {
        dfs(idx + 1, sum, willBuy = true, skills) min dfs(idx + 1, sum, willBuy = false, skills)
      }
    }
  }

  val result = dfs(-1, 0, willBuy = false, new Array[Int](m))
  val ans = if (result == default) -1 else result
  pw.println(ans)
  pw.flush()
}

Submission #17661602 - AtCoder Beginner Contest 167

Scalaで競技プログラミング ABC151-C Welcome to AtCoder

始めに

今までC++競技プログラミングをしてきたのですが、業務でScalaを書いていることもあり、ScalaAtCoderを解いてみようと思います。大半が解いたことある問題かつ、目的はScalaに慣れることなので、解説は省いています。
勉強途中であることもあり、より良い書き方とかあれば是非是非コメントにアドバイスお願いします! 記念すべき第一回は、"Welcome to AtCoder" です。

問題はこちら

atcoder.jp

解答

まず、空白区切りの数字は nextInt で受け取れる。空白区切りの文字列は next で受け取れる。

前半の入力では、まだACしていない問題に対してWAの数を加算していくようにしている。この部分は配列の要素を書き換えているので、上手な書き方が他にあるんだろうな(と言いつつ思い付かず)。

後半は取りあえず関数型っぽく foldRight で書いたけど、もっと綺麗にかける方法がないかと思っている。

object Main extends App {
  val pw = new java.io.PrintWriter(System.out)
  val sc = new java.util.Scanner(System.in)

  val n, m = sc.nextInt
  val aced = new Array[Boolean](n + 1)
  val penalty = new Array[Int](n + 1)

  (1 to m).foreach { _ =>
    val p = sc.nextInt
    val s = sc.next
    if (s == "AC") aced(p) = true
    else if (!aced(p)) penalty(p) = penalty(p) + 1
  }
  val (ac, wa) = aced.zip(penalty).foldRight((0, 0)) {
    case ((aced, penalty), (accAc, accPen)) =>
      if (aced) (accAc + 1, accPen + penalty)
      else (accAc, accPen)
  }

  pw.println(s"$ac $wa")
  pw.flush()
}

Submission #17657450 - AtCoder Beginner Contest 151

3ヶ月でやった事を振り返る - 入社1年目7~9月

はじめに

3ヶ月ごとに何をやったか、社内・社外関係なくブログにまとめていきたいと思います。前回の記事はこちら。

hiramekun.hatenablog.com

お仕事

エンジニアリング

自分も関わった学習アルゴリズムに関する特許を出願しました。どんな流れで出願するのか、どのような資料を用意するのか、など知財に関する本当の基礎を実務で体験できて面白かったです。

また、引き続き学習アルゴリズム周りの新機能実装をしていました。既存のデータ構造やコードを読み解くのに時間がかかり実装自体はスピード早くなかったので、スピードアップして行きたいです。特に、自分の実装をもう少し信頼したほうが良いと感じました。ハマったときに毎回自分のコードばかり見るのではなく、その他に原因があることも多々あります。自分の実装が期待する挙動ではないときには視点を変えてみることが大事だと感じました。

言語の面だと、Scalaらしい書き方ができているか怪しいので慣れていきたいです。可読性と実装スピードとどちらを取るかなど、色々悩むことがあり、コードを書いている時間よりも考えている時間ははるかに多いです(一般的にそうだとは思いますが)。他にはOption を for文で回したりすることが気持ちいいと感じるようになりました。

業務をしながら勉強をすることが案外難しいと感じています。コードを書く時、自分は動かすことを重視しすぎると、「とりあえずたくさん書く」ことになりがちです。常に新しい書き方はないか、ここで使っているベースとなる技術はどんなものかなど、一回立ち止まって考えてinputすることで日々成長できるのかなと思いました。立ち止まらないと、「業務で採用されてる技術を自分も使うだけはできるが、中身を理解しておらず新しいプロジェクトで自ら採用することはできない状態」に陥ると危機感を覚えました。実践して行きたいですね。

ざっと新しく勉強したことは以下のようなものです。AkkaとScalaについては本も読んだので、お勉強の章でまた触れます。まだ非常に浅い理解なので深めていきたいです。

全社関連

会社をより良くしていくオープンなプロジェクトがあり、そこに複数参加していました。役員の方に直接指摘をしても、人ではなく内容を見てくれるので、コミュニケーションが取りやすいと感じました。

採用関連では、座談会に登場したものがWantedlyの記事になったり、採用プロセスについてちょっと横から意見を出したりしてました。

全社的なプロジェクトでたくさん発言するように心がけていたのですが、これからは特に慣れてしまわないことを心がけていきたいです。現状に慣れてしまっては、入社したそのままの熱量を保つのは難しいと感じています。適度な緊張感を持って熱量忘れずに仕事をしていきたいです。

教育のお勉強

教育を勉強するサークルがあって、参加しています。業界に関係あることを学べて貴重だし、その時間が業務時間内に確保できることに感謝しています。意識して時間を設けないと継続してinputをしない感覚があるので。。。内容は「教育に関連すること」としか決まっていないので、毎回お題が違って楽しいです。 他にも、教育のより専門的な内容を深めるサークルがあって、自分は発表を聞くだけの参加をしています。それぞれ興味深いテーマを扱っているので、ここに一例を挙げます。

  • 世界のEdTech市場
  • 文科省から出ている資料を読んでみる
  • 反転学習
  • 習熟度別授業の効果

お勉強

業務に関係しそうなことを引き続き勉強していました。

Scalaスケーラブルプログラミング
興味ないところを少し飛ばしたりしましたが、全部読みました。設計に関する内容は、実際に実装するときに読み返すと自分の力となる印象を受けました。リファレンスとして、何か詰まったことがあったときに戻ってきてまた参考にしたいです。

Scalaスケーラブルプログラミング第3版

Scalaスケーラブルプログラミング第3版

Akka実践バイブル - 2章まで
2章までだけ読みました。アクターモデルの考え方など勉強になりましたが、使わないといまいち実感が湧かないというのが正直なところでした。業務で自分が実装するタイミングでもう少し読み進めたいと思います。

Rによる項目反応理論
項目反応理論に関しては最初の3ヶ月でも勉強していましたが、具体的なアルゴリズムについて勉強したいと思い読み始めました。実際のデータを行列として扱い、EMアルゴリズムを用いてパラメータを推定するなど、詳しいところまで書いてあったので読んでよかったと感じます。

ベイズ推論による機械学習入門
グラフィカルモデルについて勉強したいと思ったので、その前段階としてベイズの入門書を読みました。入門書とはいっても、自分にとっては数式を追うのは割と大変でした。モデリング→パラメータ推定→未知データ推論→近似手法 と、統一した流れで扱っており、途中式も丁寧であったので良い基礎固めになりました。

PRML 下 - 8章
グラフィカルモデルの勉強の続きとして、8章だけ読みました。とはいっても2週間と少しかかりました。PRMLのなかでも特に価値がある章とよく挙げられますが、確かにわかりやすかったです。推論の原理は理解がしやすかったのですが、具体例がもう少し勉強したいと感じました。

見返してみると、プログラミング・アルゴリズム系の勉強が多めになってしまい、教育関係の勉強が疎かになってると感じました。次の3ヶ月で何かしらinputしたいと思います。

趣味

競技プログラミング

最近すっかりご無沙汰になってしまいました。純粋に、自分は他の勉強の方が楽しいと思う時が多くなったように感じます。たまにAtCoderの問題を解いたりするのですが、「みんな解けててレベル上がっててすごいなあ」という感想です。またモチベが上がったらコンテスト参加しようと思っています。

スマブラ

スマブラ世界戦闘力のVIPボーダー、変動数、段位 - クマメイトでいうところの魔境到達!あたりをうろうろしています。一回負けると戦闘力がとても下がる割に、勝っても全然上がらないので魔境です...。スマメイトは最高1570くらいで、これも気を抜くと1500以下になってしまいます。スマメイトでは安直な行動が通らないので、ある程度ちゃんとスマブラしないとボロ負けするイメージでした。まずは1500安定で、その次に1600目指していきたいですね。

f:id:thescript1210:20201001235809p:plain:w500

ポケモン

今更ソードシールドを始めました...実は赤しかやったことないので、クリアした後のやり込み要素多すぎて混乱していますw

エンジニアが積ん読解消パック行ってきたよ

時間のない人向け

  • THE RYOKAN TOKYO の「積ん読解消パック」に二泊三日で行ってきた。
  • 温泉気持ちいい。
  • ご飯とてもおいしい。
  • PRML持参して、30ページ読んだ(一応目標は達成した)。
  • 大満足。また行きたい。

はじめに

f:id:thescript1210:20200927030309j:plain:w500
公式Twitterより

湯河原にある 湯河原 | THE RYOKAN TOKYO の「積ん読解消パック」を何回かTwitterで見かけてかなり気になっていました。そこで、エンジニア1年目の自分が、夏休みを取得して2泊3日で行ってきた体験記です。

目立った特徴としては、こんな感じのものがあります。詳細はwebサイトを見てください。他にもいろんなサービスがついていてワクワクします。

  • ご飯が1日3食ついてくる。旅館のご飯ではなく、定食のようなものを出すことで費用を抑えている(らしい)。
  • コーヒー/紅茶/ハーブティー頼み放題。
  • 本を事前に郵送しておける。帰りに家に返送もできる。
  • 読書枕“HONTO”の貸出し。
  • スタンドライトの貸出し。

今回の目的は主に下の二つでした。

たくさん読めるとは思っていなかったので、自分の持参した「積ん読」はPRMLだけです。8章のグラフィカルモデルを読み終わるという強い意思の元出発しました。

結果どうだった?

なんとか読み終った

30ページくらいだったので余裕かと思っていたのですが、案外進みませんでしたね。何とか読み終えることができてよかったです。

リラックスできる

夏休みをとってパソコンも持っていかず、気分転換するぞ!という気持ちだったのですが、本当にリラックスできてこの目的は達成できました。

まずお部屋が広くて、さらに人をダメにするソファが置いてあったので、 人としてダメになれました。ちなみにちゃんと座椅子もあるので、姿勢良く集中したいときはそっちに移動して集中ができました。

f:id:thescript1210:20200927023037j:plain:w300
お部屋

温泉もよかったです。露天風呂は無いのですが、ちゃんとした温泉で、ゆったりとつかってました。平日だったのと、時期が時期だったので毎日貸し切り状態でお湯に浸かってました。本当は朝風呂とかしたかったんですが起きれず...

ご飯がとてもおいしい

何より 全てのご飯が美味しかった です。お料理の代金を抑えているという文章を確認していたので期待していなかったのですが、とても美味しくて満足度高かったです。さらに量がたくさん。夜ご飯はちょっといいものにしてもらいました。

f:id:thescript1210:20200927022621j:plain:w300 f:id:thescript1210:20200927182753j:plain:w300f:id:thescript1210:20200927231919j:plain:w300
左から朝食、昼食、夕食

夜食があって、21時頃にお部屋に届けてくれるとのこと。さらにお願いすればポットにコーヒーやお茶を入れてもらえて、部屋にたくさん持って帰れます。この辺はコンセプトが面白いなーと思いながら、両方とも頼んでしまいました。美味しかったです😇。

f:id:thescript1210:20200927023459j:plain:w200f:id:thescript1210:20200927023520j:plain:w300
夜食メニューと頼んだやつ

そのほか感想

生活リズム

これはこの旅館に限らず、朝食のつく宿泊全てに言えるのですが 夜型の私に8時朝飯は厳しい という感想を抱きました。眠い目を擦りながらおいしい朝ごはんを食べ、部屋に戻ってお昼まで寝る...という何とも本末転倒な過ごし方を 二日目はしてました...。朝早く起きるために早く寝ることにしたのですが、そう簡単に体内時計は治りませんでしたね。

f:id:thescript1210:20200927040331p:plain:w300
二日目

あれ...あまり勉強できてないようです。おかしいですね。眠くなって寝て、少し勉強して気付いたらご飯の時間。ご飯を食べて眠くなって、少し寝てお散歩して、その後でようやく再開...目標を達成したとはいえ、もう少し読めると思っていました。自分の実質勉強時間はとても短いと思います。

ご飯の時間が決まっているので、生活リズムを変に狂わせることがないのは、家とは違って良いことだと思いました。

いかにも旅館!という感じではない

旅館と宿名についていますが、一般にみなさんが想像されるような旅館ではないと思います。自分は事前に知っていたし、変に気を張らなくて良いので居心地がよかった ですが、おもてなしが豊富な一般の旅館を想像すると少し拍子抜けすると思います。

と書きましたが、スタッフの方々の接客はとてもよかったのでその点は何も不安に思う必要はないです。

WiFiはつながらなかった

WiFiが通っているのですが、ロビーからお部屋が遠かったせいか、自分のお部屋からは繋がりませんでした。今回は参考書読むだけなので大丈夫なのですが、開発合宿をしようと思った時には頭に留めておいたほうが良いかもしれません。(開発合宿してみたいと思ったので改善に期待したいです...!)

まとめ

色々と感想を書きましたが、全体としては リフレッシュできて進捗も生めたので大満足 でした。また参考書を片手に来たいと思ったし、WiFiさえ改善されれば開発合宿にも使いたいと感じました。

今プラン一覧を見たらコワーキング温泉パックとかもできてました。上手に運営されていると感じると共に、コンセプトを絞るだけでこんなにワクワクするのだと驚きました。他のところに旅行する際も、自分で考えてみたいですね。