ABC146C - Buy an Integerを二分探索で解いてみた

40代文系社内SEが、AtCoder Beginner Contest 146 C - Buy an IntegerをCommon Lispで解いてみました。

まず問題文を見ます。
1以上10の9乗以下の整数のうち、$A \times N + B \times d(N) \le X$を満たす最大の数$N$を求める問題です。
問題文の時点で1から順番に試していく方法は使えないことがわかります。
二分探索であれば、$O(\log N)$で間に合うので二分探索を使う方向で考えます。

次に制約をみますが、特に方針に影響はなさそうです。

問題文の式から、整数が大きくなると値段も高くなることがわかります。
整数をひとつも買えないときは$0$を返すというところを少し読み替えて、商品に$0$を追加し、常に購入できるとします。
また、絶対に購入できない数として$10^9+1$を商品に追加します。
こうすることで、途中で条件を満たさなくなる単調性のある数列を用意できました。

あとは二分探索で答えを求めます。

(let* ((a (read))
       (b (read))
       (x (read)))

  (labels ((cost (n)
             ;; 代金を計算する
             (+ (* a n)
                (* b (length (format nil "~A" n)))))

           (bsearch (min max)
             ;; 購入できる最大の整数を二分探索する
             (if (= (1+ min) max)
                 min
                 (let ((mid (+ min (floor (- max min) 2))))
                   (if (<= (cost mid) x)
                       (bsearch mid max)
                       (bsearch min mid))))))

    (format t "~A~%" (bsearch 0 (1+ (expt 10 9))))))
  

AtCoder Beginner Contestを解いてみたリスト

ABC478C - Sort Subarrayを解いてみた

40代文系社内SEが、AtCoder Beginner Contest 478 C - Sort SubarrayをCommon Lispで解いてみました。

まず問題文を見ます。
数列の一部を昇順に並べ替えることで、数列全体が昇順になるか判定する問題です。
最初に思いついた方法としては、並べ替える範囲をずらしながら並べ替え、全体が昇順になっているか判定するという方法です。計算量が$O(N^2)$になるので、$N \le 10^4$までなら採用できます。

次に制約を見ます。
$N$の最大値が$2 \times 10^5$なので、上で書いた方法では間に合いません。残念。
さらに考察をすると、数列を3つの部分に分けられることに気が付きました。操作によって並べ替えられる部分と、その両側の並べ替えられない部分です。この並べ替えられない部分の要素数を$N$から引いた値が$K$以下であれば、問題文の条件を満たすことになります。

並べ替えられない部分の要素数を数えるには、$A$と全体を昇順でソートした$A$を比較し、値が変わっていない要素を数えれば求められます。計算量は$O(N)$です。

以上より、以下の手順で解きます。

1. $A$のコピーを作成し、昇順でソートする
2. 先頭から$A$とコピーを比較し、値が一致するものを数える
3. 末尾から$A$とコピーを比較し、値が一致するものを数える
4. $N$から上の2,3で数えた値を引いた値が$K$以下のとき、条件を満たすと判定する

