実行時間制限: 1 sec / メモリ制限: 292 MB
時は 20XX 年,世界は G○○gle 社の支配によるディストピアである.現在,人々の娯楽はプログラミングコンテストに限られている.例えば,週末に家族で T○pC○der アリーナを訪れるというのはとてもよく見られる光景である.しかし,それは光の世界のプログラミングコンテストの姿に過ぎない.一方で,G○○gle と反抗勢力がぶつかり合う闇の世界では,命をかけたプログラミングコンテストが行われている.
自分も久しぶりにプログラミングコンテストに参加してみよう.足慣らしに,まずは,プログラミングコンテストの結果を処理するプログラムでも書いてみることにしよう.
問題
M 人の参加者が居て N 問の問題から成るプログラミングコンテストを考える.各参加者に関して,各問題を解いているか解いていないかが与えられるので,最も多く問題を解いている人が解いた問題数を出力するプログラムを作成せよ.
入力
入力の最初の行は 2 つの整数 M, N を含む.これは,参加者数と問題数を表す.
続く M 行には,各参加者が各問題を解いているか解いていないかが与えられる.これらの行のうちの i 行目は N 個の 0 か 1 の数字ai, 1, ai, 2, …, ai, N が書かれている.ai, j は以下のような意味を持つ.
- ai, j が 0 の時,参加者 i は問題 j を解いていない.
- ai, j が 1 の時,参加者 i は問題 j を解いている.
出力
最も多く問題を解いている人が解いた問題数を出力せよ.
制約
- 1 ≤ M ≤ 20
- 1 ≤ N ≤ 20
入出力例
入出力例 1
入力例 1:
3 4 1 0 1 0 1 1 1 0 0 0 0 1
入力例 1 に対する出力例:
3
参加者 1 は 2 問(問題 1, 3),参加者 2 は 3 問(問題 1, 2, 3),参加者 3 は 1 問(問題 4)を解いている.最も多く問題をといているのは参加者 2 で,その問題数は 3 であり,3 が正しい出力である.
入出力例 2
入力例 2:
3 4 1 1 1 1 1 1 1 1 1 1 1 1
入力例 2 に対する出力例:
4
全ての参加者が 4 問全てを解いている.最も多く問題を解いている参加者というのは参加者全員であり,その問題数は 4 である.
入出力例 3
入力例 3:
1 1 0
入力例 3 に対する出力例:
0
Problemsetter: 秋葉 拓哉
出典
UTPC 2011実行時間制限: 1 sec / メモリ制限: 292 MB
20XX 年の今,G○○gle 社の世界的な支配により,人々のコミュニケーションは限られており, 例えば,自由に人と情報をやりとりすることは基本的に許されていない. 特に,過去にプログラミングコンテストで名を馳せた強豪たちは,危険と判断され, お互いバラバラにされ,密かに注意深く監視されているという.
自分も,そんな一人であった,ような気がする. しかし実は,自分は記憶を失ってしまっているのだ. 自分が何と名乗っていたか,それすらも思い出せない. 'i' とか 'w' とか括弧とかを使っていた気がするが, それっぽいものを書きだしてみても,しっくりこない. そういえば,今思い出したことには,左右に線対称だった気がするのだ.
問題
'i', 'w', '(', ')' からなる文字列が与えられた時, 一部の文字を他の文字に置き換えて,'i', 'w', '(', ')' からなる左右に線対称な文字列にしたい. 文字の追加や削除は許さず,1 文字を別の 1 文字に変える操作のみを行うことにする. 少なくとも何文字置き換えなければならないかを出力するプログラムを作成せよ.
ここで用いる左右に線対称の定義は,以下とする.
- 以下の文字列は左右に線対称.
- 空文字列
- "i"
- "w"
- 文字列 x が左右に線対称のとき,以下の文字列も左右に線対称.
- "i" x "i"
- "w" x "w"
- "(" x ")"
- ")" x "("
- 以上のもののみが左右に線対称.
ここで,"i" x "i" とは "i" と x と "i" を連結したものを表す. 他のものも同様である.
入力
入力は 'i', 'w', '(', ')' からなる 1 つの文字列である.
出力
置き換えなければならない文字数を表す整数を出力せよ.
制約
- 入力の文字列の長さは 10 以下である.
入出力例
入出力例 1
入力例 1:
(iwi)
入力例 1 に対する出力例:
0
入力例 1 では文字列がはじめから左右に線対称である.
入出力例 2
入力例 2:
ii(((((ww
入力例 2 に対する出力例:
5
入力例 2 では例えば ww((i))ww 等に変更すればよい.
Problemsetter: 秋葉 拓哉
出典
UTPC 2011実行時間制限: 1 sec / メモリ制限: 292 MB
そうだ,僕のハンドルネームは (iwi) だ. 僕は確かに昔にプログラミングコンテストに参加していた. そして,多くの仲間と楽しい時間を過ごした.
確か,仲間たちは全員,美少女だったような気がする. プログラミングコンテストの世界は,僕のハーレムだったような気がする. G○○gle は,僕のハーレムを奪ったのだ,そうに違いない. 昔の仲間の手がかりをつかむためにも,やはりプログラミングコンテストに出なければならない.
G○○gle Code Jam に参加登録することにしよう. 今度の ID には,丸括弧以外の括弧も検討に入れてみよう.
問題
'i', 'w', '(', ')', '{', '}', '[', ']' からなる文字列が与えられた時, その部分列をとって,線対称な文字列を作りたい. 最大で何文字の文字列を作ることができるかを計算するプログラムを作成せよ.
与えられる文字列は, "iwi" という文字列を一度含み,それ以外の部分には 'i' と 'w' を含まない. より形式的には,与えられる文字列は s "iwi" t (s と "iwi" と t を連結したもの)という形で表すことができ, s と t は '(', ')', '{', '}', '[', ']' からなる文字列である. s や t が 0 文字である可能性もある.
作る文字列は,与えられる文字列の部分列をとって作る. 部分列とは,元の文字列からいくつかの文字を取り出し,それらを, 元の文字列に含まれる順番で繋げたものである. 取り出す文字たちは必ずしも元の文字列で連続していなくても良い.
また,作る文字列も,与えられる文字列と同様に,"iwi" という文字列を一度含み, それ以外の部分には 'i' と 'w' は含まないようにしたい.
ここで用いる左右に線対称の定義は,以下とする.
- 以下の文字列は左右に線対称.
- 空文字列
- "i"
- "w"
- 文字列 x が左右に線対称のとき,以下の文字列も左右に線対称.
- "i" x "i"
- "w" x "w"
- "(" x ")"
- ")" x "("
- "{" x "}"
- "}" x "{"
- "[" x "]"
- "]" x "["
- 以上のもののみが左右に線対称.
入力
入力は 'i', 'w', '(', ')', '{', '}', '[', ']' からなり上記の条件を満たす文字列である.
出力
上記の条件を満たし作ることのできる文字列の長さの最大値を出力せよ.
制約
- 入力の文字列の長さは 15 以下である.
入出力例
入出力例 1
入力例 1:
[[[iwi[[[
入力例 1 に対する出力例:
3
"iwi" という文字列しか作ることができない.
入出力例 2
入力例 2:
[{)iwi(]}
入力例 2 に対する出力例:
7
"[)iwi(]" や "{)iwi(}" など 7 文字の文字列を作ることができる.
Problemsetter: 秋葉 拓哉
出典
UTPC 2011実行時間制限: 1 sec / メモリ制限: 292 MB
G○○gle Code Jam は G○○gle 社が年に 1 度開催するコンテストである. 優勝者は G○○gle への入社を許される,世界最高峰のコンテストだ. しかし勿論,それ以外の参加者は帰らぬ者となる.
G○○gle Code Jam では自分の好きなプログラミング言語や処理系を使うことができる. 僕は Defunge という自らが開発したプログラミング言語で参加することにした. この言語を使えば,計算困難な問題はおろか,判定不能な問題ですら解決できる気がしている.
問題
与えられるプログラムが停止するかを判定するプログラムを作成せよ. 与えられるプログラムは,以下で説明するプログラミング言語 Defunge で記述されている.
Defunge のプログラムの命令は 1 文字であり,1 次元の列ではなく 2 次元の格子状に並んでいる. 下図は,Defrunge のプログラムの例である:
6>--v. .^--_@
Defunge の言語仕様は以下のようになっている.
- Defunge のプログラムは、左上のマスから右向きで開始する. (左上のマスの命令が最初に実行される.)
- 命令によって進む向きが上下左右に変更されることがある.
- 端に達したら反対側の端へジャンプする.
- メモリは 0 から 15 までの 1 つの整数を記憶することができる.
- メモリにははじめ 0 が記憶されている.
Defunge の命令は以下の通りである.
- '<' … 実行の向きを左にする.
- '>' … 実行の向きを右にする.
- '^' … 実行の向きを上にする.
- 'v' … 実行の向きを下にする.
- '_' … メモリの値が 0 ならば実行の向きを右に,そうでなければ左にする.
- '|' … メモリの値が 0 ならば実行の向きを下に,そうでなければ上にする.
- '?' … 実行の向きが上下左右のいずれかにランダムに等確率で変更される.
- '.' … 何もしない.
- '@' … プログラムの実行を停止する.
- '0' - '9' … メモリの値を指定の数値にする.
- '+' … メモリの値に 1 を加える,ただし値が 15 だった場合 0 にする.
- '-' … メモリの値から 1 を引く,ただし値が 0 だった場合 15 にする.
入力
入力の最初の行は 2 つの整数 R, C を含む.
続く R 行はプログラムを表す。それぞれ C 文字の文字列を含む。
出力
プログラムが停止する可能性がある場合は YES と出力せよ.
そうでないとき,NO と出力せよ.
制約
- 1 ≤ R ≤ 20
- 1 ≤ C ≤ 20
入出力例
入出力例 1
入力例 1:
2 6 6>--v. .^--_@
入力例 1 に対する出力:
YES
入出力例 2
入力例 2:
2 6 5>--v. .^--_@
入力例 2 に対する出力:
NO
入出力例 3
入力例 3:
2 6 .>--v. .^--?@
入力例 3 に対する出力:
YES
補足
Defunge は Befunge と類似している. Befunge の理解は Defunge の理解を助けるかもしれないが, 異なる点も多いため,注意せよ.
Problemsetter: 秋葉 拓哉