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で入茶しました

 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 その他の記号と絵文字

ASP.NETでファイルをダウンロードするボタン

クリックするとファイルをダウンロードするボタンを作りました。
主な機能は以下のとおりです。

• クリックするとFileプロパティにセットされたファイルをダウンロードする
• FileプロパティはClickイベントやDownloadingイベントでセットすることもできる
• Downloadedイベントで動的に作成したファイルを削除することもできる

使用するには、以下の手順に従います。

1. FileDownloadButtonをプロジェクトに追加する
2. FileDownloadButtonをツールボックスへ追加する
   参考: 方法 : Visual Studio でカスタム ASP.NET サーバー コントロールを使用するの「カスタム コントロールをツールボックスに追加するには」
3. *.aspxへFileDownloadButtonを配置し、イベントハンドラを設定する
   例:

   <cc1:FileDownloadButton ID="FileDownloadButton1" runat="server"
                           Text="Download"
                           OnDownloading="FileDownloadButton1_Downloading"
                           OnDownloaded="FileDownloadButton1_Downloaded"/>
   

4. *.csでイベントハンドラを実装する
   例:

           protected void FileDownloadButton1_Downloading(object sender, EventArgs e)
           {
               // Tempファイルを作成する
               var path = Path.GetTempFileName();
               var file = new FileInfo(path);
   
               // Tempファイルへデータを出力する
               using (var s = file.OpenWrite())
               using (var w = new StreamWriter(s))
               {
                   w.WriteLine("Hello");
                   w.Flush();
               }
   
               // FileDownloadButtonのFileプロパティへTempファイルをセットする
               FileDownloadButton1.File = file;
           }
   
           protected void FileDownloadButton1_Downloaded(object sender, EventArgs e)
           {
               // Tempファイルを削除する
               FileDownloadButton1.File.Delete();
           }
   

Content-Typeの設定やレスポンスの呼び出しなど、低レベルな処理をカプセル化できるので、導入のメリットはそこそこあると思います。よろしければご利用ください。

以下、FileDownloadButtonのソースです。

ASP.NETで動的に画像を生成して返す(IHttpHandler版)

ASP.NETで動的に画像を生成して返すようなときは、WebFormを使用するのが一般的なようです。

• ［ASP.NET］任意の画像を出力してブラウザで表示するには？［C#、VB］
• Dynamic Image Generation with ASP.Net

この記事ではIHttpHandlerインターフェイスを実装して画像を生成して返す方法を紹介します。
以下２つの手順に従います。

1. IHttpHandlerインターフェイスを実装した画像を出力するクラスを実装する
2. 1のクラスをweb.configファイルへ登録する

まず「IHttpHandlerインターフェイスを実装した画像を出力するクラスを実装する」について説明します。このクラスのポイントは3つあります。

1. IHttpHandlerインターフェイスを実装すること
2. 画像のバイナリデータをHTTPレスポンスへ出力すること
3. Content-Typeヘッダを適切に設定すること

次のサンプルプログラム(一部)をご覧ください。

namespace HttpHandlerSample
{
    // 動的にPNG画像を生成するクラス
    public class PngHandler : IHttpHandler
    {
        // このオブジェクトが再利用可能かを返すプロパティ
        public bool IsReusable
        {
            get
            {
                return true;
            }
        }

        // ...略...

        // HTTPリクエストを処理するメソッド
        public void ProcessRequest(HttpContext context)
        {
            // 画像を生成する
            using (var image = GenerateImage())
            {
                // PNG形式でHTTPレスポンスへ出力する
                var output = context.Response.OutputStream;
                image.Save(output, ImageFormat.Png);
                output.Flush();
            }

            // Content-TypeヘッダをPNG形式に設定する
            context.Response.ContentType = "image/png";
        }

        // ...略...

    }
}

IHttpHandlerにはIsReusableプロパティとProcessRequestメソッドが定義されています。このProcessRequestメソッドを実装することで機能を実現します。
画像のバイナリデータを出力するには、Image#Saveメソッドを使用します。
Content-Typeヘッダを指定するには、HttpResponse#ContentTypeプロパティを使用します。画像の形式が一致するように設定します。

