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を使用。下記記事のコメントにあるように初期値を与えた方が安全。
AtCoder ABC 151 A - Next Alphabet (100 点)
はじめてABCに参加
問題概要
英小文字C が与えられるので、アルファベット順で次に来る文字を返す。
制約
- Cは'a'から'y'までのアルファベットのうち1文字
解法1
本番で書いた方法
最初に変換用のハッシュを生成した。
c = gets.chomp keys = ('a'..'y').to_a vals = ('b'..'z').to_a hash = Hash[keys.zip vals] # {'a'=>'b', 'b'=>'c',...} puts hash[c]
解法2
String#nextで一瞬...
puts gets.next
余談：Brainfuckだと下のコードでいけるらしい...!
,+.
2020week2
勉強記録つけながらやっていこうというやつです。
まとめ
全体的な記録はStudyplusを利用
- 平日は通勤中に英単語、帰ってから競プロの問題を解く流れを1週間通した。
- 仕事終わりに数学やっても頭が働かないので途中でやめた。
英語
mikanでTOEFL英単語3000
<やったこと/振り返り>
- 1週間でRank22/30まで到達。来週中頃から復習フェーズを回していけそう。
- 基本的には通勤の電車でやっているため、平日の方が捗る。
- 行きで新しい単語、帰りに既出の単語を苦手なものから潰していく、という進め方をしている。
- まずは英→日でやっているが、１周したら日→英もやる。
- iKnowも気になっているが、まずはmikanでTOEFL英単語3000をやりきってから考える。
<次のアクション>
- Rank30まで進める
- 「完璧に覚えた/ほぼ覚えた」の合計を全体の7割(2100/3000)にする。
アルゴリズム
<やったこと/振り返り>
- 今はけんちょんさんの記事に沿ってAtCoderの問題を解き進めている（言語はRuby）。
- 先週末に最初の10問を終えたので、今週は「ここまで解いたら」で紹介されている問題を全部解いた。
AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～ - Qiita
<次のアクション>
- ABCに出てみる。
- 最初の10問の類似問題を全部解く。
- Rubyでの累積和とBit演算についてまとめる。
数学
数研講座シリーズ 大学教養 微分積分
<振り返り>
- 「第2章 関数」を進め始めた。
- 基本的には第1章の数列で学んだ内容を関数(1変数)に置き換えていく構成となっている。
- 平日のうちはあまり捗らなかった。
<次のアクション>
- 週末のうちに第2章を終える。
- 第2章のまとめ記事を書く。
