こんにちはー！ニアです。
今回は「paizaオンラインハッカソン7（#_poh 7）にチャレンジしました！（前編）」の続きです。
使用した言語はC#です。
まだ解いていない方は、ネタバレに気を付けてね。
3. ランクB編
3.1. A1: 画像分析（メガネ）
標準入力から入力画像とパターン画像（どちらも値は0か1です）を読み取り、パターン画像と一致する入力画像の部分の左上の座標を出力します。
シンプルに、入力画像の左上から順にパターンマッチングして求めることができます。
using System;
class Program {
static void Main( string[] args ) {
// 入力画像の大きさを読み取ります。
int n = int.Parse( Console.ReadLine() );
// 入力画像を読み取ります。
int[,] img = ReadImg( n );
// パターン画像の大きさを読み取ります。
int m = int.Parse( Console.ReadLine() );
// パターン画像を読み取ります。
int[,] ptn = ReadImg( m );
// 画像のパターンマッチングをします。
int x = 0, y = 0;
bool isMatch = false;
for( y = 0; y <= n - m; y++ ) {
for( x = 0; x <= n - m; x++ ) {
// 入力画像の現在の部分とパターン画像が一致したら、マッチング完了のフラグを立てて、for文から抜け出します。
if( Match( img, ptn, y, x ) ){
isMatch = true;
// xやyが余分にインクリメントされないように、繰り返し文の条件判断で抜け出すのではなく、break文で直ちに抜け出します。
break;
}
}
if( isMatch ) break;
}
// 一致した部分の左上の座標（ y, x ）を出力します。
Console.WriteLine( "{0} {1}", y, x );
}
// 標準入力から画像を読み込みます。
static int[,] ReadImg( int n ) {
int[,] img = new int[n, n];
string[] s;
for( int i = 0; i < n; i++ ) {
s = Console.ReadLine().Split( ' ' );
for( int j = 0; j < n; j++ ) {
img[i, j] = int.Parse( s[j] );
}
}
return img;
}
// 入力画の指定した部分が画像パターンと一致するかどうか調べます。
static bool Match( int[,] img, int[,] ptn, int y, int x ) {
bool ans = true;
int m = ptn.GetLength( 0 );
for( int i = 0; i < m; i++ ) {
for( int j = 0; j < m; j++ ) {
// 一致しない画素を検知した場合、falseを返します。
if( img[y + i, x + j] != ptn[i, j] ) {
ans = false;
break;
}
}
}
return ans;
}
}3.2. A2: ケーキの分割（サンタ服）
標準入力からケーキのサイズ及びケーキを切る向きとその位置を読み取り、切り分けられたケーキの体積の最小値を出力します。
問題文より、ケーキを切る向きは「前面と平行な向き」または「側面と平行な向き」です。それぞれの切る位置を格納するリストを作り、切る位置及び左上と右下の位置をそれぞれ追加して昇順にソートします。そこから幅及び奥行きの長さの最小値を求め、それらと高さから切り分けられたケーキの体積の最小値を求めていきます。
using System;
using System.Collections.Generic;
class Program {
static void Main( string[] args ) {
// ケーキのサイズと分割数を読み取ります。
string[] s = Console.ReadLine().Split( ' ' );
int w = int.Parse( s[0] ); // 横幅
int d = int.Parse( s[1] ); // 奥行
int h = int.Parse( s[2] ); // 高さ
int n = int.Parse( s[3] );
// ケーキを切る位置のリストです。
List<int> wc = new List<int>();
List<int> dc = new List<int>();
// 左上の位置を追加します。
wc.Add( 0 );
dc.Add( 0 );
// 標準入力から切る位置を読み取り、リストに追加します。
for( int i = 0; i < n; i++ ) {
s = Console.ReadLine().Split( ' ' );
// 0 : 側面と平行な方向（ 指定した位置で横幅を分割します ）
if( int.Parse( s[0] ) == 0 ) wc.Add( int.Parse( s[1] ) );
// 1 : 前面と平行な方向（ 指定した位置で奥行を分割します ）
else dc.Add( int.Parse( s[1] ) );
}
// 右下の位置を追加します。
wc.Add( w );
dc.Add( d );
// 左上の位置から昇順にソートします。
wc.Sort();
dc.Sort();
// 分割位置間の長さを求め、切り分け後の横幅及び奥行きの長さ最小値を求めます。
int wmin = w, dmin = d;
for( int i = 1; i < wc.Count; i++ ) {
int wcl = wc[i] - wc[i - 1];
if( wmin > wcl ) wmin = wcl;
}
for( int i = 1; i < dc.Count; i++ ) {
int dcl = dc[i] - dc[i - 1];
if( dmin > dcl ) dmin = dcl;
}
// 切り分け後のケーキの体積の最小値を求め、出力します。
Console.WriteLine( wmin * dmin * h );
}
}4. ランクA編
4.1. A3: 大きな値の階乗の一部を算出（水着）
標準入力から値を読み取り、その階乗の下位9桁（末尾から続く0を除く）を出力します。
シンプルに読み取った値から1まで降順に掛けつつ、10で割り切れなくなるまで10で割って末尾から続く0を取り除き、10憶の余剰で下位9桁分を取り出していくと求まるのでは・・・と思いますが、このプログラムではテストケース4で失敗します。
using System;
class Program {
static void Main( string[] args ) {
int n = int.Parse( Console.ReadLine() );
long ans = 1;
// 階乗を計算します。
while( n > 1 ) {
ans *= n--;
// 末尾から続く0を取り除きます。
while( ans % 10 == 0 ) ans /= 10;
// 下位9桁のみを取り出します。
ans %= 1000000000;
}
Console.WriteLine( ans );
}
}また、1から順に掛けた場合、テストケース1で失敗します。
◆ 掛ける数に含まれる素因数から、2の数と5の数をカウントしよう
掛ける値に含まれる10の素因数こと2の数及び5の数をカウントアップし、その分だけで割ったものを掛けます。そしてカウントアップした2の数と5の数の差分だけ2（2の数が多い場合）もしくは5（5の数が多い場合）を掛けます。
using System;
class Program {
static void Main( string[] args ) {
int n = int.Parse( Console.ReadLine() );
long ans = 1;
// n2 : n!の素因数に含まれる2の数
// n5 : n!の素因数に含まれる5の数
int n2 = 0, n5 = 0, j;
for( int i = 2; i <= n; i++ ) {
j = i;
// 掛ける数の素因数含まれる2の数及び5の数を数え、その分だけ割ります。
while( j % 2 == 0 ) {
n2++;
j /= 2;
}
while( j % 5 == 0 ) {
n5++;
j /= 5;
}
// 掛ける数の素因数から2と5を除いたものを掛けます。
ans *= j;
ans %= 1000000000;
}
// 2の数と5の数を比較します。
// 2が多い場合、5の数との差分だけ2を掛けます。
if( n2 > n5 ) {
n2 -= n5;
while( n2-- > 0 ) {
ans *= 2;
ans %= 1000000000;
}
}
// 5が多い場合、2の数との差分だけ2を掛けます。
else if( n2 < n5 ) {
n5 -= n2;
while( n5-- > 0 ) {
ans *= 5;
ans %= 1000000000;
}
}
Console.WriteLine( ans );
}
}これですべてのテストケースをクリアしました。
◆ 階乗に含まれる素因数は、2の数 ≧ 5の数
2～100000の階乗に含まれる素因数を調べてみたところ、2の数の方が5の数より多いです。よって、先ほどのプログラムの29行目にあるif文に指定した条件式は、nが2以上であれば常に満たすので、37行目～43行目部分を省略しても問題ないです。
| 値 | 素因数分解 | 2の数（1からの累積） | 5の数（1からの累積） |
|---|---|---|---|
| 1 | 1 | 0 | 0 |
| 2 | 2 | 1（1） | 0（0） |
| 3 | 3 | 0（1） | 0（0） |
| 4 | 2^2 | 2（3） | 0（0） |
| 5 | 5 | 0（3） | 1（1） |
| 6 | 2×3 | 1（4） | 0（1） |
| 7 | 7 | 0（4） | 0（1） |
| 8 | 2^3 | 3（7） | 0（1） |
| 9 | 3^2 | 0（7） | 0（1） |
| 10 | 2×5 | 1（8） | 1（2） |
| 11 | 11 | 0（8） | 0（2） |
| 12 | 2^2×3 | 2（10） | 0（2） |
| 13 | 13 | 0（10） | 0（2） |
| 14 | 2×7 | 1（11） | 0（2） |
| 15 | 3×5 | 0（11） | 1（3） |
| 16 | 2^4 | 4（15） | 0（3） |
| 17 | 17 | 0（15） | 0（3） |
| 18 | 2×3^2 | 1（16） | 0（3） |
| 19 | 19 | 0（16） | 0（3） |
| 20 | 2^2×5 | 2（18） | 1（4） |
また、「paizaオンラインハッカソン7（#_poh 7）にチャレンジしました！（前編）」のH2で行ったひと工夫を活用してみましょう。掛ける数の素因数に含まれる5の数の分だけ2の数をカウントダウンすることで、2の数と5の数の差分を求めることができます。
using System;
class Program {
static void Main( string[] args ) {
int n = int.Parse( Console.ReadLine() );
long ans = 1;
int n2 = 0, j;
for( int i = 2; i <= n; i++ ) {
j = i;
// 掛ける数の素因数含まれる2の数をカウントアップし、その分だけ割ります。
while( j % 2 == 0 ) {
n2++;
j /= 2;
}
// 掛ける数の素因数含まれる5の数だけ2の数をカウントダウンし、その分だけ割ります。
while( j % 5 == 0 ) {
n2--;
j /= 5;
}
ans *= j;
ans %= 1000000000;
}
// カウントアップした2の数だけ2を掛けます。
while( n2-- > 0 ) {
ans *= 2;
ans %= 1000000000;
}
Console.WriteLine( ans );
}
}単純そうに見えて、考えさせられる問題でした。
今回はC#でプログラミングしましたが、別の言語でもやってみようかな？
3. ところで、コーディネートはどんな感じ？
私のは髪を茶色のボブヘア、目をたれ目、服装をカーディガンでコーディネートしました。
ってこれ、paizaの漫画に出てくる霧島さんじゃないですかー（笑）
[END]
コメント