次に、上のクラスをweb.configへ以下のように設定します。

<configuration>
  <system.webServer>
    <handlers>
      <add name="PngHandler" path="*.png" verb="GET" type="HttpHandlerSample.PngHandler"/>
    </handlers>
  </system.webServer>
</configuration>

ちなみに

以上で動的な画像の生成が実現できます。
以下、サンプルコード全体です。

年齢を計算する関数

過去に実装した年齢計算プログラムのロジックが残念なことになっていましたので、考えを整理しました。
記事の最後に載せたプログラムのコメントにも書きましたが、ポイントは2つあります。

1. 基準日の年と生年の差
2. 基準日がその年の誕生日よりも前のときは1を減算する

2つ目の条件につきましては、生年月日の年を基準日の年と置き換え、年齢を求める日付と比較すれば判定できます。
「年齢を求める日付」はいい言葉が思いつきませんでした。いい言葉をご存知の方はコメントして頂けると助かります。
2015/8/31
NARITA Shoさんから「Excel 界隈では「基準日」という語が使われているみたいですね。」とのコメントを頂きました。ありがとうございました。

以下、xyzzy lispとC#での実装を記載します。
2015/9/2
C#での実装例を追加しました。

Javaの正規表現で後方参照を使用する

テキスト処理で重要になる正規表現と後方参照。
Javaで実装するサンプルを２つ紹介します。

$nを使用する方法
Matcher#replaceAllメソッドや、Matcher#replaceFirstメソッドは$nで後方参照を使用できます。

String regex = "\\[([0-9]+)\\]";
String src = "[1] [2] [3] [4] [5]";
 
Pattern pattern = Pattern.compile(regex);
Matcher matcher = pattern.matcher(src);
String  result1 = matcher.replaceAll("($1)");
System.out.println(result1);
// => (1) (2) (3) (4) (5)

Matcher#groupを使用する方法
Matcher#groupメソッドを使用する方法は多少複雑です。
正規表現にマッチする部分は、Matcher#startメソッドとMatcher#endから取得できます。
この部分文字列を置き換えてしまえばいいというわけです。
こちらの方法では、後方参照で取得した文字列を元にして、編集を加えられるというメリットがあります。
サンプルではアラビア数字から漢数字へ置き換えています。

String regex = "\\[([0-9]+)\\]";
String src = "[1] [2] [3] [4] [5]";
String[] kan = {"一", "ニ", "三", "四", "五"};
Pattern pattern = Pattern.compile(regex);
Matcher matcher = pattern.matcher(src);
StringBuilder result2 = new StringBuilder();
int lastEnd = 0;
String outOfMatch = "";
while(matcher.find()) {
    outOfMatch = src.substring(lastEnd, matcher.start());
    String group = matcher.group(1);
    int n = Integer.parseInt(group);
    String kanN = kan[n-1];
    result2.append(outOfMatch);
    result2.append("(" + kanN + ")");
    lastEnd = matcher.end();
}
outOfMatch = src.substring(lastEnd);
result2.append(outOfMatch);
System.out.println(result2);
// => (一) (ニ) (三) (四) (五)

以下、サンプルソース全体です。

Javaで文字列を表示した時の幅を取得する

FontオブジェクトとFontMetricsオブジェクトを使用して、簡単に取得できます。
簡単なのでいきなりサンプルプログラムです。

import java.awt.Font;
import java.awt.FontMetrics;
import sun.font.FontDesignMetrics;

public class Program {

    public static void main(String[] args) {
        // Fontオブジェクトをインスタンス化する
        // FontオブジェクトからFontMetricsオブジェクトを取得する
        // FontMetrics#stringWidthメソッドで文字列の幅を取得する
        Font font = new Font("Monospace", Font.PLAIN, 12);
        FontMetrics fontMetrics = FontDesignMetrics.getMetrics(font);
        String data = "Hello FontMetrics";
        int width = fontMetrics.stringWidth(data);
        System.out.println(width);
    }
}

※このプログラムをコンパイルすると警告が出ます。

JavaのExecutorServiceのサンプル