(let* ((n (read))
       (k (read))
       (a (make-array n)))

  (loop for i from 0 below n
        do (setf (aref a i) (read)))

  (let ((copy-a (copy-seq a))
        (count-l 0)
        (count-r 0))
    ;; コピーしたAを昇順にソート
    (sort copy-a #'<)

    ;; ソート前後で値が変わらない要素を数列の先頭から数える
    (loop for i from 0 below n
          for ai = (aref a i)
          for copy-ai = (aref copy-a i)
          while (= ai copy-ai)
          do (incf count-l))

    ;; ソート前後で値が変わらない要素を数列の末尾から数える
    (loop for i from (1- n) downto 0
          for ai = (aref a i)
          for copy-ai = (aref copy-a i)
          while (= ai copy-ai)
          do (incf count-r))

    (format t "~:[No~;Yes~]~%" (<= (- n count-l count-r) k))))
  

ABC197C - ORXORをビット全探索で解いてみた

40代文系社内SEが、AtCoder Beginner Contest 197 C - ORXORをCommon Lispで解いてみました。

まず問題文を見ます。
数列$A$をいくつかのグループに分け、グループ内で$\mathrm{OR}$を計算します。さらに、得られた値の$\mathrm{OR}$を計算します。
グループの分け方によって$\mathrm{XOR}$で得られる値が変わるので、その最小値を求める問題です。
等しい値の$\mathrm{XOR}$は0になるので、すべてのグループが同じ値になれば最小になりますが、できるだけ小さくする方法はちょっと見当もつきません。

次に制約を見ます。
$N$の最大値が20となっているので、ビット全探索なら$2^{20}=1048576$なので使えるかもしれません。
ビット全探索で解くとすると、何をビットで表現するかが問題になります。
ここで私が思いついたのは、壁をビットで表現する方法です。
数列$A$をグループ化するという部分を、数の間に壁を置くと読み替え、置く/置かないをビットで表現する方法です。
壁の設置数は、最大で$N-1$になります。

例えば入力例1であれば、

• $(0)_{10}=(00)_2$のとき、壁を置かずに全体を1つのグループとする
• $(1)_{10}=(01)_2$のとき、5と7の間に壁を置き、1,5と7に分ける
• $(2)_{10}=(10)_2$のとき、1と5の間に壁を置き、1と5,7に分ける
• $(3)_{10}=(11)_2$のとき、各数の間に壁を置き、すべて別のグループとする

$(2)_{10}=(10)_2$のときのイメージを以下に示します。

計算量はビット全探索の$2^N$と、それぞれのパターンでORXORの計算する$N$で全体で$O(2^N \times N)$となり、最大$20971520$で、間に合いそうです。

(let* ((n (read))
       (a (make-array n)))

  (loop for i from 0 below n
        do (setf (aref a i) (read)))

  (loop for b from 0 below (expt 2 (1- n))
        for ors = (loop with temp-ors = nil
                        with temp-or = 0
                        for i from 0 below n
                        do (setf temp-or (logior temp-or (aref a i)))
                           (when (or (= i (1- n))
                                     (logbitp i b))
                             (push temp-or temp-ors)
                             (setf temp-or 0))
                        finally
                           (return temp-ors))
        minimize (reduce #'logxor ors)
          into it
        finally
           (format t "~A~%" it)))
  

制約からアルゴリズムを推測し、問題を解くことができました。

AtCoder Beginner Contestを解いてみたリスト

ABC212C - Min Differenceを二分探索で解いてみた

40代文系社内SEが、AtCoder Beginner Contest 212 C - Min Differenceを解いてみました。

まず問題文を見ます。

$A$と$B$の2つの数列から数値を選んだときの差の最小値を求める問題です。

同じ数値が両方に含まれていると、答えは$0$になります。

全探索すれば答えは出ますが、C問題ですし全探索では間に合わないでしょう。

次に制約を見ます。

$1 \le N, M \le 2 \times 10^5$なので、予想通り全探索$O(NM)$では間に合いません。

$O(N \log M)$なら間に合うので、二分探索が使えないか考えます。

まず、数列の並び順については何も記載されていないのでソートが必要になりますが、ソートの計算量は$O(N \log N)$なので、入力から読み込んだあとで1回だけソートすれば問題ありません。

次に、差の最小値については、$A$から選んだ値($A_i$)以上という条件で$B$を二分探索します。一致する数値があれば$0$が答えになり、そうでなければ$A_i$より小さい数値の最大値か、$A_i$より大きい数値の最小値のどちらかとの差が答えになります。

以上より、以下の手順で解きます。

1. $B$をソートする
2. $A$から数値を順番に選択し、$A_i$とする
3. $B$から$A_i$以上の値を二分探索で検索する
4. $A_i$未満の最大値と$A_i$との差の絶対値と、$A_i$以上の最小値と$A_i$との差の絶対値のより小さい方を記録する
5. 4で記録した数値の最小値を答えとする

Common Lispによる実装例

(let* ((n (read))
       (m (read))
       (a (make-array n :initial-contents (loop repeat n collect (read))))
       (b (make-array m :initial-contents (loop repeat m collect (read)))))

  (sort b #'<)

  (labels ((bsearch (ai &optional (l -1) (r m))
             (if (= (1+ l) r)
                 l
                 (let ((mid (+ l (floor (- r l) 2))))
                   (if (< (aref b mid) ai)
                       (bsearch ai mid r)
                       (bsearch ai l mid))))))

    (loop for ai across a
          for l = (bsearch ai)
          minimize (cond ((= l -1)
                          (abs (- (aref b 0) ai)))
                         ((= l (1- m))
                          (abs (- (aref b l) ai)))
                         (t
                          (min (abs (- (aref b l) ai))
                               (abs (- (aref b (1+ l)) ai)))))
            into it
          finally
             (format t "~A~%" it))))

二分探索の結果が$B$の両端になるときだけ少し注意が必要です。

AtCoder Beginner Contestを解いてみたリスト

ABC175C - Walking Takahashiを解いてみた

40代文系社内SEが、AtCoder Beginner Contest 175 C - Walking Takahashiを解いてみました。

まず問題文をみます。

座標$X$にいる高橋君をできるだけ原点に近づけるように移動させると、どこまで近づけることができるかという問題です。

移動には距離($D$)と回数($K$)の制限があります。

次に制約をみます。

$1 \le K \le 10^{15}$より、愚直に移動を繰り返すとTLEになります。

まず、問題を単純にするためにXが負の値のときは$-1$を掛けて正の値にします。

次に高橋君を原点を超えない範囲で負の方向に移動し、その座標を$G$とします。このとき、$G$を引き算で求めようとすると$O(K)$で間に合わないので割り算を使います。

移動回数: $X \div D$

$G$: $X - (D \times 移動回数)$

この時点で移動回数を使い切ったとき、$G$が答えになります。

まだ移動回数が残っているとき、$G$とさらに1回だけ負の方向に移動した座標を往復することになります。すなわち、残りの移動回数が偶数であれば$G$が答えになり、奇数であれば$G$引く$D$の絶対値が答えになります。

(let* ((x (read))
       (k (read))
       (d (read)))
  ;; 単純化するためにxを正の値にそろえる
  (when (< x 0)
    (setf x (* x -1)))

  ;; できるだけ原点に近づく
  (let* ((move-count (min k (floor x d)))
         (g          (- x (* d move-count))))
    (cond ((zerop (- k move-count))
           ;; これ以上移動できないとき
           (format t "~A~%" g))
          ((oddp (- k move-count))
           ;; 残りの移動回数が奇数のとき
           (format t "~A~%" (abs (- g d))))
          (t
           ;; 残りの移動回数が偶数のとき
           (format t "~A~%" g)))))

ABC154D - Dice in Lineを解いてみた

40代文系社内SEがAtCoder Beginner Contest 154 D - Dice in Lineを解いてみました。

まず問題文を見ます。

期待値を求め、合計を計算し、さらに最大値を求めると。$N$個から$K$個の合計を計算することになるので、愚直に計算すると$O(NK)$となるのでおそらくTLEになるでしょう。

次に制約を見ます。

$1 \leq N \leq K \leq 200000$ということで、やはり期待値の合計を計算するところは工夫が必要です。正$1000$面体のサイコロはほぼ球になる気がします。出目がわかりにくそう。

さて、解き方についてですが、まず期待値についてはサイコロの目をすべて合計して面数で割ります。

$1$から$K$までの合計を計算するには、$(1 + K) \times K \div 2$を使えば$O(1)$で求められます。例えば、一般的な正六面体の場合は、$(1 + 6) \times 6 \div 2 = 21$となります。

次に$N$個から$K$個の合計を計算するところですが、「連続する$K$個」というところがポイントです。まず先頭$K$個の合計を求め、合計1とします。合計2を求めるには、合計1に$K+1$個目の値を足し、1個目の値を引くことで$O(1)$で求められます。

例えば、入力例1では以下のようになります。

合計1: $1.0 + 1.5 + 1.5 = 4.0$
合計2: $4.0 + 2.5 - 1.0 = 5.5$
合計3: $5.5 + 3.0 - 1.5 = 7.0$

以上より、以下の手順で解きます。

1. 各サイコロの期待値を計算する
2. $K$個の期待値の合計を計算する
3. 期待値の合計の最大値をとる

(defun solve ()
  (let* ((n (read))
         (k (read))
         (p (make-array n :initial-contents (loop repeat n collect (read))))
         (q (make-array n)))
    (loop for i from 0 below n
          for p-i = (+ (aref p i) 0d0)
          do (setf (aref q i) (if (= p-i 1)
                                  1
                                  (/ (* (1+ p-i) p-i) 2 p-i))))
    (loop with a = 0
          for i from 0 below n
          for qi = (aref q i)
          maximize (progn
                     (incf a qi)
                     (when (>= (- i k) 0)
                       (decf a (aref q (- i k))))
                     a)
            into it
          finally
             (format t "~,10F~%" it))))

(solve)

0d0は、倍精度浮動小数点数で計算するために使用しています。

ABC141D - Powerful Discount Ticketsを優先度付きキューで解いてみた

40代文系社内SEがAtCoder Beginner Contest 141 D - Powerful Discount Ticketsを解いてみました。

まず問題文をみます。

半額　小数点以下切り捨て　になる割引券という夢のような設定です。それって最終的には0円もありえる？と思ったら入力例3にありました。

割引前の金額に対して割合で値引きをするので、割引前の金額が高いものからチケットを使用していきたいところです。問題には、「順番に購入する」とありますが、購入前のシミュレーションと考えれば購入順は気にしなくてよさそうです。

そのような要件に応えるようなアルゴリズムとしては、優先度付きキューがあります。優先度つきキューなら最大値の取り出しと値の追加が$O(\log N)$で完了します。

次に制約をみます。

品物の個数$N$と割引券の枚数$M$がともに最大$10^5$です。

割引券ごとに優先度つきキューから商品を取り出して割引を適用してキューに戻すという操作を繰り返しても、$O(M \log N)$で完了します。

以上から、以下の手順で実装します。

1. 最大値を返す優先度付きキューを用意する
2. 優先度付きキューに商品を追加する
3. 割引券ごとに、優先度付きキューから商品を取り出して割引を適用してキューに戻す操作を繰り返す
4. 優先度付きキューの値の合計を出力する

(defun solve ()
  (let* ((n (read))
         (m (read))
         (heapq (make-array 0 :fill-pointer 0 :adjustable t)))
    (loop repeat n
          for ai = (read)
          do (heap-push heapq ai))
    (loop repeat m
          for ai = (heap-pop heapq)
          do (heap-push heapq (floor ai 2)))
    (format t "~A~%" (reduce #'+ heapq))))


(defun shift-down (q idx)
  (let ((idx-l (+ (* idx 2) 1))
        (idx-r (+ (* idx 2) 2))
        (idx-next idx))
    (when (and (< idx-r (length q))
               (> (aref q idx-r) (aref q idx-next)))
      (setf idx-next idx-r))
    (when (and (< idx-l (length q))
               (> (aref q idx-l) (aref q idx-next)))
      (setf idx-next idx-l))
    (when (/= idx-next idx)
      (rotatef (aref q idx) (aref q idx-next))
      (shift-down q idx-next))))

(defun heap-push (q item)
  (vector-push-extend item q)
  (loop with idx = (1- (length q))
        for parent-idx = (floor (1- idx) 2)
        while (and (> idx 0)
                   (> (aref q idx) (aref q parent-idx)))
        do (rotatef (aref q idx) (aref q parent-idx))
           (setf idx (floor (1- idx) 2))))

(defun heap-pop (q)
  (cond ((zerop (length q))
         nil)
        ((= (length q) 1)
         (vector-pop q))
        (t
         (let ((ans (aref q 0)))
           (setf (aref q 0) (vector-pop q))
           (shift-down q 0)
           ans))))

(defun heap-top (q)
  (if (zerop (length q))
      nil
      (aref q 0)))

(solve)

Common Lispには優先度付きキューがないので、自前で実装しました。

AtCoder Beginner Contestを解いてみたリスト

ABC138D - Kiを解いてみた

40代文系社内SEが、AtCoder Beginner Contest 138 D - Kiを解いてみました。

まず問題文を確認します。

根が頂点1の木があり、それぞれの頂点はカウンターをもっています。部分木のカウンターに値を加算する操作を繰り返し、最終的なカウンターの値を求めます。

まず、「木」と記載されていることからグラフの問題であることが考えられます。また、部分木に値を加算するとありますが、おそらくそのまま実装するとTLEになるだろうと思われます。

次に制約を確認します。

頂点の個数$N$が最大$2 \times 10 ^ 5$であり、操作回数$Q$も最大$2 \times 10 ^ 5$であることから、毎回頂点1に操作をするケースで計算量が$10 ^ {10}$を超えて間に合いません。

どのように計算量を抑えるかと考えたとき、根から部分木に値を加算していくという操作が累積和のようにみえました。すべての頂点が一直線につながっているようなケースを考えると、イメージしやすいかと思います。

累積和が使えれば、値を加算する操作は最後に1回だけ処理すればいいので、計算量を$2 \times 10 ^ 5$に抑えられそうです。

以上より、以下の手順で実装します。

1. a、bを隣接リストとして読み込む
2. カウンターを用意して、カウンターpにxを加算する
3. 頂点1からグラフを探索し、累積和の要領で値を加算する

(defun solve ()
  (let* ((n (read))
         (q (read))
         (graph (make-array (1+ n) :initial-element nil))
         (counter (make-array (1+ n) :initial-element 0)))

    ;; a, bを読み込み、隣接リストとして保持
    (loop repeat (1- n)
          for ai = (read)
          for bi = (read)
          do (push bi (aref graph ai))
             (push ai (aref graph bi)))

    ;; p, xを読み込み、カウンターに記録
    (loop for i from 1 to q
          for p-i = (read)
          for xi  = (read)
          do (incf (aref counter p-i) xi))
    (let ((visited (make-array (1+ n) :initial-element nil)))
      ;; 頂点1を訪問済にして深さ優先探索を開始
      (setf (aref visited 1) t)
      (dfs graph counter '(1) visited)
      (format t "~{~A~^ ~}~%" (coerce (subseq counter 1) 'list)))))

(defun dfs (graph counter visiting visited)
  ;; 深さ優先探索でグラフを探索し、カウンターを更新する
  (when (not (null visiting))
    (loop with pos = (pop visiting)
          for dest in (aref graph pos)
          when (not (aref visited dest))
            do (incf (aref counter dest) (aref counter pos)) ; 次の頂点にカウンターの値を加算する
               (setf (aref visited dest) t)
               (push dest visiting))
    (dfs graph counter visiting visited)))

(solve)

ACできたのですが、訪問済のチェックを省略していて1回WAになってしまいました。

ABC128C - Switchesをビット全探索で解いてみた

40代文系社内SEがAtCoder Beginner Contest 128 C - Switchesを解いてみました。

まず問題文を読んでみる。

1行目と3行目は問題ないが、2行目がうまくのみこめない。

「電球iはki個のスイッチに繋がっており、スイッチsi1, si2, ..., sikiのうちonになっているスイッチの個数を2で割った余りがpiに等しいときに点灯します。」

ちょっとずつ分解してみる。

まず、piは制約に0または1と記載されているので、2で割った余りがpiに等しいとは、つまり偶数か奇数ということ。

「全部がonだったら」とか、「どれかひとつがonだったら」なら容易にイメージできるのに。

残りの前半部分については、電球ごとに繋がっているスイッチは異なり、

個数がkiで示され、続けてsijでどのスイッチに繋がっているかが示される。

続けて制約をみる。

NもMも10以下というのはかなり小さい値だ。

それ以外は特に気になることはなかった。

スイッチの状態がon/offの2種類であることと、個数が最大10個という制約から、スイッチの状態が全探索できそうだ。

$2^{10} = 1024$

電球が点灯しているかどうかを判定するには、電球ごとにonになっているスイッチを数えなければならない。

電球もスイッチも最大10個だから、最大でも10 * 10で網羅できる。

あとは実装方法だが、スイッチの状態がon/offの2種類なのでbit全探索が使える。

0以上(2^N)未満までループで回せば網羅できる。

例えば入力例1だと、0(00)、1(01)、2(10)、3(11)の4通りになる。

以上より、以下3ステップで問題を解く。

1. スイッチの状態ごとに、全ての電球が点灯しているか判定する

2. 電球ごとに、点灯しているか判定する

3. 電球に繋がっているスイッチごとに、onになっているか判定する

(let* ((n (read))
       (m (read))
       (k (make-array m))
       (s (make-array m :initial-element nil))
       (p (make-array m)))

  ;; k, sを読み込み
  (loop for i from 0 below m
        for ki = (read)
        do (setf (aref k i) ki)
           (loop repeat ki
                 for sij = (read)
                 do (push sij (aref s i))))

  ;; pを読み込み
  (loop for i from 0 below m
        for p-i = (read)
        do (setf (aref p i) p-i))

  ;; on/off
  (loop for stat from 0 below (expt 2 n)
        ;; 点灯している電球の個数
        for light-on = (loop for light from 0 below m
                             ;; onになっているスイッチの個数
                             for switch-on = (loop for switch in (aref s light)
                                                   count (logbitp (1- switch) stat))
                             count (= (mod switch-on 2)
                                      (aref p light)))
        count (= light-on m)
          into it
    finally
       (format t "~A~%" it)))

AtCoder Beginner Contestを解いてみたリスト

ABC143D - Trianglesを二分探索で解いてみた

40代文系SEがAtCoder Beginner Contest 143 D - Trianglesを解いてみました。

様々な長さの棒が与えられ、その中から3本選んで三角形を作る選び方は何通りかを求める問題です。

まず注目したのは制約の$10^3$です。

あまり見かけない数字です。

$N^2$でも$10^6$なので2重ループが使えそうです。

3本の棒のうち、2本まで選ぶと3本目の長さの最大値が決まります。

棒の選び方にもともとの並び順は関係ないので、ソートしても問題ありません。

ということで2分探索が使えます。よっしゃ。

3本中2本を全探索で選び、残りの1本として選べる範囲を2分探索で求めることでACできました。

(defun solve ()
  (let* ((n (read))
         (l (make-array n :initial-contents (loop repeat n collect (read)))))
    (format t "~A~%" (solve2 l))))

(defun solve2 (l)
  (let* ((ll (make-array (1+ (length l)))))
    (loop for i from 0 below (length l) do (setf (aref ll i) (aref l i)))
    (setf (aref ll (1- (length ll))) (1+ (expt 10 3)))
    (sort ll #'<)
    (loop with ans = 0
          for i from 0 below (- (length ll) 2)
          do (loop for j from (1+ i) below (- (length ll) 1)
                   do (incf ans (solve1 ll i j)))
          finally
             (return ans))))

(defun solve1 (l i j)
  (labels ((f (min max)
             (if (= (1+ min) max)
                 min
                 (let* ((li (aref l i))
                        (lj (aref l j))
                        (mid (+ min (floor (- max min) 2)))
                        (lmid (aref l mid)))
                   (if (< lmid (+ li lj))
                       (f mid max)
                       (f min mid))))))
    (- (f j (1- (length l))) j)))

(solve)

AtCoder Beginner Contestを解いてみたリスト

AtCoderで入茶しました

 2023/02/04に開催された、Ｓｋｙ株式会社プログラミングコンテスト2023（AtCoder Beginner Contest 289）の結果レートが403になり、入茶できました。

自分も色変記事として思っていることをつらつらと並べてみたいと思います。

感謝について

家族の皆様、毎週コンテストに参加するために時間を調整してくれてありがとう。

AtCoder社様、毎週コンテストを開いてくださってありがとうございます。

Twitterでリアクションしてくださった皆様、ありがとうございます。一緒に盛り上げましょう。

自分について

新卒でシステムエンジニアとして就職して18年。社内SEに転職して5年。

今の環境に慣れてきて、若干飽きてきている部分もあったりして、少し変化が欲しかった。

参加したプロジェクト内ではプログラムをよく書けるほうだと思っていた。

AtCoderでも茶色くらいにはなれるんじゃない？

初めて参加したコンテストでは1完灰パフォ。

「AtCoderが保証できる実力はまったくありません。」うそやろ。

勉強について

まずは問題に慣れるために、過去問のAB問題を新しいものから順番に解いていった。

B問題まで安定してきたところで、茶色になるにはC問題まで解けないと難しそうだと感じた。

過去問の範囲をC問題まで広げ、C問題もほぼ解けるようになった。

D問題はまだほとんど解けない。競技プログラミングに出題されるアルゴリズムについての知識が不足している。

競プロ典型90問などで知識を増やし、類題を繰り返し解いて問題を解くための道具として使いこなせるようにしなければならない。

モチベーションを上げるために

自分よりちょっと強いユーザーをお気に入りに登録する。順位表をみて、「お、さすが」「今回は自分の勝ちですね」などニヤニヤしている。

TwitterでAtCoder関係のフォローを増やす。コンテスト開始前終了後にざわざわしているのが楽しい。

AtCoder Problemsでどれくらい問題を解いているかを確認する。一覧に緑色が増えると嬉しい。

モチベーションを下げないために

必死になりすぎない。

まだレートを上げたいとも思うし、勉強が必要だとも思う。

でも頑張らないとできないことは続かないので、頑張らなくてもできる範囲にする。

その代わりにあまりレートが上がらなくても受け入れる。

世の中には自分より熱心に取り組んでいる人がいるので、そういう人に追いつけなかったり、追い越されたりしても当たり前。気にしない。

あとは特に理由がないかぎり、毎週Ratedでコンテストに参加する。

競プロは仕事に役立つか

今までのところ、特に役立ったと感じる場面はない。

灰コーダーには灰コーダーなりの問題解決方法があり、それで十分なこともある。

「インデックスを貼れば検索が早くなるんでしょ」みたいなざっくりとした理解とか。

勉強を進めていく中で、見える景色が変わってくれると嬉しい。

最後に

まだ続けたいと思っています。

引き続きよろしくお願いします。

Strings.StrConvで全角に変換するときにサロゲートペア文字が文字化けする

Strings.StrConvで全角に変換しようとする文字列にサロゲートペア文字が含まれていると"？？"に変換されてしまいます。

Debug.WriteLine("𠀋=" + Strings.StrConv("𠀋", VbStrConv.Wide)); // 𠀋=？？と表示される

「.NET Frameworkは文字列を内部的にUnicodeしており、標準機能のStrConvを使用しているからヨシ！」と思っていると失敗するので注意が必要です。

参考

Strings.StrConv

PHPのビルトインWEBサーバーを使用する

PHPプログラムをブラウザから実行するにはWEBサーバーが必要です。
PHP5.4からビルトインWEBサーバーが組み込まれたため、開発時はPHPのみで動作確認ができます。
ビルトインWEBサーバーを起動するには、ドキュメントルートとするディレクトリをカレントディレクトリとし、php.exeに-Sオプションをつけて実行します。

C:\> cd path\to\docroot
C:\path\to\docroot> php -S 127.0.0.1:8080

もしくは-tオプションでドキュメントルートを指定します。

C:\> php -S 127.0.0.1:8080 -t C:\path\to\docroot

出力のバッファリングを使用した関数のエラー処理とLaravelのエラー処理との問題

弊社のシステムに下のようなプログラムがありました。

try {
    // ob_startなどは、file_get_contentsだけで処理を完結させるために使用。
    ob_start();
    $image = file_get_contents($path);
    $warning = ob_get_contents();
    ob_end_clean();
    if (strlen($warning) > 0) {
        throw new \Exception($waring);
    }
} catch (\Exception $e) {
    // エラー処理
}

コメントが何を伝えようとしているのか不明だったため、調べてみました。
PHPではエラーが発生すると、メッセージが画面に表示されます。
ob_start関数は出力のバッファリングを開始する関数で、エラーメッセージもバッファリングされます。
上のプログラムではfile_get_contents関数で発生したエラーのメッセージを一旦バッファリングしたあとで、例外としてthrowしたいようです。

しかし、弊社のシステムではフレームワークとしてLaravelを採用しており、エラーはErrorExceptionとしてthrowされるようになっています。
file_get_contentsでエラーが発生すると、ob_end_cleanが実行されないままcatchブロックが実行されてしまいます。

過去のPHPではある程度有効なパターンだったのかもしれませんが、Laravelには合わないので改修しなければなりません。

VB.NETのキライなところ: 構造体にNothingを代入できる

C#ではintなどの構造体にnullを代入しようとすると、コンパイルエラーが発生します。

int x = null; // コンパイルエラー

一方、VB.NETではnull許容型でない構造体にNothingを代入すると、デフォルト値が代入されます。

Dim x As Integer = Nothing ' x = 0

Nothing的な値との比較は以下のようになります。

Public Shared Sub Main()
    Dim n As Integer = Nothing

    ' コンパイルエラー(VBNC30020)
    ' If n Is Nothing Then
    '     Console.WriteLine("n is Nothing")
    ' End If
    If n = Nothing Then
        Console.WriteLine("n equals Nothing")
    End If
    If IsNothing(n) Then
        Console.WriteLine("isNothing n")
    End If
    If n = 0 Then
        Console.WriteLine("n equals zero")
    End If
End Sub
' 実行結果
' n equals Nothing
' n equals zero

n = Nothingは使えるけど、IsNothing(n)常にFalseを返すので使えない。
仕様を理解していても混乱してしまうのでキライです。
null許容でない構造体の初期化にはNothingを使わないようにします。

参考
Nothing(Visual Basic)

openpyxlで行のグルーピング

PythonでExcelを読み書きするライブラリの１つとして、openpyxlがあります。
公式サイトには列のグルーピングについては記載されていましたが、行のグルーピングについては記載されていませんでした。
ソースを参照しながら工夫したらどうにかできたので公開します。
今後公式から行のグルーピングについてアナウンスされるかもしれませんので、ご留意ください。
以下、ソースです。

Bash on Ubuntu on Windowsでemacs-eclimは動作するのか

結論からいえば、動作します。

基本的にInstalling on a headless serverや、Installationの手順に従えば使用できるようになります。
いくつかつまづいたことがあったので記録しておきます。

package-installコマンドでemacs-eclimをインストールできない
apt-get upgradeコマンドを実行したらインストールできました。

package-list-packagesコマンドを実行するとemacsがバックグラウンドに回る
bash on Ubuntu on Windowsのバグらしいです。
どうにかしてX Window System経由でemacsを起動しないと対応できないようです。

これでEmacs on Bash on Ubuntu on Windowsでも快適にJavaが書けます。

PowerShellで、ショートカット情報を得るフィルタを作ってみる(5.1.14393.576対応)

PowerShellで、ショートカット情報を得るフィルタを作ってみるにて、Windows PowerShellからショートカットの情報を得る方法が紹介されています。
しかし、残念ながら私の環境では動作しませんでした。
以下のように、CreateShortcutメソッドへ渡すパラメータを$_から$_.FullNameへ変更することで動作させることができました。

filter Get-Shortcut()
{
    $shell = New-Object -ComObject WScript.Shell
    return $shell.CreateShortcut($_.FullName)
}

ExcelからRSSを取得するサンプルプログラム

MSXMLを使用すれば、ExcelからRSSを取得できます。
XmlNode.SelectNodesメソッドを使用するときは名前空間(Namespace)に注意します。
サンプルではXMLDOMDocument.setPropertyを使用して名前空間を指定しています。

以下、サンプルプログラムです。

Public Sub Msxml()

    Dim namespaces As String
    Dim xml        As Object
    Dim ret        As Boolean
    Dim nodeList   As Object
    Dim item       As Object
    
    namespaces = "xmlns:rss='http://purl.org/rss/1.0/'"
    namespaces = namespaces + " xmlns:rdf='http://www.w3.org/1999/02/22-rdf-syntax-ns#'"
    
    Set xml = CreateObject("MSXML2.DOMDocument.6.0")
    Call xml.setProperty("ServerHTTPRequest", True)
    Call xml.setProperty("SelectionNamespaces", namespaces)
    xml.async = False
    
    ret = xml.Load("http://b.hatena.ne.jp/sample/rss")
    
    If ret Then
        Set nodeList = xml.SelectNodes("/rdf:RDF/rss:item/rss:title")
        
        For i = 0 To nodeList.Length - 1
            ActiveSheet.Cells(i + 1, 1).Value = nodeList.item(i).Text
        Next
    End If
End Sub

POIで絵文字を出力するためのハック

この記事では、POIを使ってExcel(xlsx)ファイルへ絵文字を出力するためのハックを紹介します。
「ハック」と表現したように、あまりお行儀のいい方法ではないと思っているので、もっとスマートな方法を御存知でしたらコメントなどで教えていただけると嬉しいです。

POIで絵文字を出力しようとすると、そのままでは「??」と文字化けしたようになってしまいます。

これは、Apache XMLBeansのTextSaver(org.apache.xmlbeans.impl.Saver.TextSaver)クラスのisBadCharメソッドが絵文字に対してtrueを返すからです。

Apache XMLBeansはすでに開発が終了しています。isBadCharメソッドはprivateで定義されているので、オーバーライドもできません。私はクラスを上書きする方法を選択しました。

まずは、Apache XMLBeansのソースを取得します。

svn export http://svn.apache.org/repos/asf/xmlbeans/trunk/ xmlbeans

次に、xmlbeans\src\store\org\apache\xmlbeans\impl\Saver.javaをプロジェクトへコピーします。必要なディレクトリ(org\apache\xmlbeans\impl)を作成し、その配下へコピーします。

最後に、isBadCharメソッドを書き換えます。書き換え後は次のようになります。

        private boolean isBadChar ( char ch )
        {
            if (Character.isHighSurrogate(ch) ||
                Character.isLowSurrogate(ch))
                return false;
            return ! (
                (ch >= 0x20 && ch <= 0xD7FF ) ||
                (ch >= 0xE000 && ch <= 0xFFFD) ||
                (ch >= 0x10000 && ch <= 0x10FFFF) ||
                (ch == 0x9) || (ch == 0xA) || (ch == 0xD)
                );
        }

OptimizedForSpeedSaverにも同様のメソッドがあるので、ついでに書き換えておきます。

以上で絵文字を出力できるようになります。

参考
Apache POI
Apache XMLBeans
Unicode その他の記号と絵文字