2025-08-04

■

Haskell練習記です。ABCのB問題を解きます。

問題

広義単調増加数列Aから、M回次の操作を行う。i番目(i=[1.,.M])の操作は、長さMの整数列Bのi番目の数B[i]と同じ整数を、Aから取り除く。M回操作を行ったAを出力せよ。

実装

まず、i番目の操作を行う関数を考えました。計算量を気にしなくてもよいB問題なので、Haskellの効率の悪いが素直に書ける(単連結)リストを使います。命令型言語で書く場合、B[j]と同じ要素を探すためにiをループで回しA[i]と添字アクセスするのが素直な書き方ですが、リストにはえ字アクセスできないので、Aを表すリストを左右に分割し、左右の区切りを左から右にずらしていけばいいと考えました。これを書くと、

-- delete [] A biはAからbiの要素を取り除かれたリストを表す
deleteBi :: [Int] -> [Int] -> Int -> [Int]
deleteBi leftA rightA bi = deleteBi (leftA ++ take 1 rightA) (tail rightA) bi

となります。次に、終了条件を足すと、

deleteBi leftA rightA bi =
    if rightA == []
        then leftA
    else
        deleteBi (leftA ++ take 1 rightA) (tail rightA) bi

となります。leftAとrightAに分かれているので、各再帰でrightAの先頭が、A[i]に相当することになります。よって、AからB[i]を取り除く処理は、

 else if head rightA == bi then leftA ++ (tail rightA)

となります。これでこの処理は完成です。関数全体は以下の通りです。

deleteBi :: [Int] -> [Int] -> Int -> [Int]
deleteBi leftA rightA bi =
    if rightA == []
        then leftA
    else if head rightA == bi
        then leftA ++ (tail rightA)
    else
        deleteBi (leftA ++ take 1 rightA) (tail rightA) bi

あと足りないものは、この関数の引数biに整数列Bの各要素を入れて、返り値をまた引数rightAに、biにさっきいれた整数列Bの要素の次の要素を代入して、...という操作を繰り返すことです。これは畳み込みなので、foldlが使えそうです。...が、そこから自分では書けそうになかったので、AIに書かせました。

deleteAll :: [Int] -> [Int] -> [Int]
deleteAll xs bis = foldl step xs bis
    where
            step acc bi = deleteBi [] acc bi

あとは入力を受け取り、deleteAllを適用して、指定通りに出力するだけです。Haskellで数列を空白区切りで出力するには、unwordsを使うのが便利なようです。また、AとBの数列を受け取るとき、getLineで一気に1行受け取り、そこからmapで一気に入力を受け取る変数に代入していくので、入力1行目のNとMは使いません。mainと数列を出力する関数は以下のようになりました。計算量はO(MN^2)のようです。

deleteAll :: [Int] -> [Int] -> [Int]
deleteAll xs bis = foldl step xs bis
    where
            step acc bi = deleteBi [] acc bi

intsToString :: [Int] -> String
intsToString = unwords . map show
main :: IO ()
main = do
    size <- getLine
    aIO <- getLine
    bIO <- getLine
    let
        [n, m] = (map read . words) size :: [Int]
        a = map read $ words aIO :: [Int]
        b = map read $ words bIO :: [Int]
        result = deleteAll a b
    putStrLn $ intsToString result

2023-10-04

それでもスクリーンショットを繰り返すと色が変わる

前置き

以前、こんなツイートが話題になった。

Windows、コピペするだけで色が壊れる pic.twitter.com/llbqwZokB2
— 🍣 (@refeia) September 24, 2022

https://x.com/refeia/status/1573753515172044800

これはスクリーンショットを取られた画面の色空間の情報がそのスクリーンショットに埋め込まれないからである。画像に色空間の情報がないとき、その画像はsRGBの色空間であるだとみなされることが多い。もし、Adobe RGBのモニターに赤色(R,G,B) = (255, 0, 0)を表示し、これのスクリーンショットをとったとき、そのスクリーンショットは当然、(255, 0, 0)という数字が記録されている。このスクリーンショットを同じモニターに貼ると、アプリケーションは(255, 0, 0)という数字の色をsRGBの色空間での数字だとみなし、これをAdobe RGBのモニターに表示するわけだから、モニターには(242, 0, 0)(この数字はsRGBの(255,0,0)と同じ色である))という信号を送る。これがスクリーンショットを貼ると色が変わる理由だ。