Javaでスレッドを使用するには、ExecutorService#invokeAllを呼ぶのが簡単です。ExecutorService#inokeAllは別スレッドで実行するCallableオブジェクトのコレクションを引数として受け取り、処理がすべて完了するまで現在のスレッドをブロックします。処理の結果はFutureのリストとして返ります。
サンプルとして、複数のホストに対してpingコマンドを発行するプログラムを作成しました。

import java.util.List;
import java.util.ArrayList;
import java.util.concurrent.Callable;
import java.util.concurrent.Executors;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Future;

public class Program {
    
    public static void main(String[] args) throws Exception {

        ExecutorService svc = Executors.newFixedThreadPool(3);

        try {
            List<Callable<Integer>> listCallable = new ArrayList<>();
            for (String ipAddress : args) {
                listCallable.add(new PingCommand(ipAddress));
            }
            List<Future<Integer>> listFuture = svc.invokeAll(listCallable);
            for (Future<Integer> future : listFuture) {
                System.out.println(future.get());
            }
        } finally {
            svc.shutdown();
        }
    }

    private static class PingCommand implements Callable<Integer> {
        private final String ipAddress;

        private PingCommand(String ipAddress) {
            this.ipAddress = ipAddress;
        }

        public Integer call() {
            try {
                String[] args = {"ping", ipAddress, "-c", "3"};
                Process proc = new ProcessBuilder(args).start();
                return proc.waitFor();
            } catch (Exception e) {
                e.printStackTrace();
                return -1;
            }
        }
    }
}

参考
ExecutorService
Callable
Future

Windows PowerShellでExcelが出力したCSVを読み込むには

先日、Excelで作成されたドキュメントを一括処理する作業をしていました。
最近「Windows PowerShellいいよ」という話をみかけたので、Windows PowerShellで自動化することにしました。

Windows PowerShellには、CSVを取り込むためのコマンドレットがあり、"Import-Csv"といいます。
ところがこのコマンドレット、Windows 7に標準でインストールされているバージョンでは、取り込む対象のエンコーディングを指定できないという致命的な欠点があります。Excelが出力するCSVのエンコーディングはShift-JIS。一方Import-CSVが対応しているのはUnicode。困りました。

解決策は2つあります。
1. Windows PowerShellをアップデートする
Windows PowerShell 3.0以降、Import-CSVに-Encodingパラメータが追加されました。"-Encoding Default"を指定すれば、Shift-JISのファイルにも対応できます。アップデートファイルは、下記参考の"Windows Management Framework 4.0"から取得してください。

Import-Csv -Path .\Book1.csv -Encoding Default

2. Get-ContentとConvertFrom-Csvを使用する
Get-ContentはShift-JISに対応していますので、Get-ContentとConvertFrom-Csvをパイプでつなぐことで読み込めます。

Get-Content .\Book1.csv | ConvertFrom-Csv

参考
Windows Management Framework 4.0
ConvertFrom-Csv
Get-Content
Import-Csv

Clojureでawtの画面を表示

ClojureからawtのWindowを表示するだけのサンプルプログラムです。

(ns myawt)

(import '(java.awt Frame)
        '(java.awt.event WindowListener))

(def window-width 600)
(def window-height 480)

(doto (Frame.)
    (.addWindowListener
        (proxy [WindowListener] []
            (windowActivated [e])
            (windowClosed [e] (System/exit 0))
            (windowClosing [e] (.dispose (.getWindow e)))
            (windowDeactivated [e])
            (windowDeiconified [e])
            (windowIconified [e])
            (windowOpened [e])))
     (.setSize window-width window-height)
     (.setVisible true))

windowClosedとwindowClosingのイベントハンドラを実装するのがポイントです。

参照
Frame
WindowListener

行指向ファイル処理フレームワーク

業務でファイルを一行ずつ読み込んで処理するプログラムをコーディングしているのですが、提供された設計書のフローチャートに従って実装を進めていたら、脳みそがぐちゃぐちゃにかき回されるようないらだちを覚えました。
"ファイルを一行ずつ読み込んで処理する"という要件は、あちこちで需要がありそうなので、モデルを考えてみました。 Process、FileFinder、FileHandler、LineHandlerの4つのクラスで構成します。