Hatena::Grouptopcoder

ir5は引退した

2015-12-22

topcoder ボツ問供養

23:35

この記事はCompetitive Programming (その2) Advent Calendar 2015の22日目です.

今回は,大昔にtopcoderに出題しようとしていたけど,お蔵入りになってもうどこにも出題する予定がない問題を幾つか紹介します.作問勢の人達は自分のボツ問と比べながら見てみると面白いかもしれませんしそうでもないかもしれません.

  • 元々topcoderで出す予定のものだったのでtopcoderの問題文風に紹介します.ほぼ提案時の原文まんまなので問題文も英語です.全部僕が書いているのでクソ英語の可能性があります.
  • 問題文の前にdiv1換算の推定難易度を載せています.難しいのが多くてヘビーユーザー向けになっちゃってるかもしれませんがすいません.
  • 提案時の問題文なので制約とかあんまりちゃんと書いてません.わざとです.妄想で補ってください.
  • 出題できなかっただけあって微妙なのが多いかもしれません.B級グルメのようなものです.
  • 問題文のあとにコメントを一言だけ載せています.

Easy(250) BipartiteGame

Problem Statement

Fox Ciel and Fox Jiro are playing a game with an undirected graph. Initially, they have a graph represented by graph. Ciel and Jiro take a turn alternately. Ciel take the first turn. In each turn, a player must remove exactly one edge from the graph. If the graph becomes bipartite after a player took the turn, the player loses the game. Return "Ciel" if Ciel wins the game. Otherwise return "Jiro".

Definition

Class: BipartiteGame
Method: whoWins
Parameters: String[]
Returns: String
Method signature: String whoWins(String[] graph)

(be sure your method is public)

Constraints

  • graph will contain between 2 and 50 elements, inclusive.
  • Each element of graph will contain exactly n characters, where n is the number of elements of graph.
  • Each character in graph is either 'Y' or 'N'.
  • graph will contain at least one edge.

コメント:最初から2部の時→自明 / それ以外だとゲームの最後には奇数サイクルだけ残るので辺の個数の偶奇だけみる.普通にいい問題だったと思うけど,忙しかったし準備するのがめんどかったのでやめた.


Easy(250) Eel

Problem Statement

Fox Ciel owns an eel. She wants to observe how vigorous it is.

First, she chooses two integers sx and sy and puts the eel at point (sx, sy). Let t = 0.0 be this time. Because the eel is very vigorous, it moves in each second. In one move, if the eel is at point (x, y), it moves to either (x+1, y) or (x, y+1) or (x-1, y) or (x, y-1). To measure the position of the eel, she uses a special equipment. When the eel is at (x, y), the equipment records the value of max(|x|, |y|).

The observation procedure is done as follows:

  • When t = 0.0, she puts the eel at (sx, sy).
  • When t = 0.5, the eel moves.
  • When t = 1.0, the equipment measures the value.
  • When t = 1.5, the eel moves.
  • When t = 2.0, the equipment measures the value.
  • ...

However, Ciel is afraid that the equipment is broken and the measured values contain wrong data.

You are given an int[] record, whose i-th (0-indexed) element is the value measured at time t = (1.0+i). Return "GOOD" if record is consistent; i.e. there is at least one sequence of moves of the eel that results in record. Otherwise, return "BAD".

Definition

Class: Eel
Method: isGood
Parameters: int[]
Returns: String
Method signature: String isGood(int[] record)

(be sure your method is public)

Constraints

  • sx and sy will be between -10000 and 10000, inclusive.
  • record will contain between 1 and 10000 elements, inclusive.
  • Each element of record is between 0 and 10000, inclusive.

コメント:隣り合う要素の差が1以下であるかと,0の出現インデックスの偶奇だけ見ればconsistentかどうか分かる.これたしか4年位前に提案した問題なんですが,当時はtopcoderの仕様で配列の要素が50までしか詰められなくて,それだと何も考えずに探索すればよくなってつまらんので取りやめた.


Medium(700) PaveRoads

Problem Statement

There are N cities in Randomization Country. The cites are numbered from 0 to N-1. Currently there are no roads between any two cities, so the government of Randomization Country decided to pave roads to connect some pairs of cities. Because the country has not so much budget, the government is going to pave at most N roads.

You are given a String[] roads. If city i can pave a road that connects between city i and city j, roads[i][j] will be 'Y', otherwise, it will be 'N'. It is possible that city i is able to pave a road between city i and city i, i.e., roads[i][i] = 'Y'. The pavage is done by each city executing the following operation.

  1. City i uniformly randomly chooses a city that city i can connect to. Let the index of chosen city be j. Note that it is possible that j equals to i.
  2. City i paves a road between city i and city j. The road will be bidirectorial, thus people in city i can go to city j by the road, and vice versa.

The government wants to know the probability that any two cities are connected directly or indirectly by the roads. Your method must return this probability.

Definition

Class: PaveRoads
Method: getProbability
Parameters: String[]
Returns: double
Method signature: double getProbability(String[] roads)

(be sure your method is public)

Constraints

  • roads will contain between 2 and 14 elements, inclusive.
  • Each element of roads will contain the same number of character with the number of elements of roads.
  • Each character of roads will be either 'Y' or 'N'.
  • Each element of road will contain at least one 'Y' character.

コメント:3^Nでなんかかしこい感じの数え上げDPをする.MediumにしてはむずいがHardにしては典型的な感じがしてアレというなんとも扱いにくい問題だった.

