長さNの数列の切れ目はN-1通りあるため、3つの切れ目を選ぶ組み合わせはn-1C3通りあります。Nは最大2×105であるため、全ての組み合わせを試すのは現実的ではありません。「P、Q、R、Sの最大値と最小値の差の絶対値が最小になる」は言い換えると、「P、Q、R、Sの大きさが出来るだけ近い場合」ということです。最適なのは、数列の総和の1/4になる場合ですが、実際にはなるべく1/4に近い値を目指すことになります。ここで数列の三つの切れ目をi1、i2、i3とおきます。i2を固定した場合を考えます。この時、PとQ、RとSの差が最小になる切れ目がi1とi3であったとします。次に、i2を右に一つずらす場合を考えます。この時、i1とi3は「そのまま」か「右にずれる」ことになります。(つまり単調増加)そして、PとQ、RとSの差が最小になる新しいi1とi3に更新していきます。このような処理をi1=0、i2=1、i2=3を初期状態として繰り返しながら、「P、Q、R、Sの最大値と最小値の差の絶対値が最小」になる値を求めることで解けます。配列の部分和については、累積和を事前に求めておくことで定数時間で計算できますので、全体としてはO(N)で解くことが出来ます。以下の数式の値を最小にするbをどのようにして求めるかという問題です。abs(B_N-b)$$と書き換えることがが出来ます。これが最小になるのは、数列Bの中央値をbとした場合です。図にしてみるとよく分かります。(見やすくするためにBはソート済みとしています)Nが奇数の場合、bがB3より大きく(小さく)なるとその分合計値が増加します。Nが偶数の場合、B2〜B3の間から外れると、その分合計値は大きくなります。競技プログラミング久しぶりにリアルタイムで参戦できたので結果のまとめです。Bは奇数でなくてはいけません。Bが偶数ならNo、奇数ならYesを出力すればOKです。Cが3通りしかないので愚直に組み合わせを試行しても良いですが、計算で解けるのはかなり明らかなのでその必要は無いかなと。単語を読み取りながら、2つの条件にあっているかを逐次チェックしていけば良いです。・その単語はまだ発言していない単語であるハッシュを使って既出かどうかを確認します・その単語の先頭の文字は直前に発言した単語の末尾の文字と一致する直前の単語の末尾と同じかどうかを判定します。x3とたどることになります。x2について考えます。x1とx2に訪れるためには、DがXとx1の距離とx1とx2の距離の公約数である必要があります。効率的に=最短回数で訪れるには、Dが最大公約数であれば良いことになります。x3についても同様です。Xと各xiの距離の最大公約数を求めることになります。複数の値の最大公約数は、2つの値の最大公約数を求める処理を用意しておき、その結果と3つ目以降の値の最大公約数を順次求めていけば求まります。「偶数枚のコインが置かれたマスの数を最大化」するには、奇数のマスから奇数のマスにコインを移動することになります。総コイン数が偶数であれば、全てのマスが偶数になりますし、奇数であれば1マス以外が偶数になります。一つのポイントは、各マスにつき一度しかコインの操作が出来ない点です。・奇数のマスを見つけたら次の奇数のマス目までコインを移動するという操作を繰り返していけば良いです。最短の操作数という制約はないので、どういう経路でマス目をたどるかは気にしなくて良いですね。その制約があると、もっと難しかったと思います。添字の扱いがちょっとごちゃごちゃしてしまいました。出力の最初に操作の数を出す必要があったため、最初に操作内容(どのマスからどのマスに移動するか)を配列に入れておき、最後に結果を出力するようにしました。s[i][0],s[i][1],t[i][0],t[i][1])end結果Dで凡ミスで一度WAを食らってしまいましたがとりあえず全部解けました。今回はABC単独開催だったので、Dもそれほど難しくなかったからだと思います。順調にいけば次回あたりで水色は達成できそうな見込みです。ARCにもチャレンジしようかな。競技プログラミング問題https://beta.atcoder.jp/contests/abc108/tasks/arc102_a解法a+b、b+c、c+aが全てkで割り切れると言うことは、$$(a+b)\%k=(b+c)\%k=(c+a)\%k=0$$ということです。・aがkで割り切れる場合(a+b)%k=0よりbもkで割り切れることになり、さらにcもkで割り切れることになります。a、b、cが全てkで割り切れる場合に条件を満たすことになります。a%k=1の場合、b%k=k-1となり、c%k=1となります。その場合、(c+a)%k=0となるにはkが2である必要があります。次にa%k=2の場合、b%k=k-2となり、c%k=2となります。その場合、(c+a)%k=0となるにはkが4である必要があります。場合に条件を満たすことが分かります。よって、aが偶数の場合と奇数の場合でそれぞれ個数が変わります。bi)の組み合わせについて、a→bの順番でソートします。ソート後の組み合わせについて、昇順に橋を落とす範囲を求めていきます。その場合、i番目とi+1番目について、以下の4つのケースが考えられます。ケース1の場合、i番目の条件が達成できればi+1番目は必ず達成されるので、i+1番目は無視することが出来ます。bi+1)に更新して次に進みます。bi)に更新して次に進みます。bi+1)に更新して次に進みます。このようにして、橋を落とす範囲を移動させながら、落とす橋の数を数えていくことで求まります。最大になるのは、mがaiの倍数-1の時で、余りはai-1になる。よって、mがa1,a2,,,anの最小公倍数-1の時にf(m)は最大になる。最大値を求めるだけなら最小公倍数自体は求める必要は無く、ai-1の総和を求めれば良い。(最初、mを求める問題かと思い、最小公倍数を求めるコードを書いてしまって時間ロス。各自がとるべき戦略を考えるにあたり、まずはどのような状態で勝敗が確定するかを考えます。勝敗が確定するのは、以下のように片方が端っこに追いやられた状態で、次のターンがまわってくる場合です。この状態でAliceが次のターンだとAliceの負けになります。この1ターン前の状態、2ターン前の状態を考えると以下のようになります。このように1ターン前の状態をたどっていくと、「隣接した状態になると次のターンの人の負けが確定する」ことがわかります。次に初期状態でのAliceとBorysの間のマスの数について考えます。AliceとBorysの間のマスの数が1であれば、最初にBorys側に移動すれば隣接状態となるためAliceの確定します。AliceとBorysの間のマスの数が2の場合、AliceがBorys側に移動すれば次のターンでBorysが隣接してくるとAliceの負けが確定します。よって、Borysと反対側に移動することになり間のマスの数は3になります。すると、BorysはAlice側に移動してくるので、再び間のマスの数は2に戻ります。これを繰り返すことになるため、最終的にAliceは端っこに追い詰められて負けてしまいます。よって、Aliceは必ず負けます。AliceとBorysの間のマスの数が3の場合、最初にAliceがBorys側に移動すると、AliceとBorysの間のマスの数は2になります。これは上記の「AliceとBorysの間のマスの数が2の場合」の逆になるため、今度はBorysが必ず負けます。間のマスの数が奇数の場合、Aliceの勝ち間のマスの数が偶数の場合、Borysの勝ちであることがわかります。選んだ人より東の人の内、東を向いている人の数となります。よって、上記を数え上げる配列を最初に作成し、それぞれの和が最小となるものを求めれば解にになります。例2の場合、上記の配列は以下のようになり、上下の配列の和の最小値は4となります。文字列のサイズが最大でも100なので、全ての切断箇所のパターンで「どちらにも含まれる文字」の種類を数え上げれば解けます。Rubyの場合、配列の「&」をとると共通部分が求められるので、実装は以下のようになります。