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さんによる「いろんな人のテンプレートを観察」です.みんなのおもしろテンプレートに期待です.

2014-12-11

問題を難易度表で管理することについて

01:32

この記事は Competitive Programming Advent Calendar 2014 の11日目の記事です.主に ICPC・JAG難易度表(a.k.a. AOJ-ICPC) の話を書きます.難易度表の話は今まで断片的には色んなところに書き記していたのですが,ちゃんとまとめて書いたことがなかった気がするので,この機会にまとめてみようと思います.

難易度表について

ICPC・JAG難易度表ICPC日本地区公式のセットとOB/OG会のセットの一部の問題をまとめ,いくつかの難易度で区切って表示することを目的に作ったページです.現在は Google spreadsheet 上で管理しています.難易度は,不特定多数のユーザーからの投票を受け付け,管理者がそれに基づいていい感じに決めるといったことをしています.

AOJ-ICPC ではICPC・JAG難易度表の問題と AOJ での解答状況を集計して公開しています.各ユーザーの解答状況を見れる他,他人との正解した問題の差分を見る機能(diff)も実装されています.

ここで唐突ですが,去年の会津大会のときに撮影した AOJ の美しいサーバーの様子を御覧ください.

履歴

この難易度表をつくろうと思った理由と,その経緯について記します.ちょっと懐古録みたいになってる気がしないでもないですがご了承下さい.

かなり昔からこのような難易度表を作るモチベはありました.

以下のツイートは2012/9のものですがこれよりも前に似たようなことをつぶやいていた気がします.うろ覚え.

作るモチベの源泉となっているのは音楽ゲーム(特に弐寺,BMS((弐寺の二次創作版みたいものです.)))のコミュニティです.音楽ゲームでは曲が大量にあり,弐寺公式では同じレベル帯にあっても分け方が粗いために上位と下位で難易度に大きな幅があり,曲選びの際に悩みの種になったりします.そんなときに非公式の難易度表を使うと,公式よりも細かい指標で難易度がわかり,曲選びがスムーズに行えたりします.また,BMSでは作者の付けた難易度が作者によってばらばらでよくわからないのでそれらを統一して扱うためであったり,そもそもBMSでは曲が多すぎてどれをダウンロードすればわからないのでそれをまとめる役割を果たしているようです.また,攻略情報などを wiki や掲示板で共有するためのコミュニティとしての役割を果たすというのも重要な要素です.

現時点では様々なサイトがありますが,例えば以下のようなサイトは有名どころでしょう.

…ちょっと話が脱線したので競プロに戻りますが,難易度表が存在するメリットはおおまかに以下のようなものであると考えていました.

  • オンラインジャッジを始めたばかりの初心者にとってはどれを解けばいいか一目で分かりやすい.解いた人数以外の信頼できる指標として使える.
  • 中級者~上級者にとってはひたすら埋めることで修行用に使える.
  • 投票や解法の交換でコンテスタントの地力を上げる.コミュニティを活性化させる.

あと,当時は ICPC や JAG で問題がたくさん生まれていくもののあまり解いている人が居らず,問題を作るばかりではなくて問題を振り返る機会をもう少し大切にしたいなぁという考えもありました.☆の投票があるのは,数多く存在する問題の中でもできるだけ良い問題を残して行きたいといった意図があったりなかったりします.

ただこういう難易度表のためのサイトを作るには多くの場合専用のシステムが必要になり,作るための時間を確保できていませんでした.また,長い時間をかけて作ったとしてもそれを実際に使ってくれる人がどれくらいいるのかもよく分からなかったため,当時の僕は興味がちょっとあったものの手が出せていませんでした.そうした中で @japlj さんが Google Spreadsheet を使ってJOI非公式難易度表を作っていました.いつごろからあったのか忘れましたが少なくとも2012/9の時点では既に存在していたようです.たしかに Spreadsheet を公開設定にして書き込めるようにしておけば投票もできるし編集も柔軟に行えるので,これはなかなか上手い方法だなと思いました.

そういうわけで,比較的暇な時間ができた正月に3日間実家に篭って難易度表のたたき台を作り,Spreadsheet 上で公開しました.

難易度の数字は TopCoder を意識しています.突然新しい指標を作りだしても,難易度の合意が取りづらいのではないかと思ったためです.とはいえ当時はとりあえずたたき台の段階だったので難易度はだいぶ適当だった記憶があります.いかんせん300問近い問題をひよこのオスメス判定のように高速に分けていくのでだんだん自分でも何が難しくて何が簡単なのかわけがわからなくなっていきます.あと難易度もこのときはかなり細かく分けていたのですが,後になってこんなに細かい必要は無いと判断して高難易度の難易度分けはマージされています.

