なが月・5日目 - Napier

5日目

午前

ABC128A-Cを解いた。レポートの続きをやるためDをやる時間はとれなかった。

Cはbit全探索の問題で、自分はたぶん初めて実装したと思う。ON/OFF→1/0→全スイッチの状況は0110010..すなわちbin(pattern) for pattern in range(2**N)と表せる（実際はbin()が0b prefixをつけるのでbin(pattern)[2:]であるが）と考えて、スイッチのパターン網羅(2^N) * ある電球につながっている全スイッチについてオンオフチェック(k, 最大N) * 全電球ぶん(M)でO( $MN2^{N}$ )となったがM, N ≦ 10なので間に合うのだった。

http://drken1215.hatenablog.com/entry/2019/06/15/135300ではM本の $x_{s_{i_{1}}} + x_{s_{i_{2}}} + ... + x_{s_{i_{k_{i}}}} \equiv p_{i} \bmod 2$ (ただし $x_{i} = 0, 1$ )からなる連立方程式の解の個数を求めることに帰着する方法が紹介されている。この方法ならO( $M^{2}N$ )となるので一桁多い個数にも対応できる。

線形代数の授業で掃き出し法によって連立一次方程式を解く話をされたときは細かい数字の面倒な計算を機械にやらせるという以上の意義を見出していなかったが、O(2^N)をO(N^3)に落とすとN=20で100倍以上早く解けるということになり、別の問題に帰着することで効率の良い解法が利用できるようにすることの重要性がわかる問題だった。

午後

前回文字列処理を行うつもりはないと書いたが、並列計算で使う巨大な行列をハードコードできるはずもなく、ファイル入出力にあたって文字列を扱うことは避けられないのだった。ファイル入出力は他の言語同様ファイルハンドラを取得して読み書きするもので、fopenで返るのはファイルハンドラのポインタであるというところだけ知っておく必要があった。C#やPythonのstring/str.split()に類似するものとしてstrtok()があるようだが、破壊的メソッドである上初回は配列を引数として与え、2回目以降はNULLを与えることで分割を続行するというもので閉口した。

https://helpx.adobe.com/photoshop/how-to/photoshop-improve-tones-levels.htmlでは白と黒の基準点を変更することでより多くの部分が強い白、強い黒に近づくようにしてコントラストを増す方法を理解した。前回の航空機の写真の場合、すでに白側にピークがあり（壁の色）、黒側にもタイヤがあってディテールが潰れては困るためこの手法は適用できなかった。また全体的に明るさを増すために中間色（グレー）を左にシフトすることは可能だったが、床が白くウォッシュアウトされてしまうためこれも行わなかった。

f:id:napier_0b:20190806172316p:plain

https://helpx.adobe.com/photoshop/how-to/make-colors-pop-in-photo.htmlで行っているように調整レイヤーのレイヤーマスクを塗ることで一部だけ色相を変えることも試みたが、元の写真の段階で暗すぎて色の情報が失われてしまっているのか茶色を鮮やかに出すことはかなわなかった。

次は写真加工ではなくエフェクトに取り組みたい。

レポートは3問だけ解けばよいとの回答を無事いただけたので解き進めたが、線形代数に関する操作が頭から抜けておりあちこち調べ回ることになってしまった。QR分解やった記憶がない...あれ？🤔となりつつもRの定めかたを再発掘し無事A=QRが成立した。しかしなんだかんだで解いている間楽しかったし、やっぱり法学部じゃなくて工学部の情報系学科に進むべきだったなあという後悔は強い。