やり直し

ARC046 B - 石取り大作戦

解法 N <= Aの時 絶対に先行が勝つ N > Aの時 A > Bの時 N > A > Bであるため先攻が1個だけとる戦法をとると絶対にN > Bにできる。N <= Aになったら全部取れば良い。よって先攻が勝つ。 A < Bの時 N > B > Aである。A > Bの時と同様に考えると、後攻が絶対勝…

ARC051 C - 掛け算

解法 愚直にシミュレーションするとB≦109なのでTLEしてしまう。 操作を十分な回数行うと、一番小さい数にAをかけると一番大きな数になる状態ができる。 この状態になれば周期性を利用してとくことができる。 この状態になった時の数列が{a'}で残りの操作回数…

KUPC2017 C - Best Password

解説 できるだけ一文字目の方に大きい文字(z,y,x,...,a)を作っていく。繰り上げしていくイメージ。 Ai C[S_i] + Ai+1 C[S_(i+1)] => Ai (C[S_i] + A) + Ai+1 * (C[S_(i+1)] - 1)。 N文字目から繰り上げできるだけしていく。 コード #include <algorithm> #include <cstdio> #inc</cstdio></algorithm>…

天下一プログラマーコンテスト2016予選A C - 山田山本問題

解説 a,...,zを頂点としてトポロジカルソート。 頂点数が少ないので、O(N3)のアルゴリズムでOK。 トポロジカルソートの参考サイト。 Topological sort コード #include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #</stack></sstream></set></queue></cmath></map></iostream></cstdio></algorithm>…

AGC001 B - Mysterious Light

やり直し B: Mysterious Light - AtCoder Grand Contest 001 | AtCoder 正三角形中の光の経路の長さを求める問題。 解法 f(a, b) := 辺の長さがaとbの平行四辺形の中を光が、2回反射するまでに進む距離とする。 2回反射する時点でまた平行四辺形ができる。 a …

AGC019 B - Reverse and Compare

やり直し B: Reverse and Compare - AtCoder Grand Contest 019 | AtCoder 問題概要 英小文字からなる文字列A(|A|≦200,000)が与えられる Aの英小文字2つを選んでそれを両端とする文字列を反転させることを1回まで行う 何通りの文字列ができるか 解法 A = abc…

ARC064 D - An Ordinary Game

やり直し D: An Ordinary Game - AtCoder Regular Contest 064 | AtCoder 解説 ゲームが終了する直前に文字列がどうなっているか考えると良い。(頭いいな〜) 両端が同じ時 abab...a ->直前は奇数個 よって与えられた文字列が奇数の時はSecondの勝ち(firstと…

ARC043 B - 難易度

やり直し B: 難易度 - AtCoder Regular Contest 043 | AtCoder 問題概要 難易度Diの問題がN個ある 以下の条件を満たす4問を選ぶ選び方は何通りか 2 問目の難易度は 1 問目の難易度の 2 倍以上である 3 問目の難易度は 2 問目の難易度の 2 倍以上である 4 問…

ARC009 C - 高橋君、24歳

やり直し C - 高橋君、24歳 問題概要 N人に手紙をそれぞれの人の宛名で出そうとしたが、K人は自分の宛名ではない手紙がきてしまった。手紙の渡し方は何通りあるか。1,777,777,777で割った余りを求めよ。 2≦N≦777,777,777,777,777,777 2≦K≦777,777 解法 Nがめ…

ABC034 D - 食塩水

やり直し D - 食塩水 解説 平均を最大化する問題->二分探索 wiグラムの濃度pi%の食塩水をk個混ぜた時の濃度は、 これがp以上となる時は を満たす。 変形すると、 濃度がp以上の食塩水を作れるかどうかは、 の値が大きい容器からK個選んで0以上となっていれば…

ARC046 C - 掛け算

やり直し C - 掛け算 解法 Bが109乗なので愚直にシミュレーションするとTLEになってしまう。aを昇順に並び替えつつ、何回かシミュレーションをすると a[0] * A >= a[N-1] となる時が来る。こうなったらN周期で同じ列が現れる状態になる。周期的になるまでは…

ARC038 B - マス目と駒

B - マス目と駒 やり直し 解法 メモ化再帰 trueが返ってきたら負けとして再帰で解く コード #include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include <stdlib.h> #include <stdio.h> #include </stdio.h></stdlib.h></vector></string></stack></sstream></set></queue></cmath></map></iostream></cstdio></algorithm>

ディスカバリーチャンネルコードコンテスト2016 C - ロト2

できなかったのでやり直し。 C: ロト2 - DISCO presents ディスカバリーチャンネル コードコンテスト2016 予選 | AtCoder x * y が kの倍数 <=> gcd(x, k) * gcd(y, k) が kの倍数という性質を用いる。 計算量はO(N2) -> O(Kの約数の個数2)になる。 今回Kの…