実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
0 以上 255 以下の整数 A,B が与えられます。 A \text{ xor }C=B となる 0 以上の整数 C を求めてください。
なお、そのような C はただ 1 つ存在し、0 以上 255 以下であることが証明されます。
\text{ xor } とは
整数 a, b のビットごとの排他的論理和 a \text{ xor } b は、以下のように定義されます。
- a \text{ xor } b を二進表記した際の 2^k (k \geq 0) の位の数は、a, b を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
制約
- 0\leq A,B \leq 255
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
答えを出力せよ。
入力例 1
3 6
出力例 1
5
3 は 二進表記で 11、5 は二進表記で 101 なので、これらの \text{xor} は二進表記で 110 であり、十進表記で 6 です。
このように、3 \text{ xor } 5 = 6 となるので、答えは 5 です。
入力例 2
10 12
出力例 2
6
Score : 100 points
Problem Statement
You are given integers A and B between 0 and 255 (inclusive). Find a non-negative integer C such that A \text{ xor }C=B.
It can be proved that there uniquely exists such C, and it will be between 0 and 255 (inclusive).
What is bitwise \mathrm{XOR}?
The bitwise \mathrm{XOR} of integers A and B, A\ \mathrm{XOR}\ B, is defined as follows:
- When A\ \mathrm{XOR}\ B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if exactly one of A and B is 1, and 0 otherwise.
Constraints
- 0\leq A,B \leq 255
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
A B
Output
Print the answer.
Sample Input 1
3 6
Sample Output 1
5
When written in binary, 3 will be 11, and 5 will be 101. Thus, their \text{xor} will be 110 in binary, or 6 in decimal.
In short, 3 \text{ xor } 5 = 6, so the answer is 5.
Sample Input 2
10 12
Sample Output 2
6
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
相異なる二つの文字列 S, T が与えられます。
S が T よりも辞書順で小さい場合は Yes を、大きい場合は No を出力してください。
辞書順とは？
辞書順とは簡単に説明すると「単語が辞書に載っている順番」を意味します。より厳密な説明として、相異なる文字列 S と文字列 T の大小を判定するアルゴリズムを以下に説明します。
以下では「 S の i 文字目の文字」を S_i のように表します。また、 S が T より辞書順で小さい場合は S \lt T 、大きい場合は S \gt T と表します。
- S と T のうち長さが短い方の文字列の長さを L とします。i=1,2,\dots,L に対して S_i と T_i が一致するか調べます。
- S_i \neq T_i である i が存在する場合、そのような i のうち最小のものを j とします。そして、S_j と T_j を比較して、 S_j がアルファベット順で T_j より小さい場合は S \lt T 、大きい場合は S \gt T と決定して、アルゴリズムを終了します。
- S_i \neq T_i である i が存在しない場合、 S と T の長さを比較して、S が T より短い場合は S \lt T 、長い場合は S \gt T と決定して、アルゴリズムを終了します。
なお、主要なプログラミング言語の多くでは、文字列の辞書順による比較は標準ライブラリに含まれる関数や演算子として実装されています。詳しくは各言語のリファレンスをご参照ください。
制約
- S, T は英小文字からなる長さ 1 以上 10 以下の相異なる文字列である。
入力
入力は以下の形式で標準入力から与えられる。
S T
出力
S が T より辞書順で小さい場合は Yes を、大きい場合は No を出力せよ。
入力例 1
abc atcoder
出力例 1
Yes
abc と atcoder は 1 文字目が同じで 2 文字目が異なります。 アルファベットの b は t よりもアルファベット順で先に来るので、 abc の方が atcoder よりも辞書順で小さいことがわかります。
入力例 2
arc agc
出力例 2
No
入力例 3
a aa
出力例 3
Yes
Score : 100 points
Problem Statement
You are given two different strings S and T.
If S is lexicographically smaller than T, print Yes; otherwise, print No.
What is the lexicographical order?
Simply speaking, the lexicographical order is the order in which words are listed in a dictionary. As a more formal definition, here is the algorithm to determine the lexicographical order between different strings S and T.
Below, let S_i denote the i-th character of S. Also, if S is lexicographically smaller than T, we will denote that fact as S \lt T; if S is lexicographically larger than T, we will denote that fact as S \gt T.
- Let L be the smaller of the lengths of S and T. For each i=1,2,\dots,L, we check whether S_i and T_i are the same.
- If there is an i such that S_i \neq T_i, let j be the smallest such i. Then, we compare S_j and T_j. If S_j comes earlier than T_j in alphabetical order, we determine that S \lt T and quit; if S_j comes later than T_j, we determine that S \gt T and quit.
- If there is no i such that S_i \neq T_i, we compare the lengths of S and T. If S is shorter than T, we determine that S \lt T and quit; if S is longer than T, we determine that S \gt T and quit.
Note that many major programming languages implement lexicographical comparison of strings as operators or functions in standard libraries. For more detail, see your language's reference.
Constraints
- S and T are different strings, each of which consists of lowercase English letters and has a length of between 1 and 10 (inclusive).
Input
Input is given from Standard Input in the following format:
S T
Output
If S is lexicographically smaller than T, print Yes; otherwise, print No.
Sample Input 1
abc atcoder
Sample Output 1
Yes
abc and atcoder begin with the same character, but their second characters are different. Since b comes earlier than t in alphabetical order, we can see that abc is lexicographically smaller than atcoder.
Sample Input 2
arc agc
Sample Output 2
No
Sample Input 3
a aa
Sample Output 3
Yes
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
N 個の整数 A_1, A_2, \ldots, A_N が与えられます。 このうち最大でない整数の中で最大である整数を求めてください。
ただし、この問題の制約下で答えは必ず存在します。
制約
- 2 \leq N \leq 100
- 1 \leq A_i \leq 100
- A_1, A_2, \ldots, A_N がすべて等しいということはない
- 入力値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
答えを出力せよ。
入力例 1
5 2 1 3 3 2
出力例 1
2
2,1,3,3,2 の中で最大である整数は 3 です。
2,1,3,3,2 の中で 3 でない整数は 2,1,2 の 3 つであり、これらの中で最大である整数は 2 です。
入力例 2
4 4 3 2 1
出力例 2
3
入力例 3
8 22 22 18 16 22 18 18 22
出力例 3
18
Score : 200 points
Problem Statement
You are given N integers A_1, A_2, \ldots, A_N. Find the largest among those integers that are not the largest.
The constraints of this problem guarantee that the answer exists.
Constraints
- 2 \leq N \leq 100
- 1 \leq A_i \leq 100
- It is not the case that all A_1, A_2, \ldots, A_N are equal.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
Print the answer.
Sample Input 1
5 2 1 3 3 2
Sample Output 1
2
The largest integer among 2,1,3,3,2 is 3.
The integers that are not 3 among 2,1,3,3,2 are 2,1,2, among which the largest is 2.
Sample Input 2
4 4 3 2 1
Sample Output 2
3
Sample Input 3
8 22 22 18 16 22 18 18 22
Sample Output 3
18
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
文字列 S が与えられます。
S の連続する部分文字列のうち、回文であるものの長さの最大値を求めてください。
ただし、S の連続する部分文字列であって回文であるものは常に存在します。
制約
- S は長さ 2 以上 100 以下の英大文字からなる文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを出力せよ。
入力例 1
TOYOTA
出力例 1
5
TOYOTA の連続する部分文字列 TOYOT は長さ 5 の回文です。
TOYOTA の唯一の長さ 6 の連続する部分文字列 TOYOTA は回文でないので、5 を出力します。
入力例 2
ABCDEFG
出力例 2
1
すべての長さ 1 の連続する部分文字列は回文です。
入力例 3
AAAAAAAAAA
出力例 3
10
Score : 200 points
Problem Statement
You are given a string S.
Find the maximum length of a contiguous substring of S that is a palindrome.
Note that there is always a contiguous substring of S that is a palindrome.
Constraints
- S is a string of length between 2 and 100, inclusive, consisting of uppercase English letters.
Input
The input is given from Standard Input in the following format:
S
Output
Print the answer.
Sample Input 1
TOYOTA
Sample Output 1
5
TOYOT, a contiguous substring of TOYOTA, is a palindrome of length 5.
TOYOTA, the only length-6 contiguous substring of TOYOTA, is not a palindrome, so print 5.
Sample Input 2
ABCDEFG
Sample Output 2
1
Every contiguous substring of length 1 is a palindrome.
Sample Input 3
AAAAAAAAAA
Sample Output 3
10
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
正整数 N と、長さ N の整数列 A=(A_1,A_2,\dots,A_N) が与えられます。
A の空でない連続部分列であって、同じ値を複数個含むようなものが存在するか判定してください。存在するならばそのようなもののうち最も短いものの長さを求めてください。
制約
- 1\leq N\leq 2\times 10^5
- 1\leq A_i\leq 10^6 (1\leq i\leq N)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \dots A_N
出力
問題文中の条件を満たす連続部分列が存在しないならば -1 と出力せよ。存在するならば、そのようなもののうち最も短いものの長さを出力せよ。
入力例 1
5 3 9 5 3 1
出力例 1
4
(3,9,5,3) と (3,9,5,3,1) が条件を満たします。短いのは (3,9,5,3) で、その長さは 4 です。
入力例 2
4 2 5 3 1
出力例 2
-1
条件を満たす連続部分列は存在しません。
入力例 3
10 1 1 2 3 5 8 13 21 34 55
出力例 3
2
Score : 300 points
Problem Statement
You are given a positive integer N and an integer sequence A = (A_1,A_2,\dots,A_N) of length N.
Determine whether there exists a non-empty (contiguous) subarray of A that has a repeated value, occurring multiple times in A. If such a subarray exists, find the length of the shortest such subarray.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^6 \ (1 \leq i \leq N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \dots A_N
Output
If there is no (contiguous) subarray satisfying the condition in the problem statement, print -1. Otherwise, print the length of the shortest such subarray.
Sample Input 1
5 3 9 5 3 1
Sample Output 1
4
(3,9,5,3) and (3,9,5,3,1) satisfy the condition. The shorter one is (3,9,5,3), which has length 4.
Sample Input 2
4 2 5 3 1
Sample Output 2
-1
There is no subarray that satisfies the condition.
Sample Input 3
10 1 1 2 3 5 8 13 21 34 55
Sample Output 3
2