2020week5
今週のハイライト
- リファクタリングRuby復刊
去年の8月復刊ドットコムに登録したリファクタリングRubyが復刊決定した。実はある程度票が集まったタイミングでアスキーに問い合わせたところ再販検討中との回答を頂いてたのだけど、実現して良かった。
リファクタリングRuby復刊した！！https://t.co/anoNEh0g6c pic.twitter.com/PkLT7UKxrZ
— 渡り鳥🦉 (@wataridori_k) January 26, 2020
- mikanで英単語学習継続
- 平日はアルゴリズムの勉強時間あまり取れず。
- 数学は日曜に3章微分を終わらせた。
仕事が忙しめだったので平日の勉強時間はあまり取れず。
英語
mikanでTOEFL英単語3000
<振り返り>
- ひたすら復習を回すフェーズで、平均400単語/日→3000弱
- 400単語にかかる時間が30→20分とだいぶ短くなった。
- 「ほぼ覚えた」以上の割合は微増、「完璧に覚えた」が1000を超えた。
→日々やってるとまだうろ覚えな単語があるなと感じるが、数字で見るとよくなっている。なかなか覚えられない単語は他の同意語で補えるでしょ、と思ってしまう単語が多い気がしている。覚える時にニュアンスや使いどころの違いを考えてないので、ちょっと踏み込んで調べてみる時間はとった方がよいかも。あとテストに必要or教養として覚える目的以外では結局自分が使う分野の英文ベースで覚えた方が効率が良い。
<次のアクション>
- 英単語の復習は引き続きやる。
- 自分の分野の英語としてRuby Weeklyの興味ある記事を読んでみる。
アルゴリズム
<振り返り>
ABC153に参加。
- 初めてDまで解けたが、時間がかかったため今までよりパフォーマンス低く残念。
- ただ直前まで勉強してた再帰を使えて良かった。
「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」（以下、螺旋本）はあまり進められず。
- 7章 高等的整列はdone
- 8章 木の途中まで。
<次のアクション>
- 螺旋本の8, 9章を終える。
- 今週末ABCがあったら参加
- Atcoderの言語アップデートテスト環境が公開されたので触ってみる。
【言語アップデート】新ジャッジのテスト環境を公開しました。ほぼテストできていない言語も数多くあるので、ぜひ各言語で確認提出をしていただければと思います。ご協力よろしくお願いします。https://t.co/IFWMzsQbv5
— AtCoder (@atcoder) January 31, 2020
数学
数研講座シリーズ 大学教養 微分積分
<振り返り>
- 3章 微分を勢いで終わらせて、4章 積分もさらっと通して読んだ。
- やっとテイラー展開や級数展開が出てきた。懐かしい
<次のアクション>
その他
- 量子コンピュータについてインプット
ちょうどよく「驚異の量子コンピュータ」が出てたので読んだ。
- 元々物理やってない、かつ、ITちょっとわかる人向けに良さそう。
- I/II部はさらっと流して、III部の量子コンピュータの近況や課題を中心に読んだ。
- ハード面だと制御性を保ったままbit数をいかに増やすか、ソフト面だとどんな問題に適用するか、を気にしてさらに調べていけばよさそう。
- 今の自分の立場だとソフト面で調査するのが良さそうだが、ハード面も興味あるので色々漁ってみる。
最近観てるyoutubeチャンネル。色々まとまっててありがたい。
RubyMineが重くてVimを触り始めた。
- 今さらだけどvimtutorやるぞ！
Scrapboxを触り始めた。
- 社内で読書会を始めるにあたり、Scrapboxを使いまとめ始めた。某エバンジェリストの手ほどきをうけて楽しさがわかってきたので、個人でも使い始めた。
最近聴いてるPodcastでも紹介されてた（更新止まってるけど）
2020week4
まとめ
- 通勤でmikan英単語を継続できた。周回のスピードが上がって良い感じ
- 朝早めに起きて勉強時間を30分とれた。
- アルゴリズムの勉強はうまく継続できている。
- 数学は3章終わらず。難易度でペースが落ちたというより時間を取れなかっただけかと。
英語
mikanでTOEFL英単語3000
<振り返り>
- ひたすら復習を進めている。
- 平日で2000単語達成。
- ルーチンになってスピードが上がり、目標達成したら本を読むなど余裕が出てきた。
- カードめくり試していく。
- やり方をいくつか試したが、「ランクごとに100単語ずつまとめてめくる→テストする」のが自分にはあっている。
- 「ほぼ覚えた/苦手」を中心に毎日400単語復習する。
- カードめくりで100単語ずつやるため、習熟度は気にせず行き帰り200単語ずつこなしている。
- アプリの「その他」→「効率的な学習方法」の項目に今更気づいた。
- 学習設定については自分で考察してたことと同じでよかった。
- 時間設定をおすすめに沿って3秒まで短くした。これもあり学習ペースが上がった。
- なんとStudyPlusと連携機能があったためONにしてみた→何も起こらないよ😢
<次のアクション>
- ひたすら復習
- 1週間で3000単語を一周するようにしたいので、毎日の目標を400→600に上げて平日やるか、休日も頑張るか悩む。
アルゴリズム
<振り返り>
ABC152に参加
- ABC3完。今回のDは必要な知識は持っていたので、経験不足。
- 復習記事：AtCoder ABC 152 D - Handstand 2 (400 点) - 渡り鳥の旅路
「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」（以下、螺旋本）を進めた（4-6章）
- 再帰関数にまだ慣れていなく、サンプルコードを見てもすっと入ってこない感じ。要復習
- 最近青色コーダーになった人の記事が良かった。螺旋本を終えたらABCの古めの過去問解いてみよう。
<次のアクション>
- 1/26のABC153に参加
- 螺旋本を進める（7-9章）
数学
数研講座シリーズ 大学教養 微分積分
<振り返り>
- 第3章の途中。
- ペースが落ちてきた...!
- 第2章のまとめ記事も途中
<次のアクション>
- 第3章を終わらせる。
- まとめ記事は余裕あれば。
そのほか
- 最近リュックをINCASEからPUROのBYDAYに変えたら、身軽ですごく良い
![[プーロ] リュックサック BY DAY 軽量USBポート付 ブラック One Size](https://images-fe.ssl-images-amazon.com/images/I/41s08ztF40L._SL160_.jpg "[プーロ] リュックサック BY DAY 軽量USBポート付 ブラック One Size")
AtCoder ABC 152 D - Handstand 2 (400 点)
2回目のABC
問題概要
正の整数Nが与えられる。N以下の整数の組（A, B）について、
- Aの末尾の桁とBの先頭の桁が等しい、かつ、Aの先頭の桁とBの末尾の桁が等しい
となるものの個数を求める。ただしA, Bは先頭に0をつけない10進数表記である。
制約
- 1 <= N <= 2x105
解法1（本番でやったTLE）
やり方が思いつかなくてとりあえずサブミットしてみたやつ。 O(N2)なのでサンプルテストですでにTLEしてた笑
n = gets.to_i count = 0 (1..n).each do |i| (1..n).each do |j| count += 1 if i.to_s[0] == j.to_s[-1] && i.to_s[-1] == j.to_s[0] end end puts count
解法2（解説を参考に）
本番ではペアを作ることは何となく思いついたが、それをセットにして数え上げておくところまで至らなかった。桁の違いを考慮しなければと思っていたが、そういう訳でもなかった。
まず、Nを先頭の桁と末尾の桁（Nが1桁ならそれぞれ1桁目）の組に変換したペアが、それぞれ何個ずつあるか数えおく。
1からNまでの整数について、ペアの対となるペアを数え上げる。O(N)になる。
n = gets.to_i def encoder(x) a = x.to_s[0] b = x.to_s[-1] a+b end map = {} (1..n).each do |i| encoded = encoder(i) if map[encoded] map[encoded] += 1 else map[encoded] = 1 end end count = 0 (1..n).each do |j| encoded = encoder(j) oposite = encoded[1]+encoded[0] count += map[oposite] if map[oposite] end puts count
確認したところ構造体をハッシュのキーにできるので、encoderの返り値は(a, b)的な構造体にしてもよい。
2020week3
まとめ
- 通勤でmikan英単語を継続できた。
- 平日は競プロとアルゴリズム率高め。
- あいかわらず数学は週末まかせ
英語
mikanでTOEFL英単語3000
<やったこと/振り返り>
- Rank30まで進めた。
- 「完璧に覚えた/ほぼ覚えた」の合計を全体の7割(2100/3000)にした。
- 現状アプリ上の「覚えた」は英単語の表示を見て、選択肢から正しい日本語を選ぶため、平時に英文を読む分には精度が足りない。いくつかmikanの機能を見てみたところ、「暗記シートで選択肢を隠す」で少し改善しそう。
- また、今後のために他の「学習の設定」をみてみた。
- カードめくり学習：表示された英単語に対して「知っている/知らない」の2択で答えていき、設定単語数分めくったら最後にテストを行う。超短期の予習と復習をセットで行う感じが良さそう。
- 日→英：これからこれをやっていきたい。mikanでは日：英が1：多で対応しているため、日本語をみた時に思い浮かべた英単語があっていたとしても、表示される選択肢では別の単語が出てくるケースがあるのがある少しいまいちに思える。日本語が表示されたときに知っている英単語を全て思い浮かべるようすれば解決だろうか。
- リスニング：良さそう。ただ電車内では聴き取りが厳しいので、通勤でやるスタイルの自分にはあってない。
<次のアクション>
- カードめくり試していく。
- 「ほぼ覚えた/苦手」を中心に毎日400単語復習する。
- よりIT寄りで使えるような学習方法を検討する。
アルゴリズム
<やったこと/振り返り>
ABC 151に初参加した。
- 今回はAtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～ - Qiitaを通しでやった段階でABC3完だった。これは順当だと思う。ありがとうございます。
ABCの復習記事書いた。
ABCの復習をしながらアルゴリズムの基礎をやる必要性を感じ、「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」を進め始めた。これはE問題の復習時に決めたのだが、2項係数を求めるためにユークリッドの互除法を理解しておく必要があったり、またD問題をBFSで解く場合はグラフを理解しておく必要があったりと、結局実践的な手法の前に基礎的なアルゴリズムを身につけておく必要があると感じたため。
- とりあえず3章のソート、4章のデータ構造の途中まで。
<次のアクション>
- プログラミングコンテスト攻略のためのアルゴリズムとデータ構造を進める（まずは4, 5章）
- 1/19のABCに参加
数学
数研講座シリーズ 大学教養 微分積分
<振り返り>
- 第2章を終えた。
- 第2章のまとめ記事を書く（途中）。
<次のアクション>
- 第2章のまとめ記事を終わらせる。
- 週末のうちに第3章を終える。
その他
最近、物理と計算機系の本を読み漁っている。特に量子コンピュータは大学院の時に核スピン量子ビットに近いところをやっていたので、思い出しながら胸熱になっている。そのころはプログラミングが苦手で自分でまともにシミュレーションできなかったし、AWSで量子コンピュータが使えたりもできなかったし、今は少しずつ揃ってきてる。元々サイエンスに関係するソフトウェアエンジニアの仕事に興味があり、Turing Complete FMのCERN回が聴いてから色々できることがあるんだなと思えたので、近づけるようアクションを続けたい。
AtCoder ABC 151 E - Max-Min Sums (500 点)
初めてのABC
Dは飛ばして、EをTLEでフィニッシュ
問題概要
- 定義：f(X) = max X - min X (Xは有限個の整数からなる集合)
- N個の整数A_1,....,A_Nが与えら、そのうちK個を選び集合Sを作る。このとき、A_iが同じ値でも添え字iが違う場合は区別する。
- 上記の組み合わせ全てについてのf(S)の合計を求めよ。
- 大きな値に備えて、答えはmod 109 + 7で出力すること。
制約
- 1<=N<=105
- 1<=K<=N
- |A_i|<=109
解法1（本番でTLEしたやつ）
組み合わせを単純にArray#combinationで用意したが、N,Kが大きくなると爆発的に組み合わせが増えるためそこでダメだった。
n, k = gets.split.map(&:to_i) nums = gets.split.map(&:to_i) combos = nums.combination(k).to_a sum = 0 combos.each do |combo| f = combo.max - combo.min sum += f sum %= 1000000007 end puts sum
解法2
TBD
課題を理解した上で再度解く
課題
解説や参考記事を見てると色々知識が足りてないので課題となるトピックと参考記事をリスト化しておく。
- 公式解説
2項係数を求める
感想
強くなって戻ってくるぞ！
AtCoder ABC 151 C - Welcome to AtCoder (300 点)
はじめてのABC
問題概要
AtCoderを受けている状況を想定
- N問のの問題に対してM回の回答を行う。
- i番目の提出はp_i番目の問題への提出で、結果はS_i（'AC' or 'WA'）である。
- 提出結果を元に正答数とペナルティ数を求める。
- 正答数の条件：'AC'を1回以上出した問題の数
- ペナルティ数の条件：'AC'を1回以上出した各問題において、初めて'AC'を出すまでに出した'WA'の数の総和
制約
- N, M, p_iは整数
- 1<= N <= 105
- 0<= M <= 105
- 1<= p_i <= N
- S_iは'AC'または'WA'
解法（本番でやった）
問題数決まってるし最初にN個分の容れ物用意するか？でも全部解くわけでもないし、バケット（Rubyだとハッシュ）にp_iをキーとした値を適宜入れていこう、という方針で進めた。
2段階の処理を、数え上げの条件に注意しながら実装した。
- バケットにデータを入れる。
- バケットを利用して数え上げ
ペナルティの数え方と、2回目以降の'AC'が出るケースはやり過ごすあたりに注意が必要。
n, m = gets.split.map(&:to_i) scores = {} penas = {} m.times do inputs = gets.split p = inputs[0].to_i s = inputs[1] if s == 'AC' if scores[p] != 'AC' scores[p] = 'AC' end else # WA if scores[p] != 'AC' if penas[p].nil? penas[p] = 1 else penas[p] += 1 end end end end score_count = 0 pena_count = 0 scores.each do |k,v| if v == 'AC' score_count += 1 pena_count += penas[k] unless penas[k].nil? end end puts "#{score_count} #{pena_count}"
解答例は最初からバケットにN個分の要素を用意するやり方をしてた。
AtCoder ABC 151 B - Achieve the Goal (200 点)
はじめてABCに参加
問題概要
N科目のテスト（各K点満点で点数は0点以上の整数）に対して、N-1科目までの点数が出ている時（i番目の点数はA_i）、平均点をM点以上にするために最後のテストで最低点取る必要があるかを求める。
達成できない場合は'-1'を出力する。
制約
- 2<=N<=100
- 1<=K<=100
- 1<=M<=K
- 0<=A_i<=K
- 与えられる値は全て整数
解法
必要な最低点を求める簡単な方程式を時、それを実装した。テストコードで0点をとっても良いケースの考慮が必要だとわかり条件を微調整。
本番で書いたコード
n, k, m = gets.split.map(&:to_i) scores = gets.split.map(&:to_i) sum = scores.inject(:+) required_score = n*m - sum # 必要な最低点を求める式 if required_score > k puts -1 elsif required_score < 0 puts 0 else puts required_score end
N-1科目までの合計を求める時にArray#sumなんで使えない!?となってたら、AtCoderはRuby2.3.3だった。。
よってEnumerable#injectを使用。下記記事のコメントにあるように初期値を与えた方が安全。
