naoya_t@hatenablog

いわゆるチラシノウラであります

〈ARC埋め〉D問題集中アタック(残りの500点・600点のやつ:ARC 069,067,066,064,060 D)

途中まで書いたやつがネットのエラーで消えた…
家のネット最近不安定だ(DNSにアクセスできず名前解決できなくて気づく)

気を取り直して
ARC D問題の残ってるやつ(500点・600点のやつ)を粛々と埋めていく。

ARC 069 D - Menagerie (500)

もしかして2-SAT?と思ったけど
最初の2つの動物を決め打ちにしてoxで3つ目の動物を順に決めていって一周回って辻褄があえばそれを表示、でいいんじゃないかな(高々2x2=4通り、でO(N))
S/W, o/x を±1で表せば掛け算でいい感じにひっくり返せることに気づいた
→AC 33'38
https://beta.atcoder.jp/contests/arc069/submissions/2703509
自力で取れた

解説解も同様

ARC 067 D - Walk and Teleport (500)

  • 隣りの町まで歩く(A*dx) か飛ぶ (B) かの疲れない方で西から東へ進むだけでは(だとしたら500点問題としては簡単すぎやしないか)
  • 順番を変えたほうが良いケースとかある?飛ぶ場合の疲労度は距離に関係ないから、歩く区間の始めに飛ぼうが終わりに飛ぼうが同じだよね

→AC 7'09
https://beta.atcoder.jp/contests/arc067/submissions/2703525

解説解も同様(これは300点相当では)

ARC 066 D - Xor Sum (600)

(ABC埋めで最後に残ったD問題でもある)
考察

  • 任意のuについて、a xor b = uとなるaとbは必ず存在する。
    • uの中で立っているビットをa0とb0に分配すると a0 xor b0 = a0+b0 = u
    • uの中で立っていないビットだけで構成されるcをa0,b0それぞれに足した(or)もののxorはuになる
  • v = a+b = (a0|c) + (b0|c) = (a0+c)+(b0+c) = (a0+b0)+2c = u+2c
    • あるuに対し許されるvとは、uで使われていないビットのみから成る数cについて u+2c で表すことのできる数(で0以上N以下のもの)。
時間切れにつき解説を

読んだけどわからん><

を読んだ。なるほど、可能なu,vをプロットしたらSierpinski gasket

*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.
.*...*...*...*...*...*...*...*...*...*...*...*...*...*...*...*..
..*.*.....*.*.....*.*.....*.*.....*.*.....*.*.....*.*.....*.*...
...*.......*.......*.......*.......*.......*.......*.......*....
....*.*.*.*.........*.*.*.*.........*.*.*.*.........*.*.*.*.....
.....*...*...........*...*...........*...*...........*...*......
......*.*.............*.*.............*.*.............*.*.......
.......*...............*...............*...............*........
........*.*.*.*.*.*.*.*.................*.*.*.*.*.*.*.*.........
.........*...*...*...*...................*...*...*...*..........
..........*.*.....*.*.....................*.*.....*.*...........
...........*.......*.......................*.......*............
............*.*.*.*.........................*.*.*.*.............
.............*...*...........................*...*..............
..............*.*.............................*.*...............
...............*...............................*................
................*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.................
.................*...*...*...*...*...*...*...*..................
..................*.*.....*.*.....*.*.....*.*...................
...................*.......*.......*.......*....................
....................*.*.*.*.........*.*.*.*.....................
.....................*...*...........*...*......................
......................*.*.............*.*.......................
.......................*...............*........................
........................*.*.*.*.*.*.*.*.........................
.........................*...*...*...*..........................
..........................*.*.....*.*...........................
...........................*.......*............................
............................*.*.*.*.............................
.............................*...*..............................
..............................*.*...............................
...............................*................................
................................*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.
.................................*...*...*...*...*...*...*...*..
..................................*.*.....*.*.....*.*.....*.*...
...................................*.......*.......*.......*....
....................................*.*.*.*.........*.*.*.*.....
.....................................*...*...........*...*......
......................................*.*.............*.*.......
.......................................*...............*........
........................................*.*.*.*.*.*.*.*.........
.........................................*...*...*...*..........
..........................................*.*.....*.*...........
...........................................*.......*............
............................................*.*.*.*.............
.............................................*...*..............
..............................................*.*...............
...............................................*................
................................................*.*.*.*.*.*.*.*.
.................................................*...*...*...*..
..................................................*.*.....*.*...
...................................................*.......*....
....................................................*.*.*.*.....
.....................................................*...*......
......................................................*.*.......
.......................................................*........
........................................................*.*.*.*.
.........................................................*...*..
..........................................................*.*...
...........................................................*....
............................................................*.*.
.............................................................*..
..............................................................*.
...............................................................*

(出力コードはこちら

  • 左上のNxNマスの*の数を数えるような関数を書けばOK
  • 三角形の塗り面積がサイズが2倍になると3倍になることを利用して、2^kの大きなものから引いていって足りない部分はみ出した部分を加減していく。メモ化再帰

→AC
https://beta.atcoder.jp/contests/abc050/submissions/2713041

ARC 064 D - An Ordinary Game (500)

同じ文字が接することにないように取っていくゲーム。両端は取れない。
いろいろ考えてみたものの

  • 手順によって取れたり取れなかったりするのか?(相手に不利になるように振る舞えるのか)
  • あるいは、誰がどういう順で取っても何手取れるかは不変で、それのmod 2で決まるとか
時間切れにつき解説読む

結論から述べると,「s の長さが偶数である」と「s の先頭文字と末尾文字が同一である」の排他的論理和が真ならば後手が勝ち,偽ならば先手が勝ちます.

は?
先頭と末尾が同じ場合と違う場合で何かが違うのは分かる(違う場合はつるつる外していける)。

  • 同じ場合:最後に間に1つ残る
  • 違う場合:最後に間に2つ残るか何も残らないか

とすると、

  • 同じ場合:最後が奇数。最初が偶数ならFirst、奇数ならSecond
  • 違う場合:最後が偶数。最初が偶数ならSecond、奇数ならFirst

「最終的なsの長さは一意には定まりませんが、その偶奇は一意に定まります。」そういうことか。(本当なのか?)

異なる3文字(abc)が連続→1文字削れる
abcabc → ababc → abac → abc → ac
abcabc → acabc → acbc → abc → ac
abcabc → acabc → acac
どう取っていっても2種類の文字が交互に並んだ状態に落ちる、ってことでいいのか

#include <bits/stdc++.h>
using namespace std;

bool solve(string& s) {
    int N = s.size();

    int even = (N % 2 == 0);
    int same = (s[0] == s[N-1]);
    // same -> odd; even -> odd : First (true)
    // !same -> even; even -> even : Second (false)

    return even == same;
}

int main() {
    string s; cin >> s;
    cout << (solve(s) ? "First":"Second") << endl;
    return 0;
}

https://beta.atcoder.jp/contests/arc064/submissions/2703571

ARC 060 D - 桁和 / Digit Sum (500)

1. 二分探索で行ける?→行けない。単調増加・単調減少ではない
2. 桁数に着目して、1桁、2桁…最大でも\log_2 n桁あたりなはずだから決め打ちしてみる。3桁以上の場合は総当たりでも√nだから間に合う。2桁の場合はqb+r=n,q+r=sからq(b-1)=n-sなので、n-sの約数を全部試してもO(√n)。1桁の場合は…n

時間切れにつき解説読む

方針はそんなに間違ってなかった(多分バグってる)けど解説解のほうがシンプル:

  • n=sなら(1桁)n+1
  • 3桁以上:2≦b≦√nだからb総当たりでOKだった(←ここがシンプル)
  • 2桁:qb+r=n, q+r=s のqは高々√nだからq総当たりでOK

→WA(1)
r=s-qであるべきところをr=sと書いてて落ちてた
→AC
https://beta.atcoder.jp/contests/arc060/submissions/2703634