端末を特定のディレクトリで立ち上げる(Ubuntu)
$ gnome-terminal --working-directory=/path/to/dir
Linux の Thunderbird の移行
元のデータ保存先は 922vkyux.default
で、これをコピーしてきて続けて使いたい。しかし default-release とか、よくわからないことになっている。
Linux インストール時の .thunderbird/profiles.ini の内容は
[Profile1] Name=default IsRelative=1 Path=o2l4hc2s.default Default=1 [InstallFDC34C9F024745EB] Default=6scqjmh7.default-release Locked=1 [Profile0] Name=default-release IsRelative=1 Path=6scqjmh7.default-release [General] StartWithLastProfile=1 Version=2
こんな感じ。
これをこう書き換えた。
[Profile0] Name=defaul IsRelative=1 Path=922vkyux.default Default=1 [General] StartWithLastProfile=1 Version=2
これで OK だった。
キーエンス プログラミング コンテスト 2020
https://atcoder.jp/contests/keyence2020
過去問。
A
h, w, n = readlines.map(&:to_i)
puts (n / [h, w].max.to_f).ceil
B
imos法かと思ったが、ちがっていた。
n = gets.to_i data = n.times.map {gets.split.map(&:to_i)}.map {|x, l| [x - l, x + l]} result = 0 right_min = -Float::INFINITY data.sort {|a, b| a[1] <=> b[1]}.each do |arm| next if right_min > arm[0] result += 1 right_min = arm[1] end puts result
「区間スケジューリング問題」なのだそうである。知らなかった。コードはこれを参考にした。
区間を「終端が早い順」にソートして、とれる順にとる Greedy (貪欲法)で解くことができる
そうである。
C
n, k, s = gets.split.map(&:to_i) a = Array.new(n) n.times do |i| a[i] = if i < k s else s == 1 ? s + 1 : s - 1 end end puts a.join(" ")
皆んなかしこいなあ。思いつかなかった。K個Sを置いて、あとは残りの部分列でSができないようにすると。
ABC151
https://atcoder.jp/contests/abc151
過去問。
A
puts gets.chomp.succ
B
n, k, m = gets.split.map(&:to_i) sum = gets.split.map(&:to_i).inject(&:+) target = m * n - sum result = case when target < 0 then 0 when target > k then -1 else target end puts result
C
'WA'
だけの問題はペナルティにカウントされないことになかなか気づかなかった。'AC'
が出て初めてカウントしないといけない。
n, m = gets.split.map(&:to_i) ps = m.times.map {gets.split} memo = Array.new(n + 1) penalty_memo = Hash.new(0) score = penalty = 0 ps.each do |p, s| pn = p.to_i #problem number next if memo[pn] case s when "AC" score += 1 penalty += penalty_memo[pn] memo[pn] = true else penalty_memo[pn] += 1 end end puts "#{score} #{penalty}"
D
最初はTLE。それから、まさかの Ruby 2.3.3 なのにハマった。
方針がまちがっていた。スタートとゴールを設定して二重ループでやっていたが、よく考えてみたらスタートを設定してあとはいちばん遠いところへ行けばよいのだ。迷路を解くのはBFS。781ms。
class Position def initialize(x = 0, y = 0, count = 0) @x = x @y = y @count = count end attr_reader :x, :y, :count end h, w = gets.split.map(&:to_i) maze = h.times.map {gets.chomp} field = nil Position.send(:define_method, :succ) do x = @x + 1 y = @y if x >= w x = 0 y += 1 return false if y >= h end Position.new(x, y) end Position.send(:define_method, :move) do |dir| x, y = @x, @y dx, dy = [[1, 0], [0, -1], [-1, 0], [0, 1]][dir] x += dx y += dy return false if x >= w || x < 0 || y >= h || y < 0 return false if field[y][x] != "." Position.new(x, y, @count + 1).mark end Position.send(:define_method, :mark) do field[@y][@x] = "*" self end solve_maze = ->(start) { return 0 if maze[start.y][start.x] == "#" field = maze.map(&:dup) max = 0 q = [start.mark] while (po = q.shift) max = po.count if po.count > max 4.times do |dir| nxt = po.move(dir) q << nxt if nxt end end max } start = Position.new max = 0 loop do hosuu = solve_maze.(start) max = hosuu if hosuu > max break unless (start = start.succ) end puts max
E
TLE。
LIMIT = 10 ** 9 + 7 def factorial(n) result = 1 2.upto(n) {|i| result *= i} result end def permutation(a, b) [*1..a].last(b).inject(1, &:*) end def combination(a, b) permutation(a, b) / factorial(b) end n, k = gets.split.map(&:to_i) as = gets.split.map(&:to_i).sort sum = 0 if k == 1 puts 0 exit end (0..n - k).each do |min| (min + k - 1..n - 1).each do |max| f = as[max] - as[min] sum += f * combination(max - min - 1, k - 2) end end puts sum % LIMIT
TLE。
LIMIT = 10 ** 9 + 7 n, k = gets.split.map(&:to_i) as = gets.split.map(&:to_i).sort acc = 1 factorial = [1] + (1..n).map {|i| acc *= i} factorial_r = factorial.map {|a| Rational(1, a)} combination = ->(a, b) {factorial[a] * factorial_r[b] * factorial_r[a - b]} result = 0 (n - k + 1).times {|i| result -= as[i] * combination.(n - i - 1, k - 1)} as.reverse! (n - k + 1).times {|i| result += as[i] * combination.(n - i - 1, k - 1)} puts result.to_i % LIMIT
ABC152
https://atcoder.jp/contests/abc152
過去問。
A
n, m = gets.split.map(&:to_i) puts (n == m) ? "Yes" : "No"
B
a, b = gets.split.map(&:to_i) result = a.to_s * b tmp = b.to_s * a result = tmp if result > tmp puts result
C
これはすぐに思いついた。
n = gets.to_i ps = gets.split.map(&:to_i) min = ps.first count = 0 ps.each do |p0| if p0 <= min count += 1 min = p0 end end puts count
D
とりあえず総当り。もちろんこれは提出していない。
n = io.gets.to_i count = 0 (1..n).each do |i| il, ir = i.to_s[0], i.to_s[-1] (1..n).each do |j| jl, jr = j.to_s[0], j.to_s[-1] count += 1 if il == jr && ir == jl end end puts count
これで 1~200 を計算してみる。
[[1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [6, 6], [7, 7], [8, 8], [9, 9], [10, 9], [11, 12], [12, 12], [13, 12], [14, 12], [15, 12], [16, 12], [17, 12], [18, 12], [19, 12], [20, 12], [21, 14], [22, 17], [23, 17], [24, 17], [25, 17], [26, 17], [27, 17], [28, 17], [29, 17], [30, 17], [31, 19], [32, 21], [33, 24], [34, 24], [35, 24], [36, 24], [37, 24], [38, 24], [39, 24], [40, 24], [41, 26], [42, 28], [43, 30], [44, 33], [45, 33], [46, 33], [47, 33], [48, 33], [49, 33], [50, 33], [51, 35], [52, 37], [53, 39], [54, 41], [55, 44], [56, 44], [57, 44], [58, 44], [59, 44], [60, 44], [61, 46], [62, 48], [63, 50], [64, 52], [65, 54], [66, 57], [67, 57], [68, 57], [69, 57], [70, 57], [71, 59], [72, 61], [73, 63], [74, 65], [75, 67], [76, 69], [77, 72], [78, 72], [79, 72], [80, 72], [81, 74], [82, 76], [83, 78], [84, 80], [85, 82], [86, 84], [87, 86], [88, 89], [89, 89], [90, 89], [91, 91], [92, 93], [93, 95], [94, 97], [95, 99], [96, 101], [97, 103], [98, 105], [99, 108], [100, 108], [101, 113], [102, 115], [103, 117], [104, 119], [105, 121], [106, 123], [107, 125], [108, 127], [109, 129], [110, 129], [111, 136], [112, 138], [113, 140], [114, 142], [115, 144], [116, 146], [117, 148], [118, 150], [119, 152], [120, 152], [121, 161], [122, 163], [123, 165], [124, 167], [125, 169], [126, 171], [127, 173], [128, 175], [129, 177], [130, 177], [131, 188], [132, 190], [133, 192], [134, 194], [135, 196], [136, 198], [137, 200], [138, 202], [139, 204], [140, 204], [141, 217], [142, 219], [143, 221], [144, 223], [145[152, 250], [153, 252], [154, 254], [155, 256], [156, 258], [157, 260], [158, 26, 289], [166, 291], [167, 293], [168, 295], [169, 297], [170, 297], [171, 316], [172, 318], [173, 320], [174, 322], [175, 324], [176, 326], [177, 328], [178, 330], [179, 332], [180, 332], [181, 353], [182, 355], [183, 357], [184, 359], [185, 361], [186, 363], [187, 365], [188, 367], [189, 369], [190, 369], [191, 392], [192, 394], [193, 396], [194, 398], [195, 400], [196, 402], [197, 404], [198, 406], [199, 408], [200, 408]]
これを眺めていて、漸化式を計算すればよいことがわかった。つまり、n が 1 増えるときに結果がいくつ増えるか考える。O(n)。
def calc(n) result = 0 (1..n).each do |i| if i < 10 result += 1 else str = i.to_s digits = str.length - 2 next if str[-1] == "0" if str[0] < str[-1] #i=1263だったら、13, 1_3みたいなやつ result += [0, 1, 11, 111, 1111][digits] * 2 elsif str[0] > str[-1] #i=4321だったら、14, 1_4, 1__4みたいなやつ result += [1, 11, 111, 1111, 11111][digits] * 2 else #i=1321だったら、1, 11, 1_1みたいなやつ result += [1, 2, 12, 112, 1112][digits] * 2 #i=1321だったら、1001 ~ 1__1 ~ 1321みたいなやつで、1321は重複するので-1する result += (str[1..-2].to_i + 1) * 2 - 1 end end end result end puts calc(gets.to_i)
まずまずうまく解けたと思う。207ms。
E
全体の最小公倍数を求める。あとはそれぞれの a で割って足すだけ。
LIMIT = 10 ** 9 + 7 n = gets as = gets.split.map(&:to_i) result = 0 lcm0 = as.inject(1) {|acc, i| acc.lcm(i)} as.each {|ai| result += lcm0 / ai} puts result % LIMIT
誰でも思いつく凡庸な方法ですぐにクリア。大きな数を簡単に扱えるのは Ruby の恩恵である。でも、時間は 1319 ms で全然よくない感じだが、調べてみると Ruby だとまあ皆んな同じようなものか。
演奏家 / 作曲家
ピアノ・トリオ
- シトコヴェツキー・トリオ Sitkovetsky Trio (NML)
ピアノ
- ヴァネッサ・ベネッリ・モーゼル Vanessa Benelli Mosell (NML)
- セドリック・ペシャ Cédric Pescia (NML)
- クレール=マリー・ル・ゲ Claire-Marie Le Guay (NML)
- ピ=シェン・チェン or チェン・ピチェン Pi-hsien Chen (NML)
- レオン・マッコウリー Leon McCawley (NML)
- アレクサンドラ・パパステファノウ Alexandra Papastefanou (NML)
- オリヴィエ・カヴェー Olivier Cavé (NML)
- エリック・ル・サージュ Eric Le Sage (NML)
- マルセル・メイエ Marcelle Meyer (NML)
AOJ(問題集)23
0220 Binary Digit A Doctor Loved
小数の2進表現かあ。勉強になるなあ。なお、10進表現で循環小数でなくとも、2進表現で循環小数になる場合がある。
def calc(r, str = "") return str if str.length > 4 a = r * 2 b = a.to_i str += b.to_s c = a - b if c.zero? return str else calc(c, str) end end until (n = gets.to_f.rationalize) < 0 integer_part = n.to_i decimal_part = n - integer_part result = "NA" str = integer_part.to_s(2) if str.length <= 8 str = str.rjust(8, "0") tmp = calc(decimal_part) if tmp.length <= 4 result = str + "." + tmp.ljust(4, "0") end end puts result end
0221 FizzBuzz
発言データを一気読みしていなくてハマった。0.24秒。
e = Enumerator.new do |y| i = 1 loop do y << case when (i % 15).zero? then "FizzBuzz" when (i % 3).zero? then "Fizz" when (i % 5).zero? then "Buzz" else i.to_s end i += 1 end end until (given = gets.chomp) == "0 0" m, n = given.split.map(&:to_i) data = n.times.map {gets.chomp} table = Array.new(m, true) pointer = 0 count = m inc = ->{ pointer += 1 pointer = 0 if pointer >= m } data.each do |said| break if count == 1 inc.() until table[pointer] if said != e.next table[pointer] = false count -= 1 end inc.() end puts table.map.with_index {|a, i| a ? (i + 1).to_s : nil}.compact.join(" ") e.rewind end
これで0.21秒。あまり変わらないな。
e = Enumerator.new do |y| i = 1 loop do y << case when (i % 15).zero? then "FizzBuzz" when (i % 3).zero? then "Fizz" when (i % 5).zero? then "Buzz" else i.to_s end i += 1 end end until (given = gets.chomp) == "0 0" m, n = given.split.map(&:to_i) data = n.times.map {gets.chomp} table = (1..m).map(&:itself) pointer = 0 data.each do |said| if said != e.next table.delete_at(pointer) break if table.size == 1 else pointer += 1 end pointer = 0 if pointer >= table.size end puts table.join(" ") e.rewind end
0225 Kobutanukitsuneko
時間切れ。素朴な DFS。
loop do n = io.gets.to_i break if n.zero? words = n.times.map { io.gets.chomp } goal = words[0][0] try = ->(num, word) { if num.zero? word[-1] == goal else words.delete(word) words.select { |w| word[-1] == w[0] }.each do |w| f = try.(num - 1, w) return f if f end false end } puts try.(n - 1, words[0]) ? "OK" : "NG" end
0226 Hit and Blow
loop do r, a = gets.split.map(&:chars) break if r == ["0"] && a == ["0"] r1, a1 = [], [] hit = 0 r.size.times do |i| if r[i] == a[i] hit += 1 else r1 << r[i] a1 << a[i] end end blow = (r1 & a1).size puts "#{hit} #{blow}" end
0227 Thanksgiving
loop do n, m = gets.split.map(&:to_i) break if n.zero? && m.zero? ps = gets.split.map(&:to_i).sort.reverse price = 0 ps.each_slice(m) do |ary| if ary.size == m price += ary[0, m - 1].sum else price += ary.sum end end puts price end
0228 Seven Segments
Pats = %w(0111111 0000110 1011011 1001111 1100110) + %w(1101101 1111101 0100111 1111111 1101111) loop do n = gets.to_i break if n < 0 ds = n.times.map { gets.to_i } disp = 0 ds.each do |d| pat = Pats[d].to_i(2) puts "%07b" % (pat ^ disp) disp = pat end end
0229 Big Hit !
loop do b, r, g, c, s, t = gets.split.map(&:to_i) break if b + r + g + c + s + t == 0 medals = 100 bonus = ->{ medals += 15 + 1 } b.times do medals += 15 5.times { bonus.() } end r.times do medals += 15 3.times { bonus.() } end medals += 7 * g medals += 2 * c medals += 3 * s medals -= 3 * t puts medals end
Ruby でタイマーを作った
Gem 'kaki-utils' に入れた。
timer.rb
module Utils #簡易タイマー def timer(minutes) end_time = Time.now + (minutes * 60).to_i while Time.now < end_time print "\e[2K\e[1G" + "left: #{(end_time - Time.now).to_i} sec." sleep(1) end Utils.bell puts end module_function :timer end
使用例。30秒後にベルが鳴る。(Ubuntu のみ)
$ bundle exec irb irb(main):001:0> require "kaki/utils" => true irb(main):002:0> Utils.timer(0.5) left: 0 sec. => nil
(個人的)LaVie の Ubuntu 18.04 のファイルシステムが死んだので修復
Ubuntu が立ち上がらなくなってしまったので、Kubuntu のインストール・ディスクをお試しモードで立ち上げて修復する。
Ubuntu は /dev/sda3 だということを確認して、fsck で修復。
kubuntu@kubuntu:/$ umount /dev/sda3 kubuntu@kubuntu:/$ fsck /dev/sda3 -p fsck from util-linux 2.28.2 fsck.ext2: Permission denied while trying to open /dev/sda3 You must have r/w access to the filesystem or be root kubuntu@kubuntu:/$ sudo fsck /dev/sda3 -p fsck from util-linux 2.28.2 /dev/sda3 contains a file system with errors, check forced. /dev/sda3: Inodes that were part of a corrupted orphan linked list found. /dev/sda3: UNEXPECTED INCONSISTENCY; RUN fsck MANUALLY. (i.e., without -a or -p options)
kubuntu@kubuntu:/$ sudo fsck /dev/sda3 fsck from util-linux 2.28.2 e2fsck 1.43.3 (04-Sep-2016) /dev/sda3 contains a file system with errors, check forced. Pass 1: Checking inodes, blocks, and sizes Inodes that were part of a corrupted orphan linked list found. Fix<y>? yes Inode 14418682 was part of the orphaned inode list. FIXED. Inode 14419665 was part of the orphaned inode list. FIXED. Inode 14419758 was part of the orphaned inode list. FIXED. Inode 14419776 was part of the orphaned inode list. FIXED. Inode 14423215 was part of the orphaned inode list. FIXED. Inode 14423281 was part of the orphaned inode list. FIXED. Inode 14423330 was part of the orphaned inode list. FIXED. Inode 14423410 was part of the orphaned inode list. FIXED. Inode 20709604 was part of the orphaned inode list. FIXED. Inode 21758134 was part of the orphaned inode list. FIXED. Inode 21758255 was part of the orphaned inode list. FIXED. Inode 21759035 was part of the orphaned inode list. FIXED. Inode 21764033 was part of the orphaned inode list. FIXED. Pass 2: Checking directory structure Pass 3: Checking directory connectivity Pass 4: Checking reference counts Pass 5: Checking group summary information Block bitmap differences: -196672 -(11081728--11083775) -(11085824--11087871) -(11089920--11091967) -(11094016--11096063) -(11098112--11100159) -(11102208--11104255) -(11106304--11108062) -82870390 -83039424 -83039568 -(83643970--83643985) -(83643994--83644009) -(83644068--83644075) -(83664452--83664459) -83664619 -83664890 -(83946396--83946399) -(85817921--85817928) -85818358 -(92887458--92887465) Fix<y>? yes Free blocks count wrong for group #6 (32089, counted=32090). Fix<y>? yes Free blocks count wrong for group #338 (868, counted=14915). Fix<y>? yes Free blocks count wrong for group #2529 (26184, counted=26185). Fix<y>? yes Free blocks count wrong for group #2534 (13904, counted=13906). Fix<y>? yes Free blocks count wrong for group #2552 (9182, counted=9222). Fix<y>? yes Free blocks count wrong for group #2553 (9769, counted=9779). Fix<y>? yes Free blocks count wrong for group #2561 (10796, counted=10800). Fix<y>? yes Free blocks count wrong for group #2618 (1808, counted=1817). Fix ('a' enables 'yes' to all) <y>? yes to all Free blocks count wrong for group #2834 (18779, counted=18787). Fix? yes Free blocks count wrong (63838170, counted=63852292). Fix? yes Inode bitmap differences: -14417977 -14418682 -14419665 -14419758 -14419776 -14423215 -14423281 -14423330 -14423410 -20709604 -21758134 -21758255 -21759035 -21764033 Fix? yes Free inodes count wrong for group #1760 (5, counted=14). Fix? yes Free inodes count wrong for group #2528 (1718, counted=1719). Fix? yes Free inodes count wrong for group #2656 (1995, counted=1999). Fix? yes Free inodes count wrong (22957171, counted=22957185). Fix? yes /dev/sda3: ***** FILE SYSTEM WAS MODIFIED ***** /dev/sda3: 1094527/24051712 files (0.4% non-contiguous), 32339114/96191406 blocks kubuntu@kubuntu:/$
これで立ち上がるようになった。
Ubuntu で unattended-upgrades を無効にする
apt upgrade とかが出来なくなるので、unattended-upgrades を無効にしたい。
$ sudo apt install -y unattended-upgrades $ sudo dpkg-reconfigure --priority=low unattended-upgrades Replacing config file /etc/apt/apt.conf.d/20auto-upgrades with new version
訊かれる質問には「No」を選択する。