問題文をじっっっっっくり読みます.
$Cx$ , $Cy$ が小さく, これら2つを全探索できそうであることがわかります. これらを決めると, ある $x_i, y_i$ について $H$ が1つ決まります. これに対し, すべての $(x_i,y_i,h_i)$ を調べ, この $H$ が条件を満たしているか調べます.
しかし, これだけでは不十分で, ある $h_i$ が0のとき, 状態が2つ考えられます. この状態に関しては $H$ が確定した後で考える必要があるため, 後回しにして考える必要があります. 制約から, ある0でない $h_i$ が存在しているので, 後で考えてもよいことがわかります.
これを実装するとやっとACできます(9WAしました).

提出

Submission #3352560 - AtCoder Beginner Contest 112

感想

顔を真っ赤にしながら実装していました.

D問題

問題

D - Partition

解法

答えは, $M$ の約数であることが必要っぽい(?)ことをエスパーしたので, 約数を全列挙し, その約数を何個作れるか？を考えると, すべての約数について, $max\{q | qはMを割り切り, M/q \geq N \}$ が答えになります.

提出

Submission #3353977 - AtCoder Beginner Contest 112

感想

CをやっとACしたあとで, ろくに証明もせずになんとなく出したのですが, ACできてよかったです.

総評

次のAGCこそ水色になりたい

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$ とします.