SRM145Div2Easy
さて2日目ですが、Div2はやっぱ全然シンプルですね。答え出すだけなら...
Problem Statement |
|||||||||||||
Sometimes when computer programs have a limited number of colors to use, they use a technique called dithering. Dithering is when you use a pattern made up of different colors such that when the colors are viewed together, they appear like another color. For example, you can use a checkerboard pattern of black and white pixels to achieve the illusion of gray. You are writing a program to determine how much of the screen is covered by a certain dithered color. Given a computer screen where each pixel has a certain color, and a list of all the solid colors that make up the dithered color, return the number of pixels on the screen that are used to make up the dithered color. Each pixel will be represented by a character in screen. Each character in screen and in dithered will be an uppercase letter ('A'-'Z') representing a color. Assume that any pixel which is a color contained in dithered is part of the dithered color. |
|||||||||||||
Definition |
|||||||||||||
|
|||||||||||||
Limits |
|||||||||||||
|
|||||||||||||
Constraints |
|||||||||||||
- | dithered will contain between 2 and 26 upper case letters ('A'-'Z'), inclusive. | ||||||||||||
- | There will be no repeated characters in dithered. | ||||||||||||
- | screen will have between 1 and 50 elements, inclusive. | ||||||||||||
- | Each element of screen will contain between 1 and 50 upper case letters ('A'-'Z'), inclusive. | ||||||||||||
- | All elements of screen will contain the same number of characters. | ||||||||||||
Examples |
|||||||||||||
0) | |||||||||||||
|
|||||||||||||
1) | |||||||||||||
|
|||||||||||||
2) | |||||||||||||
|
|||||||||||||
3) | |||||||||||||
|
|||||||||||||
4) | |||||||||||||
|
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public class ImageDithering
{ public int count(String dithered, String[] screen) { int ct = 0; for (int i = 0; i < screen.length; i++) { for (int j = 0; j < screen[i].length(); j++) { for (int k = 0; k < dithered.length(); k++) { if (screen[i].charAt(j) == dithered.charAt(k)) ct++; } } } return ct; } } |
まだちゃんとしたコードのコピペ方法がわかりませんが、とりあえずパッと思い浮ぶのはこれくらいでした。3つもループ使ってるので ~N^3になっちゃってますが10分足らずで書けたのでまあいっか。Hash setを使うといいみたいですが、まだまだ知識不足ですね…
今は結構暇なのでCourseraでAlgorithms Part 1っていう授業取ってます。これで効率のいいコードが書けるようになるといいんですが