2022年8月31日水曜日

AtCoder Beginner Contest 265

　Eまで五完だが、Eは嘘でした。

コンテスト後のツイート

E - Warp

　解法ツイートを見て改めてACした。

　（A, B）をi回、(C, D)をj回、(E, F)をk回使ったときは何通り？　という非常に自然なDPで良かった。
　最初見たとき包除原理に見えてしまい、そこから方針転換できなかったのは反省。

F - Manhattan Cafe

　解説放送を見てAC。

　単純なDPを累積和で高速化する問題だが、単純なDPすら思いつかなかった。
　というか、そもそも誤読していた。（格子点の数も二つだけと思ってなかったし、制約ももっと大きいものと思っていた）

　N次元空間などと言われると、苦手意識があるためまともに考えられなくなる気がする。空間把握などが必要な問題が解けないのは仕方ない部分もあるが、今回の問題は、定義に従ってDPを組むだけなので、空間把握などは不要な問題だった。

　苦手意識があると、つい考えることをやめてしまいたくなるが、ちゃんと問題を読み、定義に従って考えよう。

G - 012 Inversion

　解説放送を見てAC。

　セグ木を使いそう、というのは一目で分かった。セグ木の各要素として何を持てば良いか、というところで詰まってしまったが、これも自然に考えれば分かるものだった。落ち着いて考えれば自力で思いつけたと思う。

　ただ、実装には苦戦した。遅延セグ木を使うのだが、可換性が成り立たない演算があるため、自分のライブラリ（これ自体あまり整備されていないのだが）を修正しないといけない部分が多かった。この辺は慣れておきたい（遅延セグ木の整備もすべきか……）。

　難しくはないのだが、実際に通すのは結構大変。
時刻: 0 件のコメント:
ラベル: ,

yukicoder contest 356

　眠くなってしまいA一完だったが、いくら眠くてももっと解けなくちゃいけなかったような……。


No.2035 Tunnel

　自力AC。
　各マスが取り除かれるとき、一つ前取り除かれたマスより二個以上離れていることを使えばOK。

No.2036 Max Middle

　一応自力ACだが、最初、大きい数からシミュレーションしてTLEを出してしまった。

　A[i]とA[i+1]の大小関係だけ分かれば良いと気付くのが重要。

　一番左のものから操作を行うとすると、A[x-k]<A[x-k+1]<...<A[x]>A[x+1]のA[x]に操作したら、A[x-1], A[x-2], ..., A[x-k+1]に順番に操作でき、さらに、その操作後、操作した部分は単調増加になると分かる。これを使うと回数が計算できる。

　どんな操作を行っても回数は同じというのは、解説のように、<>が><になると考えれば確かに、という感じです（証明せずACしてしまった）。

No.2037 NAND Pyramid

　自力AC。

　実験したら、2x回やった結果が元の形と一致していると気付いた。最初だけ（1が一個のブロックがある場合？）違うことがあるようなので、何回かシミュレーションした後、前後を削っていけば良い。

No.2038 Strange Arrange

　自力AC。これは結構すぐ分かった。

　1, 3, 5,...番目を1にすると、偶数番目を全て2以上にしなくてはいけなくなる。次に、同じことを偶数番目について考えれば良い。2, 6, 10, ... を2にする。そうやって再帰的に構成していける。
時刻: 0 件のコメント:
ラベル:

2022年8月29日月曜日

yukicoder contest 358

　A一完。Rustで出ようとしたら、Rustと関係なくBが分からずに終了。


No.2057 Ising Model

　解説AC。

　まあ、全部-1か、1と-1の交互だよね、と提出してみたらWA。
　それ以外に、ただの「1 -1 1 -1 1 -1……」という交互ではなく、最初の1を-1にしたもの、という可能性があった。気付かなかった。

No.2058 Binary String

　自力AC。といっても、実験したら答えが分かっただけ。
　解説の証明は鮮やかですね。

No.2059 Odd Move Nim

　自力AC。
　これは、ちょっと考え付いて思いついた解法がそのまま答えでした。（証明もできたつもり）
時刻: 0 件のコメント:
ラベル:

2022年8月20日土曜日

yukicoder contest 357

 　A、C二完。


No.2042 RGB Caps

　解説AC。コンテスト中はちょっと見て分からなくて飛ばしたとはいえ、ちょっと見た段階で分からなかったのはダメ。

　3個ずつ、Rが1個、Gが1個、Bが1個となるように並べていけば全ての場合を作れる。

No.2044 Infinite Nim

　解説AC。

　コンテスト中、

・-1以外のもののxor
・（-1の個数）% 2

　が答えに影響しそうなことが分かって、サンプルを元に適当に投げたらWA。解説を見て、-1の個数が奇数のときは常に先手が勝ちというのを見て、「あれ、それは一回考えたはずなのに？」となった。
　頭が働いていないと、一回考えたことも答えに反映させることを忘れてしまう……。

No.2046 Ans Mod? Mod Ans!

　解説AC。

　式変形すると、x<yであるようなy%xの総和を求めなくてはいけない、というところで詰まった。

　ここでさらに、

・y%x=y-x*(y//x)

　と式変形するのがポイント（だが、難しい）。
　y//xの総和ならBITを用いると、調和級数の計算量で求めることができる。
時刻: 0 件のコメント:
ラベル:

2022年8月18日木曜日

RECRUIT 日本橋ハーフマラソン 2022夏（AtCoder Heuristic Contest 013）

　pretest 66位、最終順位49位でした。ほぼツイッターのコピペですが、一応まとめておきます。ツイッターだと重くてAnimation GIFが貼れなかったので、こっちではそれを。Web版ビジュアライザの機能を使ったのですが、容量が結構大きくいですね。

コンテストへのリンク


・解法

　ある数字をEの字型で全てを繋げる。それが上手くいきそう（5000点くらい取れそう）なら二つの数字で、Eと∃を作る。
　Eと∃両方をちゃんと作れたのはほぼなく、K=5でNが大きいとき7000点くらい。
　Eは概ね作れたけど、Nが小さいときは無理で、そのときのフォロー方法はできませんでした（時々2000点とかになっている）。

・seed 1でScore = 5192
　二色結ぶのが上手くいかなかず、一色のみ結んだときはこんな感じ。
　Eと書いたけどEにはしてなくて、

　その数字が多い行いくつか決め打ち、そこにその数字を集める→行同士を繋ぐ。そのとき、どの列でつなげば一番コストが低いか、列を全探索

　としています。



・seed 7、Score = 1737。
　密集しているため、あまり集めたい行に集められずに移動は終了しています。
　その後は、1--x--1みたいに、ペナルティ一つで二つの連結成分を繋ぐことも使って頑張っています。


・seed 11、Score = 7402。
　Eと∃が両方そこそこ作れたパターン。上手くいってもこのくらいです。Eと∃を作ると書いたけど、縦と横を入れ替えたやつも試しました。



時刻: 0 件のコメント:
ラベル:

2022年8月16日火曜日

Codeforces Round #813 (Div. 2)

　Dが解けなかった。

コンテスト後のツイート


D. Empty Graph

　重みがmin(A[l:r+1])でなく、min(A[l],A[r])だと誤読してWAを量産したけど、本来の問題も難しかった。

　解説ツイートを読んでAC。

　答えがx以上になるためには、

・全てx/2以上
・隣接要素の両方がx以上となる箇所がある

　が必要（と、考察するのが難しい）。
　判定問題が解けたので二分探索すればOK。
時刻: 0 件のコメント:
ラベル:

2022年8月15日月曜日

AtCoder Grand Contest 058

　Bまで二完。Bはここなどで既出だったらしい。

コンテスト後のツイート

C - Planar Tree

　解説AC。

　「1と4」と「2と3」で分けて、「1と4」を「2と3」に繋げて消していき、全部消せたら（「2と3」のみ残ったら）OK、と考える方針は合っていたので、考え続けていれば解けた可能性はあるが、解法Stepを考えると1/4あたりまでしか辿り着けていなかったと思うので、ACまでは遠かったか。
　特に、同じ数字をつぶして良いということに気付いていなかったのが厳しい。

　まず、

・同じ数字をつぶす
・1と2が隣接→2だけ残す、3と4が隣接→3だけ残す

　として良いと気付くことが重要。

　そうすると、その後の操作では、

・...4 2 3...の4と3を結び、3だけ残す。（4 2を消す）

　というような操作しかなく、その操作で2と3のみが残れば良いので、2と4の個数、および、1と3の個数を比較すれば良いと分かる。

時刻: 0 件のコメント:
ラベル:

2022年8月9日火曜日

Codeforces Round #810 (Div. 1)

　ABの二完。 だが、Eが既出でunratedになったりして大変なことに。

コンテスト後のツイート


C. XOR Triangle

　解説AC。難しいが、手順を踏めば解ける問題という気もする。

　入力が01列で与えられているので、桁DPを使うんだろうなぁ、ということは分かる。

　その後の考察は難しいのだが、桁に注目して実験などすれば、a,b,cのある桁での値を000のように三つの数字で表すと、

・011か100の箇所が一ヶ所以上ある
・101か010の箇所が一ヶ所以上ある
・110か001の箇所が一ヶ所以上ある

　という条件を満たせば良いと分かるのだろう。解説に証明は載っており、証明を理解するのは難しくないが、この道筋で導出するのは困難な気がする。

　あとは、これを桁DPする。

・DP[i][j]で、iはa, b, cがMAXと一致しているかの八通り,  jは、011/100, 101/010, 110/010 を使ったかの八通りを持つ

　そして、a, b, cの各桁に0/1がきたときどうなるか、という遷移を考えれば良い。


　言われれば書けるけど、コードに直す部分も難しいなぁ……。

時刻: 0 件のコメント:
ラベル:

2022年8月8日月曜日

Codeforces Round #812 (Div. 2)

　Dまで四完。

コンテスト後のツイート

E. Cross Swapping

　解説AC。面白い問題だったが、最初の一手にさえ気付いてなかったので、何も言えない。

　まず、

・A[i][j]はA[j][i]としか入れ替わらない

　と気付くのが重要。（コンテスト中散々実験したのに気付かなかったのはひどかった。何故……）

　だが、A[i][j]とA[j][i]を入れ替えたいとき、iとjのどちらを用いてswapすれば良いか分からない。また、入れ替えたくない時、iとj両方使わないのか、もしくは使うのかが分からない。

　これは、グラフの問題になる。

　左上から貪欲に、A[i][j]とA[j][i]の大小に従って、iとjでswapする/しないが一致する場合は0の、一致しない場合は1が書かれた辺を張っていく。そして、iとjがループしてしまいそうなときは、辺を張らないようにする。なぜなら、ループができたら結果が決まらなくなるため。左上から貪欲に決めているので、前に決めたことを優先した方が良い。

　こうして決めた後、木それぞれについてswapする、しないを割り振っていけばOK。
時刻: 0 件のコメント:
ラベル:

LINE Verda プログラミングコンテスト（AtCoder Beginner Contest 263）

　Eまで五完。Gを考えていたが、Gは惜しくなかった。

コンテスト後のツイート

F - Tournament

　解説AC。

　DPだとは思ったが、どういうDPにすれば良いか組み立てられなかった。完全二分木なので、各段ごとにDPしていくというのは自然なのだけど、その後どう立式するかが難しい。
　勝者以外のもらえるお金を持つというのは、言われてみれば分かるけど思いつきにくい。

G - Erasing Prime Pairs

　解説AC。

　問題を見たとき、まずフローを疑ったのに、グラフの作り方を思いつかずその方針を追わなかったのはひどい。1がなければ、偶数と奇数で二部グラフになるのね、なるほど。

　実際にACしたのは、頂点を倍加し、i→j+Nに、A_i+B_iが素数のときに無限の流量を流す、という方法でACした。この解法の正当性が話題になっていたが、noshiさんのツイートに証明が書いてあった。

時刻: 0 件のコメント:
ラベル: ,

2022年8月7日日曜日

yukicoder contest 355

 　睡魔に襲われてしまいA一完でした。横になっているときにBは思いついたんだけど、起きてから解き終わりませんでした。


No.2028 Even Choice

　偶数番目の$A_i$を使うとすると、それ以降のものは全て使える、ということには結構すぐ気付いたが、実装で困った。
　後ろのindexから見て、heapqを使って、上位K-1個の値と総和を管理していけば解ける。

No.2029 Swap Min Max Min

　（寝ていたため）最初、想定解法が間違っていたという話を知らなかったが、その間違った解法で解いてしまった。

　Nが奇数の場合、奇数番目を小さい数字で埋めれば良い。
　そのあため、Nが偶数の場合、奇数番目全て、もしくは偶数番目全てを小さい数字で埋めれば良い、というのは嘘。
　ちゃんと考えると、途中まで偶数番目で、途中から奇数番目でもOK。

　解法ツイートを見てしまったけど、sampleが合わないのでそれを元に考えれば、時間あったら気付けたはず。
　ただ、sampleになかったらWAを出していただろうし、テスターだったら気付けてなかった可能性が高いよね……。

No.2030 Googol Strings

　これは自力AC。
　max(len(x)*2,len(y)*2)まで調べて、そこまで一致していたらどちらかがどちらかのprefixになっているので、長さを比較。

　で、合っている気がするけど証明できていない。

No.2031 Colored Brackets

　自力AC。DPですね。
　
　
時刻: 0 件のコメント:
ラベル:

2022年8月4日木曜日

yukicoder contest 277

　Cまでの三完でした。


No.1332 Range Nearest Query

　解説をちらっと見たらセグ木二分探索と書いてあって、確かにそれでいけるか、と思っていたけど、実際に実装するとWA。
　ちゃんと解説を読むと全然違っていて、クエリ先読みが本質の問題でした。


　……と、当時書いたままACしていなかったけど、今更、解説AC。

　絶対値を考えるときは、正と負に分けて考えるのが定石の一つ。
　正だけを考えると、平面走査＋セグ木でできる。


時刻: 0 件のコメント:
ラベル:

2022年8月2日火曜日

Codeforces Round #811 (Div. 3)

　全完を逃した。
　システムテストは全部通っていました。

コンテスト後のツイート


時刻: 0 件のコメント:
ラベル:

2022年8月1日月曜日

CodeTON Round 2 (Div. 1 + Div. 2, Rated, Prizes!)

　AB小森健。Eの四完。紫に落ちました。辛い。

コンテスト後のツイート

D. Magical Array

　解法ツイートを見てAC。

　不変量を探す問題なのだろう、とは思ったが、それを探すことができなかった。
　正しい不変量は、

・i*A[i]の総和
・累積和の総和

　（どちらでも良い。どちらも不変量）だった。

　なぜ思いつかなかったかというと、A[i]とA[0]の差に着目してしまったというのが大きい。ある配列からの差分を考えているのだから、差分が重要なのだろう、と考えていた。

　どう思いつけば良かったんだろうか。

　累積和くらいとってみても良かったのでは、というのは一つある。

　他には、Operation 1とOperation 2の違いは、足すindexが一つ違っているというだけなのだから、index*（何か）みたいに、indexを使った不変量があるはず、という風にして思いつく方向性もあったかもしれない。

　解法ツイートで見たのだけど、配列を頻度分布とみなせば、操作1では総和が1増え、操作2では総和が2増える、ということから考えることもできた。
　これは凄く自然で納得できる。が、頻度分布とみなすところが難しいなぁ。
時刻: 0 件のコメント:
ラベル:

第三回日本最強プログラマー学生選手権-予選-（AtCoder Beginner Contest 262）

　Eまで五完。

コンテスト後のツイート

F - Erase and Rotate

　解説AC。

　ある数字を先頭に持ってくるためには、

・それより前を全て消す
・それより後の数字を全て消すもしくは先頭へ移動させた後、その数字も先頭へ持っていく

　のいずれかの方法がとれる。
　コンテスト中は二番目の方法しか考えていなかったためダメでした。

　一旦先頭へ持っていった後は、範囲最小値が分かるセグ木を使って、あるindex iからi+Kの間にP[i]より小さい数字があればindex iを消去、というのを繰り返せば良い。（先頭への移動がない場合も、この方法で作ればOK）
　ただし、Kが余っていたら、最後にPの後ろを消すのを忘れずに。

G - LIS with Stack

　解説放送を見てAC。

　解法を理解するのも実装するのも難しい。
　indexがどこに移るか考えて、「区間で何かする」という発想に思い至れば思いつけるのかなぁ。

Ex - Max Limited Sequence

　解説放送を見てAC。

　解法（の高速化以外の部分）を理解するのはそれほど難しくないけど、普通にやろうとするとDPが二乗になってしまう。確かに高速化できそうではあるのだが、実装方針が難しいし、方針を理解しても実際の実装には非常に苦労した。

　解説の方法で実装したけど、遅延セグ木を使った方が実装しやすいのかなぁ。どっちみち大変そう。
時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)