Time Limit: 2 sec / Memory Limit: 256 MB
問題文
N 人の人が一列に並んだ M 個の座席に座っている。
i(1≦i≦N) 番目の人の座っている座席の両側ともに少なくとも A_i 個の空席が連続して存在することが分かっているとき、 M の最小値を求めよ。
N 人の人がこの順番で並んでいるとは限りません。(13:38)
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 .. A_N
- 一行目には人の数N(1≦N≦100000)が与えられる。
- 二行目には文章中で示された値 A_i(1≦A_i≦1000000000) が空白区切りで与えられる。
配点
この問題に部分点はありません。すべてのテストケースに正解すると100点です。
出力
座席数 M として考えられる最小値を答えよ。末尾に改行を入れること。
入力例1
3 2 3 2
出力例1
13
入力例2
5 6 6 9 7 4
出力例2
46
入力例3
10 10 6 6 10 3 8 8 9 4 2
出力例3
86
Time Limit: 1 sec / Memory Limit: 256 MB
問題文
半角英小文字からなる文字列がm個与えられる。
文字列1つにつき1つ、計m個の頂点からなる根付き木であって、
- 葉以外の頂点はちょうど2つの子を持つ
- 頂点iが頂点cの親のとき、 i 番目の文字列の最後の文字が c 番目の文字列の最初の文字に一致する
が成立するような木が存在するか判定せよ。
存在するときは構成せよ
13:35 問題文の誤字を修正
申し訳ありませんが、B問題のテストケースに間違いがあったため、テストケースを16:30より追加します。(16:10)
入力
入力は以下の形式で標準入力から与えられる。
N s_1 . . . s_N
- 一行目には文字列の数 N(1≦N≦10^4) が与えられる。
- 続く N 行には、文字列が与えられる。 i+1 (1≦i≦N) 行目にはi 番目の文字列が与えられる。
- それぞれの文字列の長さは1文字以上10文字以下である。
部分点
この問題に部分点は存在しない。
コンテストへの影響を鑑みて、従来のテストケースに99点、全てのテストケースに1点とします。(16:32)
出力
出力は標準出力に行い、末尾に改行を入れること。
条件を満たす木が存在しない場合、1行目に"NO"と出力する。
条件を満たす木が存在する場合、出力はN+1 行からなる。 1行目に"YES"と出力し、その後 i+1 (1≦i≦N) 行目にi番目の文字列の親の番号を出力する。もしi番目の文字列が根なら0を出力する。
入力例1
5 ab bc bd de df
出力例1
YES 0 1 1 3 3
入力例2
7 yokozuna takayuta namonaki reew semiexp snuke tozangezan
出力例2
NO
入力例3
1 i
出力例3
YES 0
Time Limit: 4 sec / Memory Limit: 256 MB
問題文
多角形の中の格子点を数えることに興味を持っていたすぬけ君はピックの定理を知り、 格子点に対する興味を失ってしまった。
そこで、すなけ君はすぬけ君を励ますために特別な平面を用意した。
彼が用意した平面は xy 平面の x,y≧0 を満たす領域であったが、その格子点(a,b)の各々の上には (0,0)から格子点だけを通って↑と→にだけ進んで(a,b)に到達する方法の数、すなわち_{a+b}C_aという値が割り当てられていた。
すぬけ君はこの平面をとても気に入り、すなけ君にたくさんの質問をしてきた。
すぬけ君「この平面の端（二つの軸）とax+by=cという直線に囲まれた領域の直角三角形の内部と周上に存在する格子点に書かれている値の和っていくつ？」
すなけ君「こらこらそんな大きな数言ってもわからないでしょ。落ち着きなさい。」
すぬけ君「やだー。じゃあ mod 1000000007 でいいから答えて！」
すなけ君はこんなにすぬけ君がはしゃぐとは思っていませんでした。すなけ君の代わりにすぬけ君の質問に答えてください！
入力
入力は以下の形式で標準入力から与えられる。
Q a_1 b_1 c_1 . . . a_Q b_Q c_Q
- 一行目にはクエリの数 Q(1≦Q≦1000000) が与えられる。
- 続く Q 行には、クエリの情報が与えられる。 i+1 (1≦i≦Q) 行目にはi 個目のクエリの情報が与えられ、a_ix+b_iy=c_i (1≦a_i,b_i,c_i≦10000) がすぬけ君の質問する直線を表している。
配点
この問題には部分点がありません。すべてのテストケースに正解すれば100点です。
出力
i(1≦i≦Q) 行目には i 個目のクエリに対する答えを一行に出力せよ。mod 1000000007 で答えることに注意すること。また、出力の末尾に改行を入れること。
入力例1
3 7 10 8 6 3 6 1 5 2
出力例1
2 4 3
入力例2
5 10 4 7 8 1 3 4 4 7 1 10 5 8 8 5
出力例2
2 4 3 6 1
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
すぬけ君はIOI(International Olympiad in Inverting)にh-1人の選手を引率して団長として参加することになった。
IOIでは縦 h× 横 w の大きさの反転パズルを団長と選手が協力して解く。 具体的には団長と選手合わせてh人がそれぞれ1行ずつ担当し、その行のマス目だけ押すことができる。
さて、IOIのコンテストはいよいよ明日になったがすぬけ君は急用で帰国しなければならなくなった。 幸いまぬけ君もチームに同行していたのですぬけ君の代わりにコンテストに参加してくれることになったが、まぬけ君はまぬけなので反転パズルを解くことができない。
そこですぬけ君は反転パズルの初期状態と団長の担当する行番号を入力するとまぬけ君の押すべきマス目の列番号の一覧を出力してくれる機械を作ることにした。
ただし、反転パズルとは白黒に塗られた盤面が与えられ、各人が担当する行のマスを選び、選ばれたマス及びそのマスに辺で隣接するマスの白黒を反転することを繰り返し、最終的にすべてのマスを白にすることを目的とするパズルである。
入力
入力は以下の形式で標準入力から与えられる。
w h r
a
x_1 b_1 y_{1,1} y_{1,2} ... y_{1,b1}
...
...
x_a b_a y_{a,1} y_{a,2} ... y_{a,b_a}
一行目の入力は、w,h はそれぞれ盤面の列と行の数を、r は団長の担当する行番号を表している。
二行目以降の入力は盤面が1≦i≦a,1≦j≦b_iについてマス(x_i,y_{i,j})は黒マスでそれ以外は白マスであることを表している。
- 1 ≦ w ≦ 60
- 1 ≦ h ≦ 1000000000000000000 (=10^{18})
- 1 ≦ r ≦ h
- 1 ≦ a ≦ 100
- 1 ≦ i ≦ a に対して
- 1 ≦ x_i ≦ h
- 1 ≦ b_i ≦ w
- 1 ≦y_{i,1} < y_{i,2} < ... < y_{i,{bi}} ≦w
- x_i ≠ x_j(i ≠ j)
部分点制約
subtask1(10点):w,h ≦10
subtask2(25点):h ≦10000
subtask3(10点):h ≦1000000
subtask4(25点):a ≦10
subtask5(15点):a ≦50
subtask6(15点):追加の制約はない
出力
出力は以下の形式。
n y_1 y_2 ... y_n
まぬけ君が r 行の y_1,y_2,...,y_n 列のn個のマスを押すと、選手がある押し方をした時に反転パズルが解けるとき出力は正解とみなされる。
ただし、 y_1,y_2,...,y_n は昇順で出力すること。(15:13)
ただし、与えられる入力に対して条件を満たす出力は一意に存在する。
入力例1
3 3 1 3 1 1 2 2 1 1 3 1 3
出力例1
1 2
入力例2
3 3 2 3 1 1 2 2 1 1 3 1 3
出力例2
2 1 3
入力例3
3 3 3 3 1 1 2 2 1 1 3 1 3
出力例3
2 2 3
入力例4
10 10 5 3 3 2 5 7 5 4 1 4 6 9 6 1 10
出力例4
5 2 4 5 6 10
Time Limit: 6 sec / Memory Limit: 512 MB
問題文
IOI2015の開催されたアルマトイは昔、Верный(ヴェールヌイ)という名前であった。
どうやらロシア語で「忠実な」とか「信頼できる」とかいった意味があるらしい。。
joisinoお姉ちゃんは、これを聞いて、部下が自分にいかに忠実かを試そうとした。
まず、木Xと木Yを用意した。各頂点は0から(木の頂点数-1)までの名前がついており、'a'から'j'までのどれかの小文字のアルファベットが一つ書かれている。
以下の操作をQ回行う。
例えば、'a'と'b'を入れ替えると、パス上の'a'は'b'となり、'b'は'a'となる。
例えば、'a'と'b'を入れ替えると、パス上の'a'は'b'となり、'b'は'a'となる。
ただし、(このクエリを処理する前に処理したクエリの数)≧a≧0とする。
制限
1≦Q≦10^5
1≦(木Xの頂点数)≦10^5
1≦(木Yの頂点数)≦10^5
配点
- この問題に部分点は存在しない。すべてのテストケースに正解すると100点が得られる。
入力
入力は以下の形式で標準入力から与えられる。
木Xについてのデータ 木Yについてのデータ Q クエリ1 クエリ2 . . . クエリQ始めに、木Xについてのデータが与えられる。
その次に、木Yについてのデータが与えられる。
その次に、クエリ数を指す整数Qが1行で与えられる。 その次のQ行は各クエリを意味する。
各木のデータは、以下の形式で与えられる。
N s a_1 b_1 a_2 b_2 . . . a_N-1 b_N-1データ内の1行目に、木の頂点数Nが整数で与えられる。
次の1行に、長さNの文字列sが与えられる。この文字列のi+1文字目(0≦i＜N)は、木の頂点iに書かれている小文字を指す。
次のN-1行の各行は、木の辺を意味する。
a_iとb_iは、頂点a_iと頂点b_i(0＜i≦N-1)の間に辺があることを意味する。
各クエリは1行から与えられる。 まず、初めにクエリの種類を指す整数tが与えられる。
- tが0の時
空白区切りでこの後に整数a,bと小文字c,dがこの順で与えられる。 これは、木Xの頂点a,b間のパス上の頂点(a,b含む)それぞれにおいて、cが書かれている場合dに、dが書かれている場合cに書き換えることを意味する。 - tが1の時
空白区切りでこの後に整数a,bと小文字c,dがこの順で与えられる。 これは、木Yの頂点a,b間のパス上の頂点(a,b含む)それぞれにおいて、cが書かれている場合dに、dが書かれている場合cに書き換えることを意味する。 - tが2の時
空白区切りでこの後に整数a,bと小文字c,dがこの順で与えられる。 これは、(木Xの頂点a,b間のパス上の頂点(a,b含む)に書かれている文字を、aから順に並べたときの文字列)と(木Yの頂点c,d間のパス上の頂点(c,d含む)に書かれている文字を、cから順に並べたときの文字列)が一致するかしないかを答えることを意味する。 - tが3の時
空白区切りでこの後に整数aが与えられる。 これは、木Xと木Yを、a回クエリを処理した直後の状況に戻すことを意味する。
出力
それぞれのクエリにおいてtが2のとき、文字列が一致する場合"YES"、一致しない場合"NO"を1行に出力せよ。
なお入力全体の最後には改行を忘れないこと。
入力例1
4 ckdl 0 2 0 1 1 3 4 lckd 2 1 1 3 2 0 4 2 2 3 3 0 2 2 3 0 3 2 3 2 0 3 2 3 2 3 0
出力例1
YES NO YES NO