paizaオンラインハッカソン7(#_poh 7)にチャレンジしました!(後編)

  |   2015/12/24 ( 2019/01/05 ) | 253 views
 0

こんにちはー!ニアです。

今回は「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の数が多い場合)を掛けます。

POH7-A3

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)

POH7-A3b

POH7-A3c

また、「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. ところで、コーディネートはどんな感じ?

私のは髪を茶色のボブヘア、目をたれ目、服装をカーディガンで霧島さん(POH3・6)スタイルにコーディネートしました。

https://paiza.jp/poh/ando/share/9f831288

ando-ann

それでは、See you next!

この記事をシェアする
Chronoir.netのRSSフィードを購読する

ニア(Nia)

ゲーム系の開発&運用エンジニア(目指すはフルスタック)。主にC#(Unity)/PHPを使っています。最近はDockerやKubernetes、プライベートではAndroid Wearアプリやモバイルアプリ開発(Xamarin)を探求中。好物は紅茶とコーヒー、シラス丼、趣味は写真撮影と音ゲーです

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

*

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください