A - スーパーICT高校生

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

ある高校にはスーパーICT高校生が通っています。 なぜ彼がそう呼ばれているのかはその高校の生徒の誰も知りません。 手がかりはICTという文字列だけです。けれども、ICTが何の略称なのか分かりません。 生徒たちは一晩考えぬいてICTの本来の意味であると思われる文字列を思いつきました。 しかし眠たい頭で考えたので、その文字列からいくつか文字を省いてICTになるか自信がありません。

生徒たちが考えた文字列 S が与えられるので、それからいくつか文字を省いてICTという文字列が作れるかどうか判定してください。

入力

入力は以下の形式で標準入力から与えられる。

S
  • 1 行目には、生徒たちが考えた文字列 S(1≦|S|≦100) が与えられる。ただし|S|はSの文字数のことである。
  • S は大文字、小文字アルファベットだけからなる。

出力

S からいくつか文字を省いて文字列ICTが作れるならYES、作れないならNOと1行に出力せよ。出力の末尾に改行を入れること。 なお省いてできる文字列の 大文字小文字は区別しない 。

入力例1

InformationAndCommunicationTechnology

出力例1

YES

1文字目と15文字目と28文字目以外を省けばICTが残るので出力はYESとなります。

入力例2

InformationTechnology

出力例2

NO

どのように文字を省いてもICTは作れません。ITcは作れますが順番が違うので間違いです。出力はNOとなります。

入力例3

SinCosTan

出力例3

YES

2文字目と4文字目と7文字目以外を省けばiCTが残ります。大文字小文字は区別しないので出力はYESとなります。

入力例4

Ticket

出力例4

YES

入力例5

InternetTrouble

出力例5

NO
B - 細長いお菓子

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君は細長いお菓子を持っています。このお菓子は N cm の長さのお菓子で、 1 cm ごとにブロックに分かれています。それぞれのブロックには 10^5 種類の味うちのいずれかの味がついていて、左端から i 番目のブロックには A_i 番目の味がついています。

高橋君はこのお菓子から、出来るだけ長い「同じ味のブロックが 2 つ以上含まれない、ひと繋がりになった部分」を切り出したいと思っています。最大で何 cm の部分を切り出すことが出来るでしょうか。ただし、切る場所はブロックとブロックの境界の部分のみとします。

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 ... A_N
  • 1 行目には、お菓子の長さを cm 単位で表した整数 N (1 ≦ N ≦ 10^5) が与えられる。
  • 2 行目には、お菓子の各ブロックの味の情報を表す N 個の整数が空白区切りで与えられる。このうち i 番目の整数 A_i (1 ≦ A_i ≦ 10^5) は、左端から i 番目のブロックの味が A_i 番目の味であることを表す。

部分点

この問題には部分点が設定されている。

  • N ≦ 100 かつ A_i ≦ 100 を満たすテストケースすべてに正解した場合は 50 点が与えられる。
  • N ≦ 1,000 かつ A_i ≦ 1,000 を満たすテストケースすべてに正解した場合は 99 点が与えられる。

出力

高橋君がこのお菓子から切り出すことの出来る「同じ味のブロックが 2 つ以上含まれない、ひと繋がりになった部分」の最大の長さを cm 単位で表す 1 つの整数を 1 行に出力せよ。出力の末尾に改行をいれること。

入力例1

7
1 2 1 3 1 4 4

出力例1

3

2 番目から 4 番目のブロックを含む部分、または 4 番目から 6 番目のブロックを含む部分を切り出すのが最長です。

入力例2

1
100

出力例2

1

切る必要がない場合は切らなくてもかまいません。

C - ロミオとジュリエット

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋王国には N 個の村があり、1 から N の番号がついています。N-1 組の村の間は道で繋がっていて、どの村と村の間も道をいくつか辿ることによって移動できるようになっています。

高橋王国に住んでいるロミオさんとジュリエット君が引っ越しをすることになりました。2 人はとても仲が悪いので出来るだけ離れた村に引っ越したいと思っています。あなたは、2 人がそれぞれどの村に引っ越せば 2 人の住む村の間の距離が最大になるのかを計算してあげてください。ただし「村の間の距離」とは、片方の村からもう片方の村まで行くために通る必要のある道の本数であるとします。

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 B_1
A_2 B_2
:
A_{N-1} B_{N-1}
  • 1 行目には、高橋王国にある村の個数を表す整数 N (2 ≦ N ≦ 10^5) が与えられる。
  • 2 行目から N-1 行では、村どうしをつなぐ道の情報が与えられる。このうち i 行目には、整数 A_i (1 ≦ A_i ≦ N) と B_i (1 ≦ B_i ≦ N) が空白区切りで書かれており、これは村 A_i と村 B_i を繋ぐ道があることを表す。

