2018-09-30

C++でNimをつくった

C++で某石取りゲームNimを作りました. Nimのコンパイラを作ったわけではありません... CPUと対決するようなものを作りました.

付録のソースコードをコンパイルしてお楽しみください.
開発環境の都合で表示がバグったりするかもしれないですが勘弁.

使い方

起動します
なにも始まりませんが, 石列の数(数値)を入力します(面倒なので数値以外を入力することを想定していません...)(1~30ぐらいが安全です. )
ゲームが始まります(必ず先手でスタートします~~順番ぎめが面倒だったので~~)
最後の石をとると勝ちです. がんばりましょう. CPUは一瞬で石を取るのですぐに自分の番が来ます.

各石列が16個までなのは開発環境の都合です.
クラスとかメソッドとかいろいろ学べてよかったです. あまり活かせてませんが.
にしてもグラフィカルなUIはめんどいっすね〜めんどいめんどい.

	g++ -std=c++11 -o nim nim.cpp -lglut -lGLU -lGL

スパゲッティなソースコードは続きから

2018-09-30

ARC103 反省

CとDの部分点の1.5完. とれるところは全部とれたと思う. けど立ち回りがよくなかった.

C問題

問題

C - /\/\/\/

解法

偶数添字と奇数添字でグループ分けできる. それぞれで最も数が多い数字にするのが最善であるが, その数字が同じだったときの処理が面倒(最後のサンプルで気づいた).
具体的には, 数字の数が最も多い数字を記録しておき, プリオリティーキューに偶数番目と奇数番目の数字の数を別々のものにいれておき, 数字が一致してしまったときに, どっちかのキューの2番めに大きいものと交換して差が小さくなる方を選ぶと最善.

提出

Submission #3293532 - AtCoder Regular Contest 103

感想

コンテスト中はコーナーケースあるのでは？とか考えてちょっと提出をためらってしまいました. 実装も面倒で面倒な問題です.

D問題

部分点のみで, 後で満点は解き直します.

問題

D - Robot Arms

解法

部分点解法のみ.
まず, がんばって問題文を読解します.
各 $X_j,Y_j$ について, $(X_j+Y_j) \space mod \space 2$ を考えます. この値が異なるものが存在したとき, どうやっても答えを構築することはできません.
なぜならば, $d_j$ をどのように設定してどのように足しあわせても, 各 $d_j$ の和の偶奇は不変で, 偶数グループまたは奇数グループについて, 移動しえない場所が存在してしまいます.
上の条件を満たしていると考えると, すべての $d_j$ について, $d_j = 1$ としたとき, 部分点の制約ならば十分小さい $m$ で構築が可能であることがわかります.
具体的には,
$(X_j+Y_j) \space mod \space 2 = 0$ のとき, $m = 20$ として目的の場所まで真っ先に移動し, 反復横飛びでもして残りの移動を費やします.
$(X_j+Y_j )\space mod \space 2 = 1$ のとき, $m = 19$ として目的の場所まで真っ先に移動し, 反復横飛びでもして残りの移動を費やします.
これを実装して300点です.
600点はまた今度...

提出

Submission #3301657 - AtCoder Regular Contest 103

感想

和の偶奇とかいうの, 結構当てずっぽだったんですけどヒットしたみたいでよかったです.

総評

Cを遅解きしたあと順位表を見てみると, 誰もDをやっていなかったのでEを見たんですが, 結局は解法は生えずに結構な時間を費やしてしまったので, 結果論ではありますがDをもっと速く考えていればレートは伸びたかなーと思います.
コンテスト中は自分の身の丈にあった問題を考察していきたい.
rating 1089->1134

2018-09-25

ABC 110 反省

ABDの3完.

A問題

問題

A - Maximize the Formula

解法

条件から, どれか一個だけ10倍して足すことができるのと同値になる. よって, $max\{10A+B+C, A+10B+C, A+B+10C \}$ が答え.

提出

Submission #3249860 - AtCoder Beginner Contest 110

感想

Aにしてはちょっとむずかしい.

B問題

問題

B - 1 Dimensional World's Tale

解法

$max\{x\} \leq min\{y\} \land X \leq Y$ ならば'No War' ,そうでなければ'War'です. 本番ではmin\{y\}とmax\{x\}だけ調べて $max\{x\} \leq min\{y\}$ かどうかを見て, $X < Z \leq Y$ を満たす $Z$ が存在するかどうかはそこにさらにループを回して調べました.
今考えると, 無意味ですし実装が面倒になるだけだと思います. 実際, 実装のミスで1WAしています. (リジャッジ後もWAのままでした...)

提出

Submission #3253067 - AtCoder Beginner Contest 110

感想

これもなんか問題文が読みにくく, Bにしてはちょっと面倒です.

C問題

問題

C - String Transformation

解法

コンテスト中に解けず. 考えていたのは, あるアルファベットからアルファベットへの対応を調べ, 2つ以上に対応するものがあればNo, そうでなければYes, というロジックだったのですが, 実装も考察もまずくWAを連発.
WA解答では無向グラフのように対応を双方向に一気に定めていたため, ハッシュマップがめちゃくちゃになってしまっていたようです.
書き直した解答では, 対応する文字が2つ以上あったときにNoを出力するのは同じですが, あとで対応先の文字がただ1つのアルファベットのみに対応していることを確認するようにしています.
前者がアルファベットからアルファベットへの単射であるかの確認, 後者がその対応がアルファベットへの全射であることの確認となっています.

提出

Submission #3270441 - AtCoder Beginner Contest 110

感想

えーこれ難しくないですか><.

D問題

問題

D - Factorization

解法

『素因数をいくつかの箱に入れて分割する』というのは, ARC-004D
D - 表現の自由 ( Freedom of expression )で見ていた(解いていませんでしたが)ので, 分割数やらで掛け合わせるのかなとコンテスト中は, ベル数やらスターリング数やらを調べていましたが, 結局素因数を $N$ 個の箱に分配するときの重複組み合わせでDPができることに気づき, それを実装しました.
今考えると, ARC-004Dの解答を見れば早かったですね...
DPは,
$dp[i] = i番目の素因数までを使ってN個の箱に素因数を分配する場合の数$
とすると,
$dp[0] = 1$
$dp[i+1] = _{N}H_{p_{i+1}}dp[i] \space( p_i はi番目の素因数の個数. 2*3*5^2 ならば p_1 = 1, p_3 = 2)$
となります.
前後のみを見ているdpなので0次元DPに落とせます.
制約の中では, 素因数の数はたいして大きくならず, コンビネーションの前処理は定数なので, この問題の計算量は $M$ の素因数分解がネックとなり, $O(\sqrt M)$ となります.
実は本番のコードは $O(M)$ の素因数分解をしてしまっています...
しかし, 通ってしまいました.

提出

(コンテスト時提出したもの)
Submission #3257928 - AtCoder Beginner Contest 110
( $O(\sqrt M)$ に改善したもの)
Submission #3270638 - AtCoder Beginner Contest 110
実に800倍の速度の差が出ています.

感想

ささっと思いつけてよかった.

総評

B問題に不備があり, 結果unratedとなりましたが, 初めて推定パフォ1600上限を出せたのでよかったです.

2018-09-18

ABC 041-D 徒競走

問題

D - 徒競走

解法

$N \leq 8$ のときの部分点はnext_permutationを使うと獲得できます.
満点解法では $16! = 2.0 * 10^{13}$ 通りを考える必要があるので, 別の解法を考える必要があります.
$2^{16} = 65536$ と, うさぎの集合を見るようにすると数が小さいです.
これに着目して, bitDPを行うことを考えます.
$dp[S][n] = 集合Sにおいてn番目のうさぎが最後尾であるときの並べ方$
とすると,

基底

$dp[\{n\}][n] = 1$

遷移

$dp[S][n] = 0 \space (\exists_k ( (n < k) \land k \in S)$ )
$dp[S][n] = \sum_{(k \in (S-\{n\})) } dp[S-\{n\}][k] \space (otherwise)$
とかけます. 遷移においての $(n < k)$ というのは, 与えられた $\{x\} , \{y\}$ について, 最後尾が $n$ であるが, $k \in S$ より $n$ の方が速いといったときには矛盾を孕むことになるので, そのような場合の数は存在せず $0$ となる, ということです.

提出

Submission #3221481 - AtCoder Beginner Contest 041

感想

$M$ についての制約をよく見ておらずに領域を十分にとっておらず, ACときどきWA状態でｵﾝｵﾝしてました. 領域足りてなかったらREでてほしいです...(我儘).

2018-09-13

ABC 097 C - K-th Substring

問題

Submission #3184163 - AtCoder Beginner Contest 097

解法

連続している部分文字列の中で辞書順 $K$ 番目のものを求める問題です.
制約 $1 \leq K \leq 5$ と, 『連続している部分文字列』というのがポイントで, 連続している $i$ 文字( $i \in [1,2,3,4,5]$ )をすべて列挙し,ソートして重複を取り除いた $K$ 番目の要素を見ると答えです.
今回はvectorに突っ込んでsortし, v.erase(unique(v.begin(),v.end()),v.end())で重複を取り除く実装をしましたが, setにinsertしてsets.begin()+K-1番目の要素を取得するでもいい気がします.

提出

Submission #3184163 - AtCoder Beginner Contest 097

感想

実質全列挙のような形となりました. $K$ が大きかったらどう解くんでしょう...

2018-09-13

ABC 098 D - Xor Sum 2

最近しゃくとり方を実装していなかったので解き直しました.

問題

D - Xor Sum 2

解法

問題を見るに, いかにもなしゃくとり法です.
この問題を解くうえで, xor演算の重要な性質を用います.
xor演算において以下の性質が成り立ちます.

$A \space xor \space A = 0$
$A \space xor \space B = B \space xor \space A$
$(A \space xor \space B) \space xor \space C = A \space xor \space (B \space xor \space C)$

1の性質は, この演算においては自身が逆元となることを示しています. (自明に0が単位元となっています.)
2の性質は, 可換な演算であることを示しています.
3の性質は, 結合法則が成り立つことを示しています.
これを利用すると, しゃくとり法を実装することができます.
具体的には, 以下のアルゴリズムを適用することができます.
入力の配列を $A$ , サイズを $N$ とします.

初期化 : $l:=0 , r:=0 , res := 0, now = 0$
$r > N$ ならば $res$ を出力して終了する.
$(A[r] + now) == (A[r] \space xor \space now)$ ならば4へ, そうでなければ5へ
$now := now \space xor \space A[r]$ , $r := r + 1$ , $res := res + r - l$ , 2へ
$now := now \space xor \space A[l]$ , $l := l + 1$ , 2へ

しゃくとりの右端を右に進めるときに答えを加算するようにしています.
計算量は $O(n)$ で済みます.

提出

Submission #3184217 - AtCoder Beginner Contest 098

感想

しゃくとり法は本番でバグらせやすいので演習を積んでいきたいです.

2018-09-08

ABC 109 反省

久々にコンテスト中に全完できました. しかし, B問題でWAを連発してしまったため, 大きくペナルティを食らってしまったのは反省事項です.

A問題

問題

A - ABC333

解法

$C$ を1~3まで試します.

提出

Submission #3151567 - AtCoder Beginner Contest 109

感想

素直に実装しましたが, $A* B$ が奇数だったら"Yes", そうでなければ"No"です.

B問題

問題

B - Shiritori

解法

次の文字の先頭と今みている文字の尻が一致しているかをみるついでに, mapを用いて初出の文字かチェックをしていたのですが, 最後の文字が初出であるかどうかということを確認しておらず, それに気づかずに論理式に（）をつけたり的はずれな修正をして3WA. それを修正したつもりで出すも, 分岐先でreturnしておらず1WA. 計4WAをかましました.

提出

Submission #3153980 - AtCoder Beginner Contest 109

感想

yukicoder解いてるときにWAが出るとすぐテストケースをのぞいてしまう癖があるので, こういう不測のWAに弱いとこがありました. 反省します.

C問題

問題

C - Skip

解法

すべての $x_i$ に対して $X$ の差分を取り, これら $|X-x_i|$ すべての最大公約数が答えとなります.
各 $x_i , x_{i+1}$ の間の距離が $D$ の倍数であり, さらに $X$ から距離 $D$ でステップしてどれかの $x_i$ に到達することができれば, $D$ で数列間を移動することができます. その中での最大の $D$ は, 各 $i$ に対して $|X-x_i|$ すべての最大公約数となります.

提出

Submission #3155097 - AtCoder Beginner Contest 109

感想

解法はなんとなく思いついたのですが, 説明がなんとなく難しいです.

D問題

問題

D - Make Them Even

解法

発想が必要になる問題です.
まず, $H,W$ の制約から, $O(HW)$ の解法が求められます.
これがちょっとしたヒントで, 何度もバックトラックして計算するようなことはなさそうであることがわかります.
操作について考察します.
できるだけ偶数マスを増やしたいときは, 奇数マスのコインをどこかに動かせばよいのですが, ここで動かす方向を下方向に固定してみます.
まず1行目を左から右に見て奇数マスのコインを下に動かし,
次に2行目を...として,最後から2番目の行まで繰り返します.
すると, 最後の1行以外のマスをすべて偶数マスにすることができます.
最後の1行については, 奇数マスのコインを順次右側に動かしていくと, 一番右下のマス以外すべて偶数のマスにすることができます.
コインの総数が奇数だった場合, どうしても奇数のマスは1つできます.
コインの総数が偶数だった場合, すべて偶数のマスにできます. このとき, 右下のマスが奇数で他のマスが偶数ということはありえないので, これが最適解であることがわかります.
あとはpairとvectorなどで移動元と移動先を管理し, 丁寧に実装しましょう.
0-indexedで出力してしまい1-WA.

提出

Submission #3157253 - AtCoder Beginner Contest 109

感想

0-indexedで出力してしまったのはちょっとした悔いですが, 解けてよかったです.

総括

最近難しいABCが続いてましたが, 今回は易しかったように思います. ただ, こういうときにWA量産して順位落としちゃうのはよくないですね.