で,驚いたのがこの翌日なのですが,@ichyo さんがこの難易度表と AOJ の解答状況を集計するページを作ります.スピード感があります.

以降は投票とかを地道に反映させたり,なんとなく放置したり,また更新再開させたりしていて,今に至ります.現在は難易度表の管理は @ichyo さんと僕でやっています.

現状

投票でだいぶ票が集まって結構安定してきたように思います.とはいえまだ改善点はありそうです.例えば以下のようなものです.

  • 基準の変更とか,時代の流れで簡単とみなされるようになった問題がまだ上位難易度に残っているのをどうすべきか
  • 難易度の整合性,個人差の扱いどうするか (幾何と数論とか比較しようがないし…)
    • あまり細かいところにこだわっても疲れるだけである
  • 非推薦の問題をもうちょっと賢く決めたい(今は管理者が半分独断で決めているがもう少し合理的にやるべき)

また,最近は diff 埋めといって,ライバルで実力が近い人が解いている問題を順番に埋めていくといった使い方が流行っていて,これもまた面白い使い方だなぁと思います.僕がオンラインジャッジを埋めていた頃はひたすら孤独な修行という印象だったのですが,随分とソーシャルになったものです.

今後の展望とか

現在は @ichyo さんに混ぜてもらって AOJ-ICPC をちょっとずつ変えていっています.今は github のプライベートリポジトリで管理しています.変更分は多分そのうち公開すると思います.

できたら楽しいだろうなぁと思っているのは以下のことです.

  • 投票機能を spreadsheet から移植する
  • 難易度や☆だけではなく,解法の話とかもできるようにする
  • 個人差を可視化する (投票の数値の分散を表示するとか)
  • ICPC・JAG以外の表を作る.例えばJOI版の表を作る.高校生ウケ狙い.
  • これ

…とはいえ僕はもうあまり時間が割けない(しあと立場的にもずっとこれに携わるのはある程度のところでやめたいと思っている)のでどなたかやってくれる人は常時募集しています.とりあえず投票機能の移植くらいまでは実装してしまいたいところです.

まとめ

ちょっと単に僕が昔を思い出すだけっぽい記事になりましたが,まぁみんなゲーム感覚で問題を埋めたり問題について考察とか感想を共有していけば,日本の競プロのレベルも上がるし,楽しいし,なんとなく盛り上がってる感じがするし,細かいことはよく分からないけど,いいんじゃないかと思います.面白い,知的好奇心を刺激する,これは大切なことだと思っています.

アドベントカレンダーの次の担当は @na_o_ys さんの「競プロと出会った一年を振り返る」です.一体どんな一年があったのか気になります.

2014-10-31

ICPC・JAG難易度表更新 & 次の更新について

00:13

https://docs.google.com/spreadsheet/ccc?key=0Ank515IguQc4dGJDR3FYOGZGTXQ5VHhNa1JmMDB4U0E#gid=13

10/26に更新しました.最近の問題が色々追加されています.

次の更新は 12/31 にします.(ペース的には2ヶ月に1回とかがいいのかなぁと思っています)

2014-09-24

ICPC・JAG難易度表の問題追加

23:00

最近全然更新してなかったICPC・JAG難易度表 (a.k.a. AOJ-ICPC) ですが,新しい問題を追加します.春コンテスト2013~模擬地区予選2014までが追加されています.

https://docs.google.com/spreadsheet/ccc?key=0Ank515IguQc4dGJDR3FYOGZGTXQ5VHhNa1JmMDB4U0E#gid=13

まだ難易度よく分かってない問題がほとんどなので,投票をお待ちしています.投票の仕方はスプレッドシートを参照して下さい.10/18(土)あたりで一旦区切りを付けて,難易度表に追加しようかと思います.

で,一つ変更点なのですが,

  • 100, 150点 は div2-easy レベルのもの
  • 素数判定は ≥ 150,DP は ≥ 250,ダイクストラ法は ≥ 400,フローは ≥ 450, やや重い幾何は ≥ 450

という基準を設けていたのですが,これを少し変更しようかと思います.

  • 幅優先探索,ダイクストラ法は ≥ 250~300
  • 最大流,最小費用流は ≥ 400
  • やや重い幾何は ≥ 400

ライブラリが要る問題の最低レベルを下げることにします.

今まではライブラリ化すればテンプレートになる問題でも本質的にそんなに簡単じゃないならあまり下にするべきではないと思っていたのですが,むしろライブラリ化すればいくらでもつぶしが利くようなものは下に置いておいたほうが勉強になるし解ける問題も増えていいだろうと思うので下げることにします(というのをずっと考えていたのですが今になってようやくやる気になったので変えます.)

で,こうすることで表で変更する必要のある箇所が出てくると思うのですが,まだ洗い出せていないのでそれは近いうちに….