本題

前置きが長くなったがｍスクリーンショットにそのモニターの色空間の情報(これにはICCプロファイルと呼ばれるものが広く使われている)が埋め込まれ、それが正しく解釈されたとしても計算精度の関係でわずかに色が変化する。左下の写真はテスト用の真っ赤な画像である。カラーコードは#FF0000で、Display P3のICCプロファイルを埋め込んでいる。これをiPhoneの写真アプリで表示し、スクリーンショットを撮り、そのスクリーンショットを表示する、という手順を40回繰り返して得た画像が右下の画像だ。

広色域環境でよく見比べないと違いが分からないが、カラーコードを調べると、#E70403であった。かなり色が劣化していることがわかる。iPhoneはスクリーンショットにDisplay P3のプロファイルを埋め込むため、この現象は前述した色空間の齟齬によるものではない。もう少し詳しく調べるためにこれらの差分をとってRGB値を50倍にし、(見た目が気持ち悪いので)グレースケールにしたimagemagickのコマンドを以下に示す。

composite -compose difference Red.png Red40.png diff.png
magick convert diff.png -color-matrix "50 0 0  0 50 0  0 0 50" diff50x.png
magick diff50x.png -colorspace Gray diff50xGray.png

このコマンドで生成したdiff50xGray.pngは下のようになった。

この模様はカラーマネジメントの過程で244.43...のように整数ではなくなった色を表示するときに使われるディザリングによるものであると推測した。ディザリング処理にはノイズ、つまり乱数が用いられるが、乱数を逐次計算するよりも乱数テーブルを参照したほうが速いためこのような周期的な模様が現れると考えられる。

終わりに

Windows標準のスクリーンショットはICCプロファイルを埋め込まないので、ICCプロファイルを設定した環境だと注意する必要があるが、実は埋め込まれていたとしても若干色が変わることが示せた。

2021-12-29

Windowsでも美しいフォントで読みたい

前置き

一般にWindowsのフォントレンダリングは汚いといわれています。その原因はいろいろ言われていますが、一番よく言われているのは標準で使われているフォントが汚いことです。例えばMSゴシックはフォントサイズが12pt以下だとアンチエイリアスの効いたアウトライン描画ではなく、ビットマップフォントで表示されてしまうので、特にHiDPI環境での視認性がとても悪くなります。そこで自分できれいなフォントをインストールして使うわけですが、後述するように一筋縄ではいきません。そこでこの記事ではブラウザで自分好みのフォントで読む方法を紹介します。
　ブラウザの設定でフォントは変更することができますが、font-familyが未指定かsans-serif等、総称でしか指定していない場合のみ反映されます。しかし、

font-family:"MS Pゴシック",sans-serif;

と指定されたサイトだとWindowsならブラウザのフォントの設定に関わらずMS Pゴシックで表示されてしまいます。MS PゴシックをWindowsから削除することで指定を回避することもできますが、既存のアプリの表示がおかしくなるなどの互換性の問題があります。また、Firefoxならば

ウェブページが指定したフォントを優先する

のチェックを外せばfont-familyの設定を無視してブラウザに設定したフォントで表示させることができますが、アイコンフォントが文字列に置き換わってしまうという副作用があります。そこで、Chrome、Firefox両方に対応した拡張機能Stylusを用いて気に入らないフォントのみを好みのフォントに置き換えることにします。

環境

Windows 10

ChromeまたはFirefox

フォントをインストールする

Stylusでフォントを置き換える前にフォントをインストールします。ここではゴシック体と明朝体として日本語、韓国語、中国語に対応したNoto Sans CJK JP, Noto Serif CJK JP、等幅フォントとしてPlemolJPをインストールし、MSゴシックなどをこれらに置き換えることにします。

Noto Sans CJK JPはここから、Noto Serif CJK JPはここから、PlemolJPはここからダウンロードできます。*1ダウンロードしたら解凍して.otfファイルを右クリック->すべてのユーザーにインストールを選択してインストールします。*2

Stylusでフォントを置き換える

@font-face { 
 font-family:'置き換えたいフォント'; 
 font-weight: normal;
 src: local('置き換え先のフォント');
}

font-weightで置き換えたいフォントを選びます。太字のフォントを置き換えるにはnormalに代わりboldを指定し、置き換え先のフォントをBoldフォントにします。MSゴシック、MSPゴシック、MS明朝、Yu Gothic UI、メイリオ *3を、なるべく太さや字体を変えずに上でインストールしたフォントに置き換えるスタイルシートは以下のようになります。

@font-face {
    font-family: "Meiryo";
    font-weight: normal;
    src: local("Noto Sans CJK JP");
}
@font-face {
    font-family: "Meiryo";
    font-weight: bold;
    src: local("Noto Sans CJK JP Bold");
}
@font-face {
    font-family: "メイリオ";
    font-weight: normal;
    src: local("Noto Sans CJK JP");
}
@font-face {
    font-family: "メイリオ";
    font-weight: bold;
    src: local("Noto Sans CJK JP Bold");
}
@font-face {
    font-family: "Meiryo UI";
    font-weight: normal;
    src: local("Noto Sans CJK JP");
}
@font-face {
    font-family: "Meiryo UI";
    font-weight: bold;
    src: local("Noto Sans CJK JP Bold");
}
@font-face {
    font-family: "MS PGothic";
    font-weight: normal;
    src: local("Noto Sans CJK JP");
}
@font-face {
    font-family: "MS Pゴシック";
    font-weight: normal;
    src: local("Noto Sans CJK JP");
}
@font-face {
    font-family: "ＭＳ ゴシック";
    src: local("Noto Sans CJK JP");
}
@font-face {
    font-family: "ＭＳ Ｐゴシック";
    font-weight: normal;
    src: local("Noto Sans CJK JP");
}
@font-face {
    font-family: "Yu Gothic UI";
    font-weight: normal;
    src: local("Noto Sans CJK JP");
}
@font-face {
    font-family: "Yu Gothic UI";
    font-weight: bold;
    src: local("Noto Sans CJK JP Bold");
}
@font-face {
    font-family: "游ゴシック";
    font-weight: normal;
    src: local("游ゴシック Medium");
}
@font-face {
    font-family: "Segoe UI";
    font-weight: normal;
    src: local("Noto Sans CJK JP");
}
@font-face {
    font-family: "Segoe UI";
    font-weight: bold;
    src: local("Noto Sans CJK JP Bold");
}
@font-face {
    font-family: "MS PMincho";
    font-weight: normal;
    src: local("Noto Serif CJK JP");
}
@font-face {
    font-family: "ＭＳ Ｐ明朝";
     font-weight: normal;
    src: local("Noto Serif CJK JP");
}
@font-face {
    font-family: "ＭＳ 明朝";
     font-weight: normal;
    src: local("Noto Serif CJK JP");
}
@font-face {
  font-family: "MS Gothic";
  src: local("PlemolJP");
}

どのようにしてフォントを置き換えているのか

@font-face は独自フォントを指定するためのもので、font-familyでフォントの名前、src:でフォントの場所を指定します。ここでは例えばsrc: local("Noto Sans CJK JP");と記述することでフォントの参照先をNoto Sans CJK JPの場所に上書きし、狙ったフォントのみを置き換えています。

*1:Noto Sans CJK JPは2021年12月29日現在、Google Fontsのサイトからダウンロードできなくなっていますが、GitHubには残っているのでそこからダウンロードします。

*2:Firefoxの場合はC:\Users\ユーザー名\AppData\Local\Microsoft\Windows\Fontsを参照してくれるので、右クリック->インストールで問題ありませんが、Chromeの場合はC:\Windows\Fontsのみ参照するためすべてのユーザーにインストールを選択する必要があります。

*3:メイリオをやたら好む人がいますが、私は横幅が広く、線分の太さに差をつけすぎていて嫌いです。そもそもメイリオというフォントはMSゴシックのようなビットマップフォントを避けながら、低DPI環境でも視認性を保つために開発された節があるので、現代の高画素密度なディスプレイには似合いません。

2021-12-29

最初に書くことといえば

Hello, World!