【AtCoder-Ruby】ABC096 B - Maximum Sum
問題
問題文
黒板に, 3 つの正の整数 A , B , C が書かれています.
E869120 君は, 以下の操作を K 回行います.
- 黒板に書かれている整数のうち 1 つを選び, これを 2 倍した値に書き換える.
さて, K 回の操作を終えた後の, 黒板に書かれる整数の合計としてありうる最大の値はいくつでしょうか？
制約
- A , B , C は 1 以上 50 以下の整数
- K は 1 以上 10 以下の整数
考えたこと
- A, B, C の最大値を 2 * K 倍した値に置き換える（これ間違い。。。）
- A, B, C を足す
a = gets.strip.split.map(&:to_i).sort K = gets.strip.to_i a[-1] = a[-1] * (K * 2) puts a.inject(:+)
痛恨の間違い。
2 * K ではなく、2 ** K 。。。
とりあえず、無難な直しで回答
res = a[-1]
K.times { res *= 2 }
a[-1] = res
puts a.inject(:+)
回答
2回目、とりあえず直して提出
a = gets.strip.split.map(&:to_i).sort K = gets.strip.to_i a[-1] = a[-1] * (2 ** K) puts a.inject(:+)
考察
誤答は +5 分なので慎重に。
バランスですね。
ちなみに、タイムは以下の通り
| 問題 | 1回目 | 2回目 |
|---|---|---|
| A | 3:40 | - |
| B | 15:40(+5) | 1:30（+5） |
| 計 | 24:30 | 9:20 |
2回目の(+5)は問題読解の時間
冷静にできれば、10〜15分でいけたと思う。
【AtCoder-Ruby】ABC098 B - Cut and Count
問題
問題文
英小文字からなる長さ N の文字列 S が与えられます。
この文字列を一箇所で切断して、文字列 X と Y に分割します。
このとき、「 X と Y のどちらにも含まれている文字」の種類数を最大化したいです。
文字列を切断する位置を適切に決めた際の「 X と Y のどちらにも含まれている文字」の種類数の最大値を求めてください。制約
- 2 ≤ N ≤ 100
- |S| = N
- S は英小文字からなる
考えたこと
- 配列を右と左に分けて、片方の配列を uniq しもう片方に含まれる数を数える
- 分ける位置をずらして、算出した数の最大を取る
とりあえず早く解くことを考えて実装したが、1回目は 20分ほどかかった。（寝起きだからかな。。。）
初めの回答
N = gets.strip.to_i a = gets.strip.split('') def chmax(a, b) a > b ? a : b end def f(x, y) res = 0 x.uniq.each do |c| res += 1 if y.include?(c) end res end res = 0 (N - 1).times do |i| res = chmax(f(a[0..i], a[i+1..-1]), res) end puts res
その後、再度 1から実装して 5分30秒で実装できた。
回答
N = gets.strip.to_i a = gets.strip.split('') def chmax(a, b) a > b ? a : b end def f(x, y) x.uniq.select { |n| y.include?(n) }.size end res = 0 (N - 1).times do |i| res = chmax(f(a[0..i], a[(i + 1)..-1]), res) end puts res
考察
文字の uniq 処理があるので、文字列を配列に変換する処理をはじめに実施している
はじめに実装した時に String のスライス処理で行けると思ったがうまくできなことがわかり、ここでタイムロスが出た。
A、B に関しては概ね解けない問題は無くったと思う。
ただ、C の正解率がまだ低いので、A、B は実装スピードを重視する方向で練習しようと思う。
とりあえず、これはやることにする。
- 実装の時間を計測する
- 時間がかかった問題は複数回実装する
理想は A, B 両方で 5分だが、今の実力だと早くて A（2分）、B（10分: 読解5分、実装5分）くらいだろう。
平均で A, B 含めて 15分以内であれば、合格だと思う。
【AtCoder-Ruby】ABC100 B - Ringo's Favorite Numbers
問題文
今日は, 記念すべき AtCoder Beginner Contest 100 が開催される。
そのため, 高橋君はりんごさんに, ある整数をプレゼントしようと思った。
今日のコンテストは「AtCoder Beginner Contest 100」なので, りんごさんは 100 で ちょうど D 回割りきれる正の整数をプレゼントされると喜ぶ.
さて, りんごさんがプレゼントされると喜ぶような整数のうち N 番目に小さいものを求めなさい。制約
- D は 0 , 1 , 2 のいずれかである
- N は 1 以上 100 以下の整数
考えたこと
朝、寝起きにやったこともあり、何言っているかよくわからないので、サンプル2, 3 の結果を見て回答してみた。
D, N = gets.strip.split.map(&:to_i) puts (10 ** (D + 1)) * N
まあ、ダメだよね。（10 を階乗してるし。多分頭回っていなかった。。）
お昼休みに気を取り直して回答
- D は、100で割り切れる回数で「 0 , 1 , 2」
- N は、順番で N番目に小さいもので「1 以上 100 以下の整数」
ああ。。。
- D = 0 のときは割り切れるものがないので、N が答え
- D = 1 の時 100 * N
- D = 2 の時 10000 * N
- 要は (100 ** D) * N
D, N = gets.strip.split.map(&:to_i) puts (100 ** D) * N
一部のテストケースで不正解！
なぜだ。。。
回答を確認
したがって、𝑁 ≤100 を仮定すると、𝑁 ≤99 のとき 𝑁𝑎 = 𝑁 ×100𝐷 が答えとなり、
𝑁 = 100 のとき 101𝑎 = 101 × 100𝐷 が答えになります。
なるほど。100 の判定が必要だった。
回答
D, N = gets.strip.split.map(&:to_i) n = N != 100 ? N : N + 1 puts (100 ** D) * n
考察
この回答だと、200, 300 の時には正解がでない。
方針2, 方針3 での実装が必要。
あとで回答しよう。
【AtCoder-Ruby】ABC117 C - Streamline
問題
問題文
数直線と N 個のコマを用いて 1 人でゲームを行います。
はじめ、これらのコマをそれぞれ好きな整数座標に置きます。
このとき、同じ座標に複数のコマを置いても構いません。
以下の移動を繰り返して、座標 X1, X2, ... , XM の M 個の地点全てをいずれかのコマで訪れることが目的です。移動: コマを 1 つ選び、そのコマの座標を x とする。
そのコマを座標 x + 1 もしくは座標 x − 1 に移動する。
ただし、最初にコマを置いた座標はその時点で訪れたとみなします。
目的を達成するまでに移動を行う回数の最小値を求めてください。制約
- 入力はすべて整数である。
- 1 ≤ N ≤ 10**5
- 1 ≤ M ≤ 10**5
- − 10**5 ≤ X i ≤ 10**5
- X1, X2, ..., XM は全て異なる。
考えたこと
- 各座標の間の距離が小さいところにコマを置いていけば最小の値が見つかる
- コマを置いた座標は訪れたとみなされるため、座標間の距離が長いところにコマを置けばいい
- ようするに
- 座標間の差分のリストソート（降順）
- コマの数 - 1 からのリストの合計が答え
回答
N, M = gets.strip.split.map(&:to_i) a = gets.strip.split.map(&:to_i).sort # ds: distances ds = Array.new(M - 1){0} (M - 1).times { |i| ds[i] = a[i + 1] - a[i] } puts N < M ? ds.sort.reverse[(N - 1)..-1].inject(:+) : 0
考察
今回は自力でとけたので少しホッとした。
少しは、マシになってきた気がする。
参考まで。 けんちょんの競プロ精進記録
【AtCoder-Ruby】ABC127 振返り
まず結果に関しては、以下の通り
A は普通の if 文で実装したが、一瞬三項演算子で一行にしょうかなとか迷った。
基本的にはスピード重視でそのまま提出した。
B は問題の読解に若干手間取った。
C は「ビット演算が早かろう」と思い書いたが、入力が大きい場合文字列操作で時間がかかる問題で沈没。
また、1 を並べるロジックをひねり出すのにも時間がかかったので、失敗後にリカバリーができなかった。。。
N, M = gets.strip.split.map(&:to_i) s = ("1" * N).to_i(2) M.times do l, r = gets.strip.split.map(&:to_i) s = s & (("1" * (r - l + 1)) << ("0" * (l - 1))).to_i(2) end puts ("%0b" % s).count("1")
課題
A に関しては「後は問題を多く解けば早くなると思う」ので、引き続き日々回答を続ける。
B は読解に課題あり。
コンテスト本番では早く解こうと思うあまり、問題文を読むより例から取り掛かりがち。
緊張や焦りがあるのでイメージに起こして情報を整理すること！
C はそもそも取っ掛かりで間違っている。
コンテスト後程なくして「右の最小から左の最大を引く」ということに気がついた。。。
一応回答はこんな感じ。
一回目の回答では res > 0 の判定がなかったのでダメなパターンがあった。
N, M = gets.strip.split.map(&:to_i) ls = [] rs = [] M.times { |i| ls[i], rs[i] = gets.strip.split.map(&:to_i) } res = rs.min - ls.max + 1 puts res > 0 ? res : 0
考察
今回も「ABのみ」の結果ではあったが、「落ち着いてやれば C は取れるな」との感触はあった。
今のペースで進めるが、新しい武器も揃えていこうと思う。
まあ、時間の制約もあるので焦らずに継続していこうと思う。
【AtCoder-Ruby】ABC102 C - Linear Approximation
問題
問題文
すぬけ君は、長さ N の整数列 A を持っています。
すぬけ君は、整数 b を自由に選びます。
この時、 Ai と b + i が離れているとすぬけ君は悲しいです。
より具体的には、すぬけ君の悲しさの値は、次の式で計算されます。
なおここで、 abs(x) は x の絶対値を返す関数です。
- abs(A1 − (b +1)) + abs (A2 − (b + 2)) + ... + abs (AN − (b + N))
すぬけ君の悲しさの値の最小値を求めてください。
制約
- 1 ≤ N ≤ 2 * 10**5
- 1 ≤ Ai ≤ 10**9
- 入力はすべて整数である。
考えたこと
最適な b を求める。配列の位置を引いた値の一番大きいやつ？ではないな。
20分ほど考えて答えを確認
ここで、b を Bi の中央値にするのが最適であることがわかります。
中央値でない場合は、中央値に近づけることで損をしないことからこれはわかります。
さらっと中央値と書いてある。
配列の位置を引いた値をソートして真ん中の数。
回答
N = gets.strip.to_i a = gets.strip.split.each_with_index.map { |c, i| c.to_i - i - 1 }.sort b = a[N / 2] puts a.inject(0) { |sum, n| sum + (n - b).abs }
考察
今回はコードで数え上げの処理を inject に置き換えてみた。
いつもはこんな感じ
sum = 0 N.times { |i| sum += (a[i] - b).abs } puts sum # 今回 # puts a.inject(0) { |sum, n| sum + (n - b).abs }
【AtCoder-Ruby】ABC103 C - Modulo Summation
問題
問題文
N 個の正整数 a1, a2,..., aN が与えられます。
非負整数 m に対して、 f(m) = (m mod a1) + (m mod a2) + ... + ( m mod aN) とします。
ここで、 X mod Y は X を Y で割った余りを表します。
f の最大値を求めてください。制約
- 入力は全て整数である
- 2 ≤N ≤3000
- 2 ≤ai ≤10**5
考えたこと
最大は (a1 - 1) + .. + (an - 1) だが、
このような m があるかどう証明する？
神のお告げはを聞こう。
最小公倍数を LCM で表すことにして
- M = LCM(a1,a2,…,aN)−1 が条件を満たす。あるいは単に
- M=a1a2…aN−1 でもよい。
そうなんだ。
例題で確かめてみる。
[14:37:37 ~]$ irb >> dividend = [7, 46, 11, 20, 11].inject(:lcm) - 1 => 35419 >> [7, 46, 11, 20, 11].each { |n| puts dividend % n } 6 45 10 19 10 => [7, 46, 11, 20, 11] >>
確かにその通りでした。
回答
N = gets.strip.to_i puts gets.strip.split.map(&:to_i).inject(:+) - N
考察
多分本番ではこれ系の問題はすぐに出てこない。
とりあえず、多く問題を解こう。