部分点

この問題には部分点が設定されている。

  • N ≦ 1,000 を満たすテストケースすべてに正解した場合は 40 点が与えられる。

出力

2 人の住む村の間の距離が最大にするときに、ロミオさんが住むべき村とジュリエット君が住むべき村の番号を表す整数を空白区切りで 1 行に出力せよ。出力の末尾に改行をいれること。答えが複数考えられる場合は、そのうちのいずれかを出力すれば良い。

入力例1

10
7 6
3 2
2 4
4 5
8 9
1 8
1 6
1 2
9 10

出力例1

5 10

この入力では、高橋王国は図のような構造をしている。 「10 5」と出力しても正解である。

入力例2

4
1 2
1 3
1 4

出力例2

4 3

この入力では、高橋王国は図のような構造をしている。 「2 3」「3 2」「2 4」「4 2」「3 4」と出力しても正解である。

D - スプリンクラー

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋くんは世界でも有数の広さを誇るお花畑を管理しています。このお花畑には、世界でもっとも美しい花が 1 輪だけ咲いています。 このお花畑の中の点はその世界一の花からの距離で表します。その花から東に x ,南に y 移動した点の位置を (x, y) と表します。 高橋くんは非常に几帳面なので、 x と y が共に整数であるような点 (x, y) には必ず 1 輪の花を植えています。そこ以外には植えていません。

より形式的に言うと、直交座標上の全ての格子点の上に 1 輪の花が植えられていて、原点には世界一の花が植えられています。格子点以外の点に花は植えられていません。

世界一の花は、大量の水を必要とします。そういうわけで高橋くんはお花畑のなかの N 箇所にスプリンクラーを設置することにしました。 どのスプリンクラーも x も y も整数であるような点 (x, y) に設置されます。同じ位置に 2 個以上のスプリンクラーが設置されることはありません。 各スプリンクラーは円形に水をばらまきます。半径を大きくすればそれだけ多くの範囲に水がまかれるのですが、経費がもったいないので、 どのスプリンクラーもギリギリ世界一の花に届くように水をまきます。つまりスプリンクラーがまく水の半径は世界一の花とスプリンクラーの距離と一致します。

高橋くんはスプリンクラーを稼働させた時、何輪の花に水が供給されるのか気になりました。

各スプリンクラーの位置が与えられるので、水が供給される花の個数を求めてください。

入力

入力は以下の形式で標準入力から与えられる。

N
x_1 y_1
x_2 y_2
:
x_N y_N
  • 1 行目には、設置するスプリンクラーの個数 N(1≦N≦10^5) が与えられる。
  • 続く N 行のうち i 行目には 2 つの整数 x_i, y_i(-10^5≦ x_i, y_i ≦ 10^5) が空白区切りで与えられる。これはi番目のスプリンクラーの位置が(x_i, y_i)であることを表す。
  • i \neq j ならば (x_i,y_i) \neq (x_j,y_j)が成り立つ
  • 常に (x_i,y_i) \neq (0, 0)が成り立つ

部分点

この問題には部分点が設定されている。

  • N≦100 かつ -100 ≦ x_i, y_i ≦100 を満たすテストケース全てに正解した場合10点が与えられる。
  • N≦1,000 かつ -1,000 ≦ x_i, y_i ≦1,000 を満たすテストケース全てに正解した場合さらに20点が与えられる。計30点となる。
  • N≦10^5 かつ -1,000 ≦ x_i, y_i ≦1,000 を満たすテストケース全てに正解した場合さらに30点が与えられる。計60点となる。
  • N≦10^5 かつ -10^5 ≦ x_i, y_i ≦10^5 を満たすテストケース全てに正解した場合さらに40点が与えられる。計100点となる。

出力

水が供給される花の個数を1行で出力せよ。出力の末尾に改行を入れること。

入力例1

2
0 1
0 -1

出力例1

9

下図のようになる。緑色の点が水が供給される花である。赤色の点は世界一の花の位置である。 緑と赤は合計で9個ある。

入力例2

2
3 1
1 4

出力例2

74

下図のようになる。

入力例3

4
3 4
4 3
-2 -2
-3 2

出力例3

146

下図のようになる。