Hard?(900) SymmetricSquare

Problem Statement

Please note that this problem has non-standard time limit and memory limit: 3.0 seconds and 16 megabytes. Note that this should correspond to an actual memory limit of only 4 MB. If your solution allocates more than 4 MB of memory, it may exceed the memory limit.

Fox Ciel has a square board of side length N divided into 1x1 cells. The rows of the board is numbered 0 through N-1 from top to bottom and the columns of the board is numbered 0 through N-1 from left to right. Each cell is colored in some color. The colors are numbered from 0. The color of the cell at row i in column j is denoted by color(i, j). She wants to change the color of some cells so that the board looks the same when she rotates the board by 90 degrees to the counter-clockwise order. That is, she wants to make color(i, j) = color(N-1-j, i) hold for valid i and j. What is the minimum required number of cells to change?

You are given an int N and longs z0, A, B, C and mask. N will be even. Since Ciel's board is large, the initial color of each cell is given by a random number generator. For each i and j, color(i, j) is given by the following pseudo-code.

z = z0
for i = 0 to N-1
  for j = 0 to N-1
    color(i, j) = z & mask
    z = (A * z * z + B * z + C) modulo 2^64
  endfor
endfor

Here, we denote by & by the bitwise AND operator.

Return the minimum required number of cells to change in order to achieve the objective.


Definition

Class: SymmetricSquare
Method: minChanges
Parameters: int, long, long, long, long, long
Returns: int
Method signature: int minChanges(int N, long z0, long A, long B, long C, long mask)

(be sure your method is public)

Constraints

  • N will be an even number between 2 and 7000, inclusive.

コメント:メモリ縛り系.普通にcolor(i,j)を全部求めてから計算すると7000^2*8byte≒400MBくらい必要になって辛いけどうまくやれば(N/2)^2*2bit≒3MB程度でできるようになる,と手記には書かれている.なんで出題しなかったか忘れた.


Hard?(900) Separation

Problem Statement

Fox Ciel has a convex polygon with N vertices on the XY-plane. Each vertex in the polygon is numbered from 0 through N-1 in the counter-clockwise order. Also, there are a red point and a blue point on strictly inside of the polygon. Ciel is going to draw a line on the XY-plane as follows. First, she choose a direction of the line uniformly at random. She then draw a line so that the line divides the polygon into two parts with equal area.

You are given two int[]s px, py and four ints rx, ry, bx, by. The coordinate of vertex i of the polygon is (px[i], py[i]), and the coordinates of the red point and the blue point are (rx, ry) and (bx, by), respectively. Compute and return the probability that the red point and the blue point are not on the line that Ciel draws and they are separated by the line.

Definition

Class: Separation
Method: getProbability
Parameters: int[], int[], int, int, int, int
Returns: double
Method signature: int getProbability(int[] px, int[] py, int rx, int ry, int bx, int by)

(be sure your method is public)

Constraints

  • px will contain between 3 and 50 elements, inclusive.
  • px and py will contain the same number of elements

コメント:解法は忘れたのですが「そういうのはICPCでやりましょう」と言われてまぁそうかもしれないと思ったということだけ覚えています.

未解決(???) ColorfulClay

イカの問題は解けそうな気がしていましたが考えている途中で挫折して想定解がありません.

Problem Statement

Little Fox Jiro has N blocks of soft clay. Each block is colored in distinct color. These colors are numbered 0 to N-1, inclusive.

Initially, Jiro has initAmount[i] grams of a block with color i. Since the clay is soft, he can split it into two separated blocks or combine two clay with the same color into one new clay with some cost. Also, he can repaint any block in another color with no extra cost. The objective in this problem is to obtain desiredAmount[i] grams of a block with color i, for all i, with the minimum cost.

Formally, he can perform one of the following operations as many times as possible.

  • He chooses one block. Let x be the weight of the block. Next, he chooses an arbitrary integer y between 1 and x-1, inclusive. Then he splits the block into two new blocks with weight y and x-y, respectively. This costs y*(x-y).
  • He chooses two blocks with the same color. Let y and z be the weights of the blocks. He combines the blocks to one new block with weight y+z. This costs y*z.
  • He chooses one block and a color j. He then changes the color of the block into color j.

If the objective is infeasible, your method must return -1. Otherwise, return the minimum required cost to achieve the objective.

Definition

Class: ColorfulClay
Method: minCost
Parameters: int[], int[]
Returns: long
Method signature: long minCost(int[] initAmount, int[] desiredAmount)

(be sure your method is public)

Constraints

  • N will be between 2 and 50, inclusive.
  • initAmount and desiredAmount will contain N elements.
  • Each element in initAmount and desiredAmount will be between 1 and 10^6, inclusive.

コメント:元はというとジェームスキッチンでハンバーグを食べながら,クリークの和集合で構成されるグラフの同士のグラフ編集距離がどうなるかというのを考えていた.解けそうな気がしたが,どうせ証明が大変だけど貪欲なんだろうなー頑張って証明してもチキンレースになったらいやだなーとか思って考えるのをやめた.実際に貪欲かどうかは知らないけど.


おわりに

今回は昔のメモ書きをたまたま見返していたらボツ問題がいっぱい出てきたので,供養する目的で公開してみました.

次回は@_ehaさんによる「いろんな人のテンプレートを観察」です.みんなのおもしろテンプレートに期待です.