はじめに
ｵｲｲｲｲｲｲｲｲｲｲｲｲｯｽ！どうも、歌うプログラマのことり兄貴(・8・)です！
「AtCoder Beginner Contest 197」、お疲れさまでした～
昨日はかなりやらかしました...
レート-30...
バタバタしてたので動画もないですｗ
まあ2完でしたが、Cまで書いてみたいと思います。
今回はJavaとPythonの両方で書いてみます。
目次
1.A - Rotate
2.B - Visibility
3.C - ORXOR
4.おわりに
1. A - Rotate
問題
長さ3の文字列Sが与えられます。
Sの先頭の文字を末尾に移動した文字列を出力してください。
制約
・Sは英小文字のみからなる長さ3の文字列
A問題リンク
考察
文字列のインデックス番号で考えます。
3文字の文字列の元のインデックス番号は0, 1, 2とする
↓
先頭(0)を末尾に移動
↓
1, 2, 0の順で並ぶ
ことり兄貴(・8・)の解答(Java)
import java.util.*;
class Main {
public static void main(String[] ktr) {
Scanner sc = new Scanner(System.in);
char[] c = sc.next().toCharArray();
System.out.println(new String(c, 1, 2) + c[0]);
}
}
char同士の足し算だと文字コードの和を出力してしまうので、インデックス1から2文字をStringに変換し文字列の足し算にしています。
ことり兄貴(・8・)の解答(Python)
s = input()
print(s[1:] + s[0])
PythonだとJavaでいうchar配列的な動き初めからができて、1:で1以降という表記ができるのが便利ですね。
2. B - Visibility
問題
縦H行、横W列のマス目があり、いくつかのマスには障害物(#)が置かれています。
障害物がないマスは.で表されます。
H個の文字列(S[1]~s[H])が与えられます。この文字列の上からi行目、左からj行目
をマスを(i, j)とします。現在地は(X, Y)です。
現在地から見えるマスはいくつありますか。
見えるとはXまたはYの座標が一致していて、現在地そのマスの間に障害物が
存在しないことを意味します。
制約
・1 <= H <= 100
・1 <= W <= 100
・1 <= X <= H
・1 <= Y <= W
・S[i]は.と#のみで構成される長さWの文字列
・マス(X, Y)に障害物はない
B問題リンク
やらかした
えー、筆者ここで盛大にやらかしました。
この問題においてXは縦の座標、Yは横の座標を示します。
問題文をよく読まずに「Yは縦の座標で、Xは横の座標」という前提でコードを書いて、40分以上苦闘しました...ふと問題をよく見て「逆だったのかあああ...」ってなりましたｗ
問題文はよく読みましょう(自戒)
考察
まず、この系統の問題は外側を障害物(#)で囲んでおくのが無難です。
なくても色々範囲とかに気を付ければ解けなくもないと思いますが、楽に行きましょう。
囲んでしまうことで「障害物が見つかるまでループ」という条件がすべてのテストケースに対応できるようになります。
囲んでからは
・縦の座標を固定した状態で現在地から障害物の直前まで左に進む。
-->見つかったら折り返し始める。障害物のないマスを1つ通過するたびに答えを1増やす。
・横の座標を固定した状態で現在地から障害物の直前まで上に進む。
-->見つかったら折り返し始める。障害物のないマスを1つ通過するたびに答えを1増やす。
とすれば答えが出ます。
ただし、この数え方では初期のマス(X, Y)を2回数えてしまっているので出力の際は-1を忘れずに。
ことり兄貴(・8・)の解答(Java)
import java.util.*;
class Main {
public static void main(String[] ktr) {
Scanner sc = new Scanner(System.in);
int h, w, x, y, ans, i;
h = sc.nextInt();
w = sc.nextInt();
x = sc.nextInt();
y = sc.nextInt();
ans = 0;
char[][] map = new char[h + 2][w + 2];
Arrays.fill(map[0], '#');
for (i = 1; i <= h; i++) map[i] = ('#' + sc.next() + '#').toCharArray();
Arrays.fill(map[h + 1], '#');
i = y;
while (map[x][i - 1] != '#') i--;
while (map[x][i] != '#') {
ans++;
i++;
}
i = x;
while (map[i - 1][y] != '#') i--;
while (map[i][y] != '#') {
ans++;
i++;
}
System.out.println(ans - 1);
}
}
mapって名付けてる二次元配列がS[1]~S[H]を含む配列です。
forやwhileで{}省略して横にくっつけてるのはご了承くだされ～
ことり兄貴(・8・)の解答(Python)
h, w, x, y = map(int, input().split())
ans = 0
s = []
s.append('#' * (w + 2))
for _ in range(h):
s.append('#' + input() + '#')
s.append('#' * (w + 2))
i = y
while s[x][i - 1] != '#':
i -= 1
while s[x][i] != '#':
ans += 1
i += 1
i = x
while s[i - 1][y] != '#':
i -= 1
while s[i][y] != '#':
ans += 1
i += 1
print(ans - 1)
横にちょっと短くなるぐらいでJavaとそんなに変わりませんね。
3. C - ORXOR
問題
長さNの数列Aが与えられます。
この数列を、1つ以上の空でない連続した区間に分けます。
その後、分けた各区間で、区間内の数のビット単位ORを計算します。
こうして得られたすべての値のビット単位XORとして考えられる最小値を求めてください。
制約
・1 <= N <= 20
・0 <= A[i] <= 2の30乗
・入力に含まれる値は全て整数である
考察
制約の1つ目(1 <= N <= 20)は、「あ、ビット全探索っぽいな」ってなるやつで、2つ目(0 <= A[i] <= 2の30乗)は「32ビット型(Javaでいうint)に収まる値が入力されるんだなぁ」ってなるやつです。
「1つ以上の空でない連続した区間に分ける」というのは
1 2 3という数列があるなら
※ここでは | を仕切りとして使います
1 2 3
1 2|3
1|2 3
1|2|3
といったようにグループ分けするイメージですね。
この仕切りをビット全探索(後述)用いることによって再現します。
OR ? XOR?
区間に分けることについては考えましたが、そもそも「ORとかXORってなに？」ってことについて軽く説明します。
ORは論理和、XORは排他的論理和と呼ばれるものです。
OR
A OR BとはAとBを2進数表記したときにAとBのどちらかに1がある桁は1、どちらも0の桁は0とするものです。
例えば3 OR 5を考えると
3 -> 011
5 -> 101
7 <- 111
といった感じです。
XOR
A XOR BとはAとBを2進数表記したときにAとBの一方のみが1である桁は1、AとBに同じ数がある桁は0とするものです。
例えば3 XOR 5を考えると
3 -> 011
5 -> 101
6 <- 110
といった感じです。
ただこれは式さえ書けばあとはプログラムが処理してくれるので、軽く「そうなんだ」ぐらいで大丈夫です。
A OR BはA | B
A XOR B は A ^ B
と表現します。
ビット全探索?
ビット全探索は、ざっくりいうと「全部の組み合わせを試してみる」方法です。
この問題で言う、「仕切りの有無」をビットを用いて
・その桁が0なら仕切りはない
・その桁が1なら仕切りがある
といった感じで表します。
具体的には、
1 2 3
0 0
1 2|3
0 1
1|2 3
1 0
1|2|3
1 1
といった感じです。
今挙げた例では仕切りは2つ、組み合わせは4つでした。
このように組み合わせの数は仕切りをM個としたとき、
2のM乗あります。
コード中にある1 << (n - 1)は1を左にn - 1回移動した2進数を表しているのですが、
1 << mは2のm乗に等しいです。
2の2乗 = 4
1 << 2
100(2進数) = 4 + 0 + 0 = 4(10進数)
ことり兄貴(・8・)の解答(Java)
import java.util.*;
class Main {
public static void main(String[] ktr) {
Scanner sc = new Scanner(System.in);
int n, a[], ans, i, j, xored, ored;
n = sc.nextInt();
a = new int[n];
ans = Integer.MAX_VALUE;
for (i = 0; i < n; i++) a[i] = sc.nextInt();
for (i = 0; i < 1 << (n - 1); i++) {
xored = 0;
ored = 0;
for (j = 0; j <= n; j++) {
if (j < n) ored |= a[j];
if (j == n || (i & 1 << j) > 0) {
xored ^= ored;
ored = 0;
}
}
ans = Math.min(ans, xored);
}
System.out.println(ans);
}
}
ことり兄貴(・8・)の解答(PyPy3)
n = int(input())
a = list(map(int, input().split()))
ans = 2**32
for i in range(1 << (n - 1)):
xored = 0
ored = 0
for j in range(n + 1):
if j < n:
ored |= a[j]
if j == n or i & 1 << j:
xored ^= ored
ored = 0
ans = min(ans, xored)
print(ans)
Pythonで提出するとTLEになってしまう様です。
この問題はPyPy3で提出しましょう。
4. おわりに
いやぁ、やらかしました。XとY逆...改めて問題をじっくり読むことの大切さを実感しました。
この記事を見てる方の参考にもなれば幸いです！！