昨日は杏ちゃんに水着を着てもらいましたが今日はめがねをプレゼントして様子を見たいと思います。
Paizaのイベント
paiza.jp
サンタコス回
takachan.hatenablog.com
ショートカットに「めがね」きっと似合うと思います。ぐふふ。
めがねにはランキングがあるらしい
どうやら昨今、新進気鋭の言語として巷を席巻しているSwift言語限定で「めがね」の獲得に情熱をたぎらせる紳士の方々の信仰心と技術力が試されるランキングがあるようです。
2015/12/09 23:35分現在の様子はこんな感じです。
・・・・これは！！？
、、、、ただのへっぽこSEが張り合う世界じゃないみたいです。
この世界のことはいったん忘れて、普段使っているc#で杏ちゃんに「めがね」をプレゼントしたいと思います。
頑張るぞー！おー！
・・・
・・・・・・
・・・・・・・・・
やりました！
格闘する事30分！とうとう手に入れました！！！
(今回はVisualStudio上で動作確認していたの1発OKでした！）
何の策も弄さずに事に当たった場合、0.3 ～ 0.4秒かかるみたいです。
解き方
前回記事同じくとしょっぱなからネタバレをすると面白くないので
- 仕様の確認
- 考え方
- コーディング
の順に自分がどうやったのか紹介したいと思います。
(前回と同じく杏ちゃんにプレゼントを贈ることだけを考えているので数学的に云々や効率は置いておきます。)
考え方 その(1) データの扱い方
まずは、グリッド状のデータ扱うためのデータ構造を決めます。
グリッドデータをプログラム扱う方法は大きく分けて2通りあります。
- 1次元配列で扱う
- 2次元配列で扱う
人間が直観的に理解しやすいのが2次元、よりコンピューターのメモリイメージに近いのは1次元かと思います。
今回は「左上から右下にシーケンシャルにアクセスする」プログラムになりそうなので(大して差はないですが)1次元配列で行こうと思います。
考え方 その(2) グリッド比較方法
まず、左上から配列のインデックスをイメージした番号を振ります。
そして、例題にあやかって検索対象の大きさを「4」、比較対象の大きさを「3」とした場合
こんな感じに比較対象と比較するので検索回数は最大4回になります。
(今回は必ず1つ一致するものが含まれているそうなので途中で見つかったら計算を打ちるので「最大で4回」です)
そしてその1回のパターンの中をそれぞれ左上から順番に比較していきます。
もしそれぞれのグリッドの値が途中で不一致になった場合検索を打ち切ります。
なので、この最大値は、
"検索対象のグリッド数"を"N"、"比較対象のグリッド数"を"M"、としてx, y方向ともに、0から(N - M)回ループをすれば良さそうです。
考え方 その(3) 1次元配列を2次元のように扱う
データ定義を1次元にしているため(4)の様なオフセットがある開始位置を特定するため式は
求めたいXの座標を"px"、Yの座標を"py"とした場合以下の通りです。
開始位置(p) = N * py + px
さらにその特定した位置を右上から左下まで順番にアクセスするための指揮は
オフセットからのX座標を"o_px", Y座標を"o_py"とした場合
アクセスしたい位置 (index) = p + M * o_py + o_px
となります。
また、今回は比較回数が最悪値となってもそんなに計算量が多くならなそうなので、特に計算回数を減少させる特別な仕組みは必要なさそうです。なので力技で全件検索を行いたいと思います。
コーディング
だいたいの仕様と考え方を把握したのでコーディングに移ります。
以下完全にネタバレなんで自分でコード書きたい人はご注意を・・・
あ、すいません。先に言っておきますが、1次元配列を採用しておきながら、2重のforループを使って計算がめんどくさくなっただけでした。
これじゃあ2次元配列でも大して変わらないですね。。。
using System; namespace Paiza.Megane { public class AppMain { private static void Main(string[] args) { // 元の画像の読み取り int n = int.Parse(Console.ReadLine()); int[] n_pic = read(n); // 比較する画像読み取り int m = int.Parse(Console.ReadLine()); int[] m_pic = read(m); // 左上から検索開始 int max = n - m; for (int i = 0; i <= max; i++) // y方向 { for (int j = 0; j <= max; j++) // x方向 { if (!check(n_pic, m_pic, j, i, n, m)) { continue; // 不一致の場合次へ移る } Console.WriteLine(i + " " + j); // 回答の出力 //Console.ReadLine(); return; // 結果が出たら即座に終了 } } } // 入力データ読み取り private static int[] read(int n) { int[] data = new int[n * n]; for (int i = 0; i < n; i++) { string[] bs = Console.ReadLine().Split(' '); for (int j = 0; j < bs.Length; j++) { data[i * n + j] = int.Parse(bs[j]); } } return data; } // 比較 private static bool check(int[] n_pic, int[] m_pic, int xp, int yp, int n_len, int m_len) { for (int i = 0; i < m_len; i++) { for (int j = 0; j < m_len; j++) { if (n_pic[(n_len * yp + xp) + i * n_len + j] != m_pic[i * m_len + + j]) { return false; // 不一致の場合検索を打ち切る } } } return true; // 全て一致しているとループを抜けてくる } } }
これで完成です。
おまけ
上記コードでは外していましたがテスト効率向上のため以下のような仕組みを利用しました。
入力データを毎回手入力すると効率が悪すぎますからね…
IEnumerableが取れればListでもよかったのですが、フィールドイニシャライザで宣言するとデータを用意したときに加工に手間がかかるのでyield構文を使って1行分のデータを返しています。
private static bool _isTest = true; // テストデータを使う場合true // テストデータを応答するためのイテレーター private static IEnumerator<string> _a; // Console.ReadLine()の代わりのメソッド private static string _read() { if (_isTest) { if (_a == null) { _a = getTestData().GetEnumerator(); } _a.MoveNext(); return _a.Current; } else { return Console.ReadLine(); } } // テストデータソース定義 private static IEnumerable<string> getTestData() { yield return "4"; yield return "0 0 1 0"; yield return "0 1 1 0"; yield return "0 1 0 1"; yield return "1 1 1 0"; yield return "3"; yield return "0 1 1"; yield return "0 1 0"; yield return "1 1 1"; }
まとめ
当然ですが、0.1秒の世界はこれとは異なるアプローチが必要ですね。
あと400%高速化ですｗ
今回はVisualStudioが使えたのでコーディングが前回より「かなり」楽でした。
Paiza.ioと違いインテリセンスが効いてるのが大きかったです。
