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があります。
公式サイトには列のグルーピングについては記載されていましたが、行のグルーピングについては記載されていませんでした。
ソースを参照しながら工夫したらどうにかできたので公開します。
今後公式から行のグルーピングについてアナウンスされるかもしれませんので、ご留意ください。
以下、ソースです。