ABC345参加記録
Published on 2024-03-29Last Modified 2024-03-29
Table Of Contents
はじめに
珍しくいくつかやることがあったのと、数日体調を崩していたため参加記録をサボっていました。 2週間遅刻ですが書きます。
戦績
- 順位 : 1593th
- パフォーマンス : 1342
- レーティング変動 : 1373 → 1370 (-3)
問題
A - Leftrightarrow
先頭と末尾がそれぞれ<, >で、残りの中央の文字が=のみであればYesです。
import std;
void main () {
string S = readln.chomp;
bool ok = true;
if (!(S[0] == '<' && S[$-1] == '>')) ok = false;
S = S[1..$-1];
foreach (c; S) if (c != '=') ok = false;
if (ok) {
writeln("Yes");
}
else {
writeln("No");
}
}
void read (T...) (string S, ref T args) {
import std.conv : to;
import std.array : split;
auto buf = S.split;
foreach (i, ref arg; args) {
arg = buf[i].to!(typeof(arg));
}
}
B - Integer Division Returns
切り上げを出力する問題です。 $X$が正のときは典型テクで、$\lceil \frac{X}{10} \rceil = \lfloor \frac{X + 9}{10} \rfloor$が成立します。 $X$が負のときは単に切り捨てすればよいです。
import std;
void main () {
long X = readln.chomp.to!long;
if (0 <= X) writeln((X + 10 - 1) / 10);
else writeln(X / 10);
}
void read (T...) (string S, ref T args) {
import std.conv : to;
import std.array : split;
auto buf = S.split;
foreach (i, ref arg; args) {
arg = buf[i].to!(typeof(arg));
}
}
負のときの処理を今まで考えたことがなかったです。
C - One Time Swap
ちょうど1回だけスワップしてできる文字列の種類数を数えます。 スワップして別の文字列になるとしましょう。 このとき、選択する2文字は異なっている必要があります。
また、上記のようなスワップによってできた文字列はすべて相異なります。 理由はシンプルで、例えば$(i, j)$を選択してスワップした文字列を$S$、$(k, l)$を選択してスワップした文字列を$T$とします。 ただし、$i \neq k$または$j \neq l$の少なくとも一方が成立するとします。
このとき、仮定より$S _ i \neq T _ i$または$S _ j \neq T _ j$の少なくとも一方が成立するからです。 これらのうち少なくとも一箇所において、片方は変わっているけどもう片方は変わっていないっていうことですね。
スワップしてもとと同じになる場合を考えます。これができる必要十分条件は、$S$がある文字を$2$以上含むことです。
これらを数え上げればOKです。 前者は「自分より後ろとしかペアを作らない」という制約条件で楽に数えられます。 後者はそのままです。
import std;
void main () {
string S = readln.chomp;
int[char] mp;
long ans = 0;
foreach_reverse (c; S) {
foreach (key, val; mp) if (key != c) ans += val;
mp[c]++;
}
foreach (key, val; mp) if (2 <= val) {
ans++;
break;
}
writeln(ans);
}
void read (T...) (string S, ref T args) {
import std.conv : to;
import std.array : split;
auto buf = S.split;
foreach (i, ref arg; args) {
arg = buf[i].to!(typeof(arg));
}
}
D - Tiling
本番解けませんでしたが、解説ACしたので載せておきます。
長方形タイルでマスを埋められるかを判定します。 いかにも全探索という見た目をしています。 実際、目標マスがかなり大きいこと、タイルのサイズが自由であることからbitで状態を持つのは無理そうです。
しかし、この問題はよくあるdfsで置いていくやつは厳しそうです。 これは単純に長方形タイルが(目標マスのサイズに対して)多いからです。 もっといい感じの全探索を構築してあげないといけません。
ここで、置くタイルが長方形であることを利用して高速化できます。 左上から右下に次のように番号をつけて見ていくことにします。
1 2 3 ... N N+1 N+2 N+3 ... 2N ...
さて、任意の完成状態のタイルを考えて、上の順番に長方形を見ていきます。 すると、まだ未発見だったある長方形に出会うとき、必ず左上の角のマスに出会うことがわかります。 これはどのような配置でも例外なく共通しています。
このことから、任意の完成状態まで持っていける置き方は、タイルの使用順の順列と対応付けることができます。
これより、わざわざdfsをして置いていく必要がなく、タイルの使用順の順列を列挙する問題になります。 それぞれのタイルの使用順に対しては、上の順番でマスを見ていき、最初に出会った空きマスに左上の角を合わせて設置を試みれば良いです。
import std;
void main () {
int N, H, W; readln.read(N, H, W);
auto tiles = new Tuple!(int, int)[](N);
foreach (i; 0..N) {
int A, B; readln.read(A, B);
tiles[i] = tuple(A, B);
}
solve(N, H, W, tiles);
}
void solve (int N, int H, int W, Tuple!(int, int)[] tiles) {
auto ord = iota(N).array;
auto used = new bool[][](H, W);
do {
bool ok = false;
void rec (int cur, int y, int x) {
if (ok) return;
while (y < H) {
// 空いてる？
if (!used[y][x]) {
if (N <= cur) return;
{ // 縦
bool next = true;
if (y + tiles[ord[cur]][0] <= H && x + tiles[ord[cur]][1] <= W) {
foreach (i; 0..tiles[ord[cur]][0]) {
foreach (j; 0..tiles[ord[cur]][1]) {
if (used[y + i][x + j]) next = false;
}
}
if (next) {
foreach (i; 0..tiles[ord[cur]][0]) foreach (j; 0..tiles[ord[cur]][1]) used[y + i][x + j] = true;
rec(cur + 1, y, x);
foreach (i; 0..tiles[ord[cur]][0]) foreach (j; 0..tiles[ord[cur]][1]) used[y + i][x + j] = false;
}
}
}
{ // 横
bool next = true;
if (y + tiles[ord[cur]][1] <= H && x + tiles[ord[cur]][0] <= W) {
foreach (i; 0..tiles[ord[cur]][1]) {
foreach (j; 0..tiles[ord[cur]][0]) {
if (used[y + i][x + j]) next = false;
}
}
if (next) {
foreach (i; 0..tiles[ord[cur]][0]) foreach (j; 0..tiles[ord[cur]][1]) used[y + j][x + i] = true;
rec(cur + 1, y, x);
foreach (i; 0..tiles[ord[cur]][0]) foreach (j; 0..tiles[ord[cur]][1]) used[y + j][x + i] = false;
}
}
}
return;
}
// 進める
x++;
if (x == W) {
y++;
x = 0;
}
}
ok = true;
}
rec(0, 0, 0);
if (ok) {
writeln("Yes");
return;
}
} while (next_permutation(ord));
writeln("No");
}
void read (T...) (string S, ref T args) {
import std.conv : to;
import std.array : split;
auto buf = S.split;
foreach (i, ref arg; args) {
arg = buf[i].to!(typeof(arg));
}
}
bool next_permutation (alias less = "a<b", T) (T array)
if (is (T == E[], E) || is (T == E[n], E, size_t n))
{
import std.algorithm : swap, reverse;
import std.functional : binaryFun;
alias is_a_less_than_b = binaryFun!(less);
int i = -1, j;
foreach_reverse (idx; 1..array.length) {
if (is_a_less_than_b(array[idx-1], array[idx])) {
i = cast(int) (idx-1);
break;
}
}
// Next permutation doesn't exists.
if (i == -1) return false;
foreach_reverse (idx; i+1..array.length) {
if (is_a_less_than_b(array[i], array[idx])) {
j = cast(int) idx;
break;
}
}
swap(array[i], array[j]);
array[i+1..$].reverse;
return true;
}
bool prev_permutation (alias less = "a<b", T) (T array)
if (is (T == E[], E) || is (T == E[n], E, size_t n))
{
import std.algorithm : swap, reverse;
import std.functional : binaryFun;
alias is_a_less_than_b = binaryFun!(less);
int i = -1, j;
foreach_reverse (idx; 0..array.length-1) {
if (is_a_less_than_b(array[idx+1], array[idx])) {
i = cast(int) idx;
break;
}
}
// Previous permutation doesn't exists.
if (i == -1) return false;
foreach_reverse (idx; i+1..array.length) {
if (is_a_less_than_b(array[idx], array[i])) {
j = cast(int)idx;
break;
}
}
swap(array[i], array[j]);
array[i+1..$].reverse;
return true;
}
計算量は$O(N! 2^N HW)$くらいです。多分。
終わりに
未だに全探索を落としてしまうとは…と落ち込みましたが、振り返ってみてこれは無理だなと思いました。 正直、すべて長方形であることを利用して、順列と置き方を対応付けるというのはとんでもなくad-hocに思えます。 解けた人がどこをとっかかりにしたのかがいまいちわからないので、どうしようもないです。
E問題も見ましたが、だいぶ間に合わないdpを思いついただけなので、ここには載せないことにします。 Dが解けなかったことにより、この回は実質開始7分で解答終了したみたいです。