金魚亭日常

読書,ガジェット,競技プログラミング

AtCoder ABC #077

1185 -> 1172

C

二分探索するところまでは思いついたが,その後難しく考えすぎて解けなかった.

B より大きいCの個数は毎回求めてたらTLEしたので,前計算する.

AtCoder ABC #077

2017年10月に読んだ本

今月は

Wシリーズ新刊,

数学ガール 積分

食戟のソーマ

を読んだ.

食戟のソーマ読むと,焼きたてジャぱん を読みたくなる.

期間 : 2017年10月
読了数 : 22 冊
ペガサスの解は虚栄か? Did Pegasus Answer the Vanity? (講談社タイガ)
森 博嗣 / 講談社 (2017-10-19)
読了日:2017年10月31日
食戟のソーマ 25 (ジャンプコミックス)
佐伯 俊 , 森崎 友紀 / 集英社 (2017-07-04)
読了日:2017年10月6日
食戟のソーマ 24 (ジャンプコミックス)
佐伯 俊 , 森崎 友紀 / 集英社 (2017-05-02)
読了日:2017年10月6日
食戟のソーマ 23 (ジャンプコミックス)
佐伯 俊 , 森崎 友紀 / 集英社 (2017-03-03)
読了日:2017年10月6日
食戟のソーマ 22 (ジャンプコミックス)
佐伯 俊 , 森崎 友紀 / 集英社 (2016-12-31)
読了日:2017年10月6日
食戟のソーマ 21 (ジャンプコミックス)
佐伯 俊 , 森崎 友紀 / 集英社 (2016-11-04)
読了日:2017年10月6日
食戟のソーマ 20 (ジャンプコミックス)
佐伯 俊 , 森崎 友紀 / 集英社 (2016-09-02)
読了日:2017年10月6日
食戟のソーマ 19 (ジャンプコミックス)
佐伯 俊 , 森崎 友紀 / 集英社 (2016-07-04)
読了日:2017年10月6日
食戟のソーマ 18 (ジャンプコミックス)
佐伯 俊 , 森崎 友紀 / 集英社 (2016-05-02)
読了日:2017年10月6日
食戟のソーマ 17 (ジャンプコミックス)
佐伯 俊 , 森崎 友紀 / 集英社 (2016-03-04)
読了日:2017年10月6日
食戟のソーマ 16 (ジャンプコミックス)
佐伯 俊 , 森崎 友紀 / 集英社 (2016-01-04)
読了日:2017年10月6日
食戟のソーマ 15 (ジャンプコミックス)
附田 祐斗 , 佐伯 俊 / 集英社 (2015-10-03)
読了日:2017年10月7日
食戟のソーマ 14 (ジャンプコミックス)
佐伯 俊 , 森崎 友紀 / 集英社 (2015-08-04)
読了日:2017年10月7日
食戟のソーマ 13 (ジャンプコミックス)
佐伯 俊 , 森崎 友紀 / 集英社 (2015-06-04)
読了日:2017年10月7日
食戟のソーマ 12 (ジャンプコミックス)
佐伯 俊 , 森崎 友紀 / 集英社 (2015-04-03)
読了日:2017年10月7日
食戟のソーマ 11 (ジャンプコミックス)
佐伯 俊 , 森崎 友紀 / 集英社 (2015-03-04)
読了日:2017年10月7日
食戟のソーマ 10 (ジャンプコミックス)
佐伯 俊 / 集英社 (2014-11-04)
読了日:2017年10月8日
食戟のソーマ 9 (ジャンプコミックス)
佐伯 俊 / 集英社 (2014-09-04)
読了日:2017年10月8日
食戟のソーマ 8 (ジャンプコミックス)
森崎 友紀 , 佐伯 俊 / 集英社 (2014-07-04)
読了日:2017年10月8日
食戟のソーマ 7 (ジャンプコミックス)
附田 祐斗 , 佐伯 俊 / 集英社 (2014-04-04)
読了日:2017年10月8日
食戟のソーマ 6 (ジャンプコミックス)
佐伯 俊 / 集英社 (2014-02-04)
読了日:2017年10月8日
数学ガールの秘密ノート/積分を見つめて (数学ガールの秘密ノートシリーズ)
結城 浩 / SBクリエイティブ (2017-06-30)
読了日:2017年10月1日

RubyInstaller2 をビルドする

環境

  • OS: Windows 10 Pro Version 1709 Build 16299.19
  • MSYS2
  • Ruby2.4(RubyInstaller2, ruby 2.4.2p198 (2017-09-14 revision 59899) [x64-mingw32])

普通にビルドする

Ruby Installer 2

bundler 使うので入れる

gem install bundler 

README にある通りに,Inno-Setup (unicode) をインストールして, (git config --global core.autocrlf false しておいた方がよいかも)

set PATH=%PATH%c:\msys64\usr\bin;c:\msys64\mingw64\bin;"c:\Program Files (x86)\Inno Setup 5"
git clone https://github.com/oneclick/rubyinstaller2.git
cd rubyinstaller2
bundle install --path vendor/bundle
bundle exec rake rubyinstaller:ruby-2.4.2-x64

packages/rubyinstaller/recipes/ 以下に生成物ができる

インストールするRubyにパッチを当てる

まず,RubyInstaller2 の pacmanレポジトリを使ってパッチを当てたRuby をビルドする

レポジトリを取ってきて,

git clone https://github.com/oneclick/rubyinstaller2-packages.git

以下のパッチ

mingw-w64-ruby\0007-fix-onedrive-file-ondemand-issue.patch

に保存して,

diff --git a/win32/win32.c b/win32/win32.c
index 62801dae71..7e8afb2ddc 100644
--- a/win32/win32.c
+++ b/win32/win32.c
@@ -4958,7 +4958,7 @@ rb_w32_read_reparse_point(const WCHAR *path, rb_w32_reparse_buffer_t *rp,
        ret = rp->SymbolicLinkReparseBuffer.PrintNameLength;
        *len = ret / sizeof(WCHAR);
    }
-   else { /* IO_REPARSE_TAG_MOUNT_POINT */
+   else if (rp->ReparseTag == IO_REPARSE_TAG_MOUNT_POINT) {
        static const WCHAR *volume = L"Volume{";
        enum {volume_prefix_len = rb_strlen_lit("\\??\\")};
        name = ((char *)rp->MountPointReparseBuffer.PathBuffer +
@@ -4971,6 +4971,9 @@ rb_w32_read_reparse_point(const WCHAR *path, rb_w32_reparse_buffer_t *rp,
        memcmp(name, volume, sizeof(volume) - 1 * sizeof(WCHAR)) == 0)
        return -1;
    }
+   else {
+       return -1;
+   }
    *result = name;
    if (e) {
        if ((char *)name + ret + sizeof(WCHAR) > (char *)rp + bufsize)

PKGBUILD を編集する

  • source に patch ファイルを追加
  • prepare(){} に patch を適用する処理を追加
  • SHA256 hash を更新: ridk exec sh -c "updpkgsums PKGBUILD
diff --git a/mingw-w64-ruby24/PKGBUILD b/mingw-w64-ruby24/PKGBUILD
index 084a994..fc3d144 100644
--- a/mingw-w64-ruby24/PKGBUILD
+++ b/mingw-w64-ruby24/PKGBUILD
@@ -21,6 +21,7 @@ source=("https://cache.ruby-lang.org/pub/ruby/${pkgver%.*}/${_realname}-${pkgver
         0002-use-gnu-printf.patch
         0004-exclude-changelog-from-rdoc.patch
         0006-fix-conversion-warning-win32-powl.patch
+        0007-fix-onedrive-file-ondemand-issue.patch
         ruby.ico
         rubyw.ico)

@@ -31,6 +32,7 @@ sha256sums=('08e72d0cbe870ed1317493600fbbad5995ea3af2d0166585e7ecc85d04cc50dc'
             '578bd0830fe96efc7656c732ec46b0658fc436a7a30d8945cf3b8240797809f0'
             '389236bdca5f283adde9b4b56febcfc25e228716e06a0edc21ea8fd7f27b75fa'
             'e7f83bc6e3b7ddadb5e3b14aa7d3a4e30eb97aea02df38796ca78714ad20e9b7'
+            '4d845e75ea4558bebbce51f6f2c858f9c6db96ca5fd4757dbf07b63c6b9582e9'
             '6c80ba2ca49840e387a08b7fedc6e7acd298ac2ec853155209efb2af20397b22'
             'c30fb04ac0e88ba634daaa811a81ea5a75027646617b895acd14df9518a4a55a')

@@ -40,6 +42,7 @@ prepare() {
   patch -p1 -i ${srcdir}/0002-use-gnu-printf.patch
   patch -p1 -i ${srcdir}/0004-exclude-changelog-from-rdoc.patch
   patch -p1 -i ${srcdir}/0006-fix-conversion-warning-win32-powl.patch
+  patch -p1 --ignore-whitespace -i ${srcdir}/0007-fix-onedrive-file-ondemand-issue.patch

   autoreconf -fi
 }

ビルド(コマンドプロンプトではなくMSYS2から)

cd rubyinstaller2-packages\mingw-w64-ruby24
MINGW_INSTALLS=mingw64 makepkg-mingw -sLf

mingw-w64-x86_64-ruby24-2.4.2-1-any.pkg.tar.xz ができるので,msys64\tmp\rubyinstaller に置く

再びインストーラ生成

ビルドしたRubyを使うようにRake ファイルを編集して再度ビルドする.

diff --git a/recipes/unpack/50-install-msys-packages.rake b/recipes/unpack/50-install-msys-packages.rake
index bddfa89..5290cb4 100644
--- a/recipes/unpack/50-install-msys-packages.rake
+++ b/recipes/unpack/50-install-msys-packages.rake
@@ -8,11 +8,13 @@ file ruby_exe => [self.repo_added] do
   %w[var/cache/pacman/pkg var/lib/pacman].each do |dir|
     mkdir_p File.join(unpackdir, dir)
   end
-
+  require "open3"
+  o, s = Open3.capture2("pacman -Ss #{install_packages.map(&:inspect).join(" ")}")
+  rb_subver = o.split("\n")[0].split(" ")[1]
   msys_sh <<-EOT
     mount #{unpackdir_abs.inspect} #{pmrootdir.inspect} &&
     pacman --root #{pmrootdir.inspect} -Sy &&
-    pacman --root #{pmrootdir.inspect} --noconfirm -S #{install_packages.map(&:inspect).join(" ")};
+    pacman --root #{pmrootdir.inspect} --noconfirm -U /tmp/rubyinstaller/#{install_packages.map(&:inspect).join(" ")}-#{rb_subver}-any.pkg.tar.xz;
     umount #{pmrootdir.inspect}
   EOT
   touch ruby_exe

出来た 7zip を展開してPATHを通して終了.

AtCoder ABC #076

Rating は変動なしで 1185

A

式変形して  2 G - R を出力

B

両方の操作の結果を毎回比べて小さい方を取る.

C

左から順番に文字列  S を走査していって, T と一致させることができる部分が見つかったら,その部分を  T で置換したものを配列に入れる. 終わったらソートして辞書順最小のものを得て,残りの ?a で置換して出力. 1回目 WA したのは 文字列を clone() してなかったせい.

テストケースが弱くて間違った解法で通る,みたいな話があったみたいだけど,まぁそんなこともたまにはあるし,長い目で見れば妥当なRatingに収束して行くので別にいいでしょう,という感想.

D

これは解けなかった.

加速度として考えるのは -1, 0, 1 のみで,道のりは台形・長方形・三角形の面積として求められるので,各区間についてグラフを作ればよい,ってとこまでは考えたけど,実装できそうに無かったので諦め. 片手間にやってると弱気になってよくない.

AtCoder ABC #076

Code Festival 2017 予選 C

CODE FESTIVAL 2017 qual C - CODE FESTIVAL 2017 qual C | AtCoder

A

文字列を2個ずつ処理. 今回は Array にして each_cons() を使った.

B

差が1以下なので,とれる範囲は元の数字とその前後の3通り. 一つでも偶数のものがあればいいので,全通りの  3^N から全て奇数のものを引く.

元の数字が偶数なら前後は奇数になるので 2通り,元の数字が奇数なら前後は偶数になるので1通り.

なので,奇数が m 個あるとすると  2^m を引く.

C

最初は,

x を除いた文字列が回文じゃなかったら "No",回文だったら,真ん中の文字の位置がとれるので ... みたいな感じで考えていて,無理だった.

普通に両サイドから判定して行く.

Code Festival 2017 予選 C

AtCoder ARC #049 B - 高橋ノルム君

B: 高橋ノルム君 - AtCoder Regular Contest 049 | AtCoder

コストを固定して,二分探索.

何回するかがパッと思いつかないが, 10^8 ぐらいなら  2^5 回ぐらいで十分らしい.

AtCoder ARC #049 B - 高橋ノルム君