与えられた整数Nを2つの整数(A+B)に分割する。この時、AとBのどの桁にも4が含まれ無いように分割するという問題。Nの各桁を順次見ていき、4の場合は2と2、それ以外は0と元の数、のようにAとBに割り振る。答えを出力する際に、先頭の0は削除する必要がある点に注意する。USD.codingcompetitions.withgoogle.com解法NxNのマス目を北西から南東に移動する。移動は南(S)、東(E)の組み合わせのみで後戻りは無し。テストケースで与えられた移動方法に対して、経路が重ならないような移動方法を1通り出力するという問題。これは、与えられた移動方法(SとEの並び)に対して対象な移動方法(SならE、EならS)を作れば良いです。SEEESSESならESSSEESE。このようにすると、移動経路はマス目の北西から南東への対角線に対して対象な移動経路になるので、絶対に重なりません。USD.codingcompetitions.withgoogle.com解法テストケースとして与えられる整数列は、元の文字列が対応する素数の積になっています。テストケースの整数列をEi、元の文字列の対応する素数をPiとすると、E0はP0xP1、E1はP1xP2です。よって、E0とE1の最大公約数をとればP1が求まり、それでE0とE1を割ることでP0とP2も求めることが出来ます。ここで注意点ですが、E0とE1が等しい場合、つまり、P0〜P2が同じ素数(=文字)の場合はこの方法では求めることが出来ません。(これに気づかずに最初WAをくらいました。)よって、整数列を前から見ていき、隣り合う整数が最初に異なる場所に上記の方法を適用し、そこから前方、後方を見ていくことで全ての素数を求めることが出来ます。素数が全て求まったらソートして小さい方からアルファベットを割り当てていき、元の文字列に戻すことが出来ます。USD.codingcompetitions.withgoogle.com解法N台のコンピュータのうちB台が壊れている。N個のビット列を与えたとき、壊れたコンピュータのビットは返ってこない。F回までビット列を投げることが出来る場合に、何台目のコンピュータが壊れているかを特定する方法を考えるという問題。TestSet1のF=10の場合は結構簡単。いうのも、Nの最大値が1024(=2^10)なので、0〜1023までの数字を各コンピュータに割り当てて、1回目の問い合わせは1ビット目、2回目の問い合わせは2ビット目、・・・というように10ビット目まで投げてやる。その結果、返ってきた回答を繋げて10進数に戻してやった場合に、欠けている数字が壊れているコンピュータの位置になります。TestSet2のF=5の場合は少し工夫が必要です。2^5=32なので、5回の問い合わせで作れるビット列は0〜31になります。N=1024の場合、0台目から順にサイクリックに0〜31を割り当てます。すると、0〜31、0〜31、・・・、0〜31が32回繰り返されることになります。問題の制約として、壊れているコンピュータは最大15台までなので、抜けている数字の位置によってどのコンピュータが壊れているか一意に特定することが出来ます。厳密にはBが最大31までであれば大丈夫だと思います。32以上になると、例えば連続する0〜31が抜けていた場合に何番目の0〜31が抜けているのかが特定できない、ということになります。入力に対応する塩基を出力するだけ。実装とりあえずcaseで実装。文字を一文字ずつ読み込み、ATGCのいずれかであれば部分文字列の長さを1増やし、それ以外であれば部分文字列の長さを0にもどす。各部分文字列の最大値を記憶・更新しておいて、最後に出力すれば良い。累積和の変形問題という感じ。最初に1文字目からn文字目までの’AC’の出現回数の数列を用意しておく(Cnとする)そして、各l、rについては、C[r]-C[l]を計算すれば定数時間で計算可能。online.atcoder.jp解法DPで解ける。文字列の長さがnでの直前の3文字毎の文字列の数とすると、nが3の場合が初期値となり、以下の通りとなる。14文字目以降については、直前の4文字に着目して条件に一致する場合だけ数え上げて行けば良い。手に入れた宝石の価値の合計から支払ったコストの合計を引いた値が最大になるような宝石の選び方を考えれば良い。宝石はいくつ選んでも良いので、各宝石の「価値−コスト」が正になるものは全て選んで良いことになる。よって、「価値−コスト」が正になるものを加算していけばよい。online.atcoder.jp解法N個の整数のうち1つだけ好きな整数に書き換えた後の最大公約数をなるべく大きくするためには、1つの整数を他の整数のうち一つと同じにすればよい。これは、その整数を取り除くのと同じ意味になる。N個のうち1つを取り除いた残りのN-1個の最大公約数の最大値を求めれば良い。2つの数の最大公約数はlogAで求まるので、N-1個の最大公約数はO(NlogA)となり、これをN通り試すと間に合わない。そこで以下のような工夫をする。Aiを取り除いた場合の最大公約数は、A1〜Ai-1の最大公約数とAi+1〜ANの最大公約数になる。よって、あらかじめA1〜A2、A1〜A3・・・のように左から順番に整数を追加した最大公約数とAN-1〜AN、AN-2〜AN・・・のように右から順番に整数を追加した最大公約数を求めておくことで、i番目を取り除いた場合の最大公約数をlogAで求めることが出来る。すれば、全体の計算量はO(NlogA)で収まるので間に合う。整数列のうち、隣り合う任意の2枚の正負を反転させることが何回でも出来る。操作後の整数列の総和の最大はいくつになるか、という問題。これは、以下のルールに気づけばすぐに解ける。AiとAj(i<j)の正負を反転させたい場合、「iとi+1」、「i+1とi+2」、「i+2とi+3」・・・・「j-1とj」のように隣り合う2つを順次反転させていけば良い。数個であれば好きなように正負を反転させることが可能(奇数は不可)よって、整数列の初期状態において、負が偶数個であれば全て正にすることが出来る。絶対値の総和をとれば良い。負が奇数個の場合、(初期状態が正のものも含めて)絶対値が最も小さいものを最終的に負としてそれ以外を正にすれば良い。online.atcoder.jp解法2個のボタンのサイズが等しい時は、A+Bが解。