AtCoder Grand Contest 034 A,Bの解説

たぶん考察も実装も300レベルかなぁとか勝手に思っています。

Aに関しては解き方はすぐわかったり、BはCPSCOでこんな問題あったよな…となり結構早めに分かったんですが、A問題で4WAしたのが痛すぎた。本当に悔しすぎる…「この冷えの中、どれだけ自分を見失わずに精進ができるか…」というのが試されているのかもしれません。

とかいうのは置いておいて、自分なりの解説です。
Cを解説できるくらいの実力があればいいんですが…

敗因

問題文をちゃんと読んでいなかった
A問題、左右に移動できると勝手に思っていた…これからはちゃんと問題文を読みます…

A - Kenken Race

制約をちゃんと読みましょう。
1マス右か2マス右にしか移動できない。まず、C＜Dのときを考えます(クロスしない)。
最大で2マスしか右に移動できないということは、飛び越えられる岩の限界は1つまで。もし2つ連続して岩があったら、不可能です。for文をaからc、bからdにそれぞれしていくイメージで実装していけばいいです。

次に、途中でクロスしている、つまりD＜Cのときを考えます。すると、途中で順番を入れ替える必要が出てきます。クロスするとき、それぞれの位置関係はA＜B＜D＜Cなので、BからDの間に、「...」のような入れ替わりスポットがある必要があります。なので、あった場合はYes、ない場合はNoみたいな実装をすればいいです。

B - ABC

ABCがBCAになる…ということは、「A」と「BC」が入れ替わる、と考えてもよさそうです。
もうBCだと見にくいので、BCをまとめてXにすることにします。BCでもAでもないものは、/と書くことにします。

ABCACCBABCBCAABCB は、変換(?)すると
AXA///AXXAAX/ になります。AとBCを入れ替える作業を最後まで続けると、
XAA///XXXAAA/ という感じになります。この時点で、/で区切られた部分ごとに回数を計算して足していけばいいと分かります。この入れ替え回数は、「Aから見た時に右にあるXの数」で計算することができます。例えばXAXXの場合だと、Aは2回交換されます。

自分は後ろからXの数を数えていき、Aを見つけた時はans += Xの数として、もし/が来たらX = 0にする、という感じの実装にしました。「Aから見た時に右にあるBCの組の数」でなく、

「BCから見た時に左にあるAの数」をansに加えていってもいいです。たぶんこっちのほうが楽です。substr辺りが役に立ちそうです…(自分は使い方忘れていましたが)。

M-SOLUTIONS プロコンオープン

500が解けて900位台って何なんでしょうね…？最近の緑色と茶色、強すぎませんか（自分が弱すぎるだけ説もありますが）

というわけで解けた各問題の感想と解説です。

A - Sum of Interior Angles

n角形(nは3以上)の内角の和は(n-2)*180で表すことができます。ちゃんと括弧でくくりましょう。

B - Sumo

逆に考えてみます。つまり、「負けた回数が7回以下ならワンチャンある」みたいな考え方をします。
文字列についてその文字が'x'なら1を足す、という作業をしてその数が7以下の時にYESとすればいいです。

C - Best-of-(2n-1)

期待値できないんです…精進します

D - Maximum Sum of Minimum

自分はまず、グラフを紙に書きまくりました。そうすると、まず小さい数字は極力端に置いたほうがいいことが分かりました。もしも中央集権的グラフの真ん中が1だと、大変なことになってしまうので。
なので、葉からの距離を計算して、葉からの距離が小さい順に小さいのを入れていく…みたいな貪欲をしました→WA。えー

もしや大きい順では…？と思い少し変えたものを提出するも、これもWA。ちょっとだけACが増えたけど、半分以上がWAっていた。

この時点で、「考え方がずれてるのでは…？」と思った。よく考えてみると、「大きいのを隣同士にしたほうがいい」ということに気づいた。1000と1001は隣同士にすると、1000になるので。なので、中心っぽい所から、BFSをする感じで大きい数字を順番に書いていきました。はい。

diverta 2019 Programming Contest D - DivRem Number

500点問題が自力で通せました！嬉しい！（800は通せなかったけど）

問題

自然数Nが与えられるので、N/a == N%a となる自然数の総和を答えて下さい。

したこと

一旦入力例1を書き出してみた！
数字…(商,余り)のように書いてみると

1…(8,0)
2…(4,0)
3…(2,2)
4…(2,0)
5…(1,3)
6…(1,2)
7…(1,1)
8…(1,0)

という風になりました。

数学タイム

この場合、商と余りが同じなのは3と7の場合です。で、よ〜〜く考えてみると

xで割った商と余りが(a,a)になる自然数xは、必ずa+1以上である。

ということが分かります。なぜなら、xで割った時の余りは必ずx未満になるからです。
(例) 商と余りが(2,2)になる数字xは必ず3以上です。なぜならxが2以下だと割った余りが1以下になるので。

そう考えると、xは必ず(a+1)以上なのでNはa回割り切られるために(a+1)*a以上になる必要があります。(a+1)*aがNを超えたらそれ以上は無理です。for文でaを1から回していくと、だいたい√N回くらいのループになります。

Nが10のとき、商と余りがともに2となる自然数xは、(10-2)/2 = 4と求められます。商と余りがともにaとなる自然数xがあるかどうかの判定は、だいたい(N-a)%a == 0でできます。%を/に変えれば、xが求められます。

WAる

よっしゃいけるわ…！と思って出してみたものの、1問だけWA。これはコーナーケースか？と思ったので1から順番に試していくと、3辺りで間違っているのが分かった。一回一回のxを求めた時に本当に商と余りが合っているのかどうかのフィルターをif文でかけてみると、上手くいきました。（こういう対策方法良くなさそう…）

まとめ

以上です。今回使えた知識は
・とりあえず紙に書いてみる
・ちょっとした数学

でした。アルゴリズム成分は少なめだったと思います。以上です。

ABC-C埋めを済ましたので、振り返る

ABC-Cまでを埋め終わったので、一旦感想を書きます。

途中からScrapboxに解説を書いていった

scrapbox.io
ACしたけどよく分からんのだが…？という状態を極力避けるために、こういう事をしました。効果は他のと比較してないのでなんとも言えませんが、まぁ他の人が見た時に「ふーん」となってくれるのであれば十分だと思っています。

実装が難しいのは、一部だけ

基本的にはsortとかのSTL(元から使える関数とか)を使えばどうにかなります。DFSとかもあまり書かないイメージ。いや、書くこともある。
for文を回しながら最小値を更新していくとか、二重for文とかそういうのが出てくるイメージ。基本、全探索と基本が書ければ7割くらい通せるんじゃないでしょうか。累積とかimos法とかは使えるので覚えといても良いかもしれない。セグメント木とかUnion-Find木とかはABC-Dの方に出ると思います。

難しいやつは難しい（哲学）

ABC-Dレベルで難しいです。特に自分が苦戦したのは（覚えている範囲で）「双子と○×ゲーム」、「Blue Bird」、「倍々ゲーム」、「2D Plane 2N Points」辺りです。ABC-C簡単じゃね？と思う人は優先してこれを解きましょう。逆にそうじゃない人はこの問題に当たっても、「まぁ難しいんだな〜解説見よ」みたいな軽い気分で無理に頑張らなくてもいいと思います。解説ACで力を付けましょう。

次はABC-Dかなぁとも思っていますが、まずDPか？とも思っています（DPは優先して習得する必要があるので…）

AtCoder Beginner Contest 125 の解説

久しぶりに全完したような気がしますが、酷いミスが多すぎて喜べません…考察はすぐに生えたのにミスを量産してしまいました。具体的には

C…forの範囲をi <= n にしていてWA。正しくは i < n。
D…総和 - 最小*2 の所を、総和 - 最小 にしてしまった。

です。いやこれで15分ロスしてるんですが…悲しい…ということで解説です

A

T/A*Bを出力すれば良いです。

B

問題文に「一つも選ばなくてもよいです」と書いてある。宝石を取るメリットがある時(Vi > Ciのとき)は取っていき、その総和を計算すればいいです。

C

i番目を選んで数字を好きなものに変えるとします。
その時、「i番目以外全ての数字の最大公約数」と同じ値にしてあげるのが一番いい手です。例えば 1 10 10 10 10 で、1番目の数字「1」を書き換える場合、他の4つの最大公約数の「10」に書き換えてあげると答えは10になります。

よく考えてみると「i番目を書き換える時の最大の値は、i番目を除いた全ての数字の最大公約数」ということが分かります。一つの数字だけ無視できる、みたいな感じになります。
なのでこの問題は、「どの数字を無視すれば、最大公約数が最大になるか」のような問題にもっていけます。

このように、点線の丸以外の全ての数字の最大公約数は、左部分と右部分に分けてgcd(左の部分, 右の部分)と計算することができます。配列の扱いに十分注意して下さい。

D

Dのほうが簡単だったかも…？

隣り合った二つのプラマイを反転させる時、
① +と-→-と+（左右が入れ替わる！）
② -と-→+と+（マイナスを消した）
というふうなパターンに分けることができます。

1. - + + - + のようなものは、①のパターンを使いまくることで右に寄せることができます。

②番を使うことでマイナスを消していけますが、一度に消せるのは2つずつなので、マイナスの数が
・偶数…全てプラスにできる
・奇数…ひとつだけマイナスになってしまう
という風になります。①番を使いまくれば一番被害が少ない数字（絶対値が一番小さい数字）をマイナスにすることで、最大値にすることができます。

はい。急いで書いたのでクオリティが低いです。すいません。

エクサウィザーズ 2019 C - Snuke the Wizard

exawizards2019.contest.atcoder.jp

問題概要

分かりやすいけど、難しいので説明しません！（読めば分かると思います…）

気づいたこと

• 「俺の方が崖に近いのに落ちてない」みたいなことは絶対にない。

例えば左から100番目のやつが左に落ちた時、必ず左から1~99番目のやつも落ちている。
なぜなら、99番目のやつは100番目より右に行くことは不可能だからです（最高でも重なるのが限界）

→ゴーレムが、2つの境を挟んで、
左に落ちる 左に落ちる 左に落ちる || 落ちない 落ちない 落ちない 落ちない || 右に落ちる 右に落ちる 右に落ちる
となっていることに気づいた

この時点で、この問題は「左に落ちるボーダーライン || と、右に落ちるボーダーライン || を求める問題」に変換できる。

• とある地点のゴーレムが落ちるかどうかは、シミュレーションすればN(Q)で求められる

int ochi(int now) 関数を作って、左に落ちる→-1、落ちない→0、右に落ちる→1と返すようにした

ボーダーラインの求め方…にぶたん！！
二分探索を使えば、ボーダーラインがlogNで求められる。今日二分探索を使う問題を解いたばっかだったので、その発想はすぐに浮かんできた。
めぐる式二分探索を使った。leftとrightを使って、(ochi(i) == -1)と(ochi(i) == 1)のボーダーラインをそれぞれ求めた。

あとは「ボーダー右 - ボーダー左」を出力すればいいです。

AGC032 B - Balanced Neighbors

atcoder.jp

グラフで考えた

隣接するグラフの頂点の番号の和が、同じになるように辺を引きましょう。という問題。前半は実際にグラフを書いていた。う〜ん難しい。

隣接行列で考える

途中で隣接行列で考えるようにすると、とても考えやすくなりました。例えばN=6のとき。それぞれの行がそれぞれの頂点と繋がってるかどうか？を考えていきます。

それぞれの合計を取ると、

こうなります。実は、逆向きに斜め線を引くと合計が同じになります。

ここまでくるとあとはこれを実装すればいいんですが、今回の制約を見ると、Nが100以下なので

• boolのN×Nの隣接行列を作って、
• 左上から右下にfalse false…とする
• 右上から左下にfalse false…とする
• 辺の数を数えて、出力する
• 辺を出力する

という風に実装していけばいいです。

Nが偶数か奇数か？で場合分けをしないと、斜め線がクロスする辺りでWAが発生します。気をつけましょう。