ABC109
A - ABC333
AとBが両方奇数なら問題ない。掛け算してmod2で終わり。
B - Shiritori
やるべきことはすべて問題文に書いてある。
まずは重複排除にsetを使おうとするが、文字列を文字のリストとして読み込んでいたため、リストのリストがsetに変換できずちょっと詰まる。
ゴリ押しするために読み込みの段階で文字列リストと文字列の両方の形式で別々のリストに格納する。
その後文字列のほうをsetに変換して長さ比較して重複チェック。
重複チェックにおいて問題がおきなかったら、今度は文字のリストになっているほうでループを回して、前の単語の末尾と今の単語の先頭が合致しているかをチェックしていく。
しりとりの条件を満たしているならばYesを出力して終了。
C - Skip
とりあえず全部の座標(xi)をXとの距離に変換する。
あとはそれらの最大公約数を求めればいいことはすぐわかった。
とりあえずソートして重複排除して、そこからの簡略化で悩む。
とりあえず１個ずつ最小公約数とっていく方針でやってみて、TLEでるかなーって思ったらAC。
gcd部分はよそから持ってきたけど編集ミスってそこでWA。
D - Make Them Even
とりあえず全マス通る方針でいけそうな予感がしてくる。
条件をよく読んだところ、とりあえずすべての行を横にみていき、奇数が検出された場合は入れ替える、という処理を行う。その後右端の１列について同様の入れ替えを行えば、最大HxW-1回の変換ですべてのマスを網羅することが可能とわかった。
あとは愚直に書いてバグをとってAC
パフォは1423だけど水色までは上がらず。ARCとかに出てたときのやらかしが響いてるなあ。
こういう簡単な回でミスを出さないようにしたい。
ABC108
久しぶりに参加。
A - Pair
2で割って余りつかって奇数と偶数の数を割り出した後、かけ合わせればおわり
B - Ruined Square
頭の中で正方形描きながら、xの増加分をyに足して、yの増加分をxから引いて・・・と
順番に考えていって合計4回足し算引き算して終わり。
(x2, y2)→(x3, y3)のところで、間違えて(x1, y1)を基準にしたためサンプルが通らず。
よく読んだら気づけたのでOK。変数名が悪かったかも
C - Triangular Relationship
とりあえずmodで考える問題だろうなというところからスタート。
a,b,cをkで割った余りがx,y,zとすると、0<=(x+y),(y+z),(z+x)<2k-1であることから、
それらをkで割った余りが0になるパターンは、0かkのみ
さらに、x+y=kかつy+z=0のようなパターンは、x-z=kとなるが、0<=x,z<kであり
これらを満たすx,zの組は存在しない。
したがって、x+y=y+z=z+x=kまたは、x+y=y+z=z+x=0である
このとき、x=y=z=k/2または0
0であるパターンは、Nに含まれるKの倍数すべてであり、その個数の3乗
k/2であるパターンは、kが偶数の場合のみ存在し、N + K/2に含まれるKの倍数の個数
であり、その場合に存在する組み合わせは求めた個数の3乗
この2つを合計すると答えが出る
最初にk/3で考えてしまってサンプルが通らなかったりしてたけど、
通せた段階でのスコアはノーミスで7位だった
D - All Your Paths are Different Lengths
配点を見て絶望する。皆目検討がつかなず諦めかけていたが、10^6という条件が
引っかかったのでそこから考えてみることに
多重辺がOKなので、まずはシンプルに0,1の組み合わせを考える
その上に何がつながるか考えて、0,2を考えると、0-3まで網羅できることがわかった
ここで、最初の1→2の間の辺を、0,1,2にすると、たとえば上を0,3,4とすると
0→4と1→3で選んだときが同じになってしまい、唯一性を満たさない
ということで0,3,6にしてみると、これはうまくいきそうだが、そもそも
2^20で40本使って20本余った状態で、10^6を超えられるならばそちらのほうが
簡単だろうと思い、計算してみたところ本数に余裕があることがわかったので
それ以上は考えないことにした。
これにより、基本となるツリーが以下のように完成した
1 2 0
1 2 1
2 3 0
2 3 2
3 4 0
3 4 4
...
ここで、問題となるのは2の累乗の超過分である。
別のツリーを作って・・とやっていくとさすがに辺の本数が足りない
ここでまた20分ほど試行錯誤した結果、まずはLを2進数にすることを考えた
そして、0であるビットを示すものを前に、1であるものを後ろにして、
その切れ目の頂点からNまでを新しい辺でつないでやればよかったと考えた
ところが実際にコードを書いてみると、L-1の距離をもつルートはあるが、L-2が
満たせない場合があるなど、歯抜けになってしまうことがわかった。
ここで解決策が思いつかず、残り20分を切る。
結果的に、たとえばL=100であるとすると、
1 =(0,1)=2=(0,2)=3=(0,4)=4=(0,8)=5=(0,16)=6=(0,32)=7
という形が基本になる（カッコの中は辺の長さ、カッコなしの数字は頂点）
ここでまず、0-63までは網羅され、残りは36個である
その後、頂点6までは0-31をもっていることから、6-7を長さ64の辺でつないでやれば
よいことがわかる。この時点で、残りは4個である。
その後、3と7を長さ96の辺でつないでやれば、96-99を網羅することができ、
完成となった
これを一般化して、大きい頂点から順番に、そことNをつないだときの経路数が
Lを超過しないならば、現在の経路数+1の長さの辺でNとつなぐ、という操作を
繰り返し、ACのコードが書けた
実際には、脳内でぐちゃぐちゃやっていた部分のせいでつなぐ頂点を1個間違えたり
経路数+1の長さの辺でつなぐ、というところがうまく理解できていなかったり、
長さはLまでではなくL-1までだということがすっぽ抜けたりしていて間に合わず、
コンテスト終了の7分後に通過
途中で心が折れていなければ間に合っていたかもしれないなあというペースなので
純粋にくやしいですね
それはそれとして、パフォーマンス的には1600だったのでレートも上がって満足
次回からまたARCに挑戦するか、水色まではABCで頑張るかは未定
ABC103
久しぶりに完答
A:
最初のコストが0なのを見落としていて無駄な時間がかかる
意味もなくソートしたりしたけど、実際はmax - minをすればいいだけ
B:
1こずつずらしてn回ループするだけ。pythonのリスト分割はやはり便利
C:
mを最小公倍数-1にすればいいのではと思ってぐちゃぐちゃやってた
実際のところ、mが最小公倍数なら、各要素はa_{i} - 1なので、もっと簡単
...なんだけど、それを手計算したら1ずれるとかなってて混乱してた。要反省
D:
これも問題の読み間違い。一直線なのに木構造と勘違いして悩む。
で、入力部分書くときに木はどこ？ってなって判明。あのさぁ・・・
とりあえず重複部分を削除するため、、iと組になるj（j > i）について、最小のjについてi-j間で切ればいいいことがわかる。
ということでj - 1で切って、次のiはj以上のものから検索、ってやろうとしたらサンプルでエラーが出た。
なんでやーって思ったら、1-7と2-3があった場合、7で切って3で切らないみたいなことをやってしまっていた。
ということで、各aに対して、最小のbのみを記録した配列を作成する
で、全体をみて最小のbの手前で切るのが一番効率がいいので、そこで切り、そのb以上であるaの中から、新たにbが最小となる点を探すように探索を行う。
これがギリギリで間に合ってなんとか緑に
安定して完答ができれば水色までは狙えそうだね（今回のDはえらく簡単だったけど）
ARC100
C: Linear Approximation
+iの部分をまず数列aから減算しておく。
それにより作られたaの平均値をとり、そこから上下に値を移動させて、
悲しさが増減するかを検証し、減るようならば更新、増えるようならばストップ。
という形で作ったところTLE。
Dをちょっと考えてから戻り、まずは数列をソートしてみることに。
その後bを増減させたときの挙動について考えてみたところ、
bより大きい数のほうが多ければ、bを1増やすことで悲しさが減り、
逆ならば悲しさが増えるのではということがわかった。
結果的には、数列を加工して中間値を取ればよいだけだと判明したため、
そのようにコードを書き換えてAC。
D: Equal Cut
なんとなく試しに３個さしてみるところから先が思いつかない
とおもったけど別にしゃくとり法で計算するだけで
普通の計算時間になるからいらない方向に思考がいっていた気がする
Cは安定してとけてるからABCに戻るのもなんだかなあなので
過去問ノックを真面目にやってみるしかないのかな。
ARC099
ABC100でD問題までいけたから今回はARC
開始時間忘れてて21:17からスタート
C - Minimization
まず全体の最小値を出す。
前から順番に見ていって、最小値ならば次の数字へ。
そうでない場合、その数からK個目の間に最小値があれば、その区間全体をつぶせばいいのでカウントを１個増やして現在地からK+1番目の数へ移動。
最小値がない場合、現在地の１個前をつかってK-1個を変換する必要があるため、カウントを増やして現在地からK番目の数へ移動。
この場合に、変換する領域が１個でも重なっていれば前後は問わないので、一番最初の数からK番目の数までに最小値がない場合でも、計算上の問題はない。
ここまでで14分。解く速さがほしいなあ。
D - Snuke Numbers
ためしに10000くらいまで計算してみるも、法則性がいまいちつかめない。
前の数と次の数の間隔が少なくなることはなく、その間隔は10の累乗であることはなんとなくわかった。
ということで、今の間隔と、その間隔に10をかけたもののそれぞれについて比較を行って、間隔を増やしたほうが値が小さくなるならば間隔を増やす、という処理を行ったところAC。
なんだけど時間が1分ほどオーバーしてた。
完全な証明を思いついてないのももやっとするなあ。
Dで詰まっている間にEを見ていて、問題は似たようなのを過去にやった気がするなあってなったけれどぱっと思いつかず。
ファミリーを作っていってどうこうって形だったと思うけど。
このへんは経験不足だね。
