2022年10月30日日曜日

トヨタ自動車 プログラミングコンテスト2022(AtCoder Heuristic Contest 015)

 水パフォは出たものの、AHCでレートを上げられなかった。

コンテストへのリンク
コンテスト後のツイート

・一手先のコマをどこに置くか? と考えて盤面を傾けるのが本質だった。言われてみれば確かに。
・モンテカルロ法を使うのは悪くないらしい。使い方が悪かった模様。

2022年10月29日土曜日

yukicoder contest 366

 Cまで三完。Dを思いつかず終了。


No.2112 All 2x2 are Equal

 自力AC。

 市松模様に塗り分ける。(i+j)%2==0であるマスを左上から順番に塗り、その後、(i+j)%2==1のマスを右下から逆に塗っていけばOK。

 お絵描きしていたら偶然思いついたが、偶然としかいえない。

No.2113 Distance Sequence 1.5

 最大値に着目すれば良いというツイートを見てAC。

 ゲームの問題になっているが、差がK以上の組があるとまずいのはほぼ明らかなので、数え上げの問題。
 どう数えるかで困っていたら、最大値に着目というツイートが目に入ったため解くことができた。

2022年10月28日金曜日

AtCoder Regular Contest 146

 AB二完で終了。

コンテスト後のツイート

C - Even XOR

 解説AC。

 コンテスト終盤、Sの要素で場合分けする、という方針を思い付き、N=4までは実験コードと結果が一致した。そのとき考えていたのは、

・相異なる3要素がSに入っていれば、それ以外の要素一つが禁止になる

 というものだった。偶然N=4までは一致したが、これは間違い。

 線形独立性を考えるのがポイントで、正しくは、

・x個の要素がSに入ったら、x個のうち一つを0に平行移動させ、それと線形従属な$2^{(x-1)}$個が禁止になる

 だった。

 コンテスト中書いていたコードを少し変えれば通った……という意味では惜しかったが、線形独立性は全く思いついていなかったので本質が分かっていなかったという意味では惜しくなかった。

D - >=<

 珍しく自力AC。

 できるだけ小さくしたいので、ANS=[1]*Nから始めて、条件p, x, q, yについて、ANS[p]>=x となる部分があればANS[q]=max(ANS[q], y)もしくはANS[q]=max(ANS[q], y+1)と、条件を満たす最小値へ更新していく。

 今更だけど、CでなくDへ行くべきでしたね。題意を理解するのにちょっと時間がかかる問題なので避けてしまったけど、ちゃんと検討すべきだったかなぁ。

2022年10月27日木曜日

AtCoder Regular Contest 148

 Dまで四完。このコンテスト終了時、AtCoderのAC数がちょうど3000になった。

コンテスト後のツイート

E - ≥ K

 解説放送を見てAC。

 数列Aを小さい順、もしくは大きい順に見て、DPか何かで計算……みたいな方針を考えたが、これだと上手くいかない。

 今回は、

・大きい方か、小さい方か、どちらかなら並べ方が一通りに定まる

 というもの。

 上から見れば/下から見ればOKというものではないので気付きにくく、違う方針を検討してしたくなるけれど、こういう風に「上手い順番で見れば計算できる」こともあると押さえておこう。
 

2022年10月24日月曜日

Codeforces Round #829 (Div. 1)

 Cまで三完。Dは解法はあっていたけど制限時間が厳しく通せなかった。

コンテスト後のツイート

D. The Beach

 自力AC。
 ツイートした通りで、空きマスから適切にダイクストラをすれば良い。

 コンテスト後、Rustで通したが、書くのに30分以上かかっている。もう少し速く書けるようになりたいね。PyPyで通している人はいるけど、ちょっと技巧的な気もするし、それでもギリギリなので、他言語への書き換えが素早くできると良かった。

 このコンテストは、based on Moscow Team Olympiadということなので、PyPyじゃ制限が厳しい問題が出題される可能性は高いと思っていた。この問題は制約を見ればPyPyでは厳しそうと分かる。Rustで時間内に書き切る自信があればRustで書こうとしたはずなので、もうちょっと慣れて、速く書けるようになりたい。

yukicoder contest 365

 調子が良くなかったとはいえ、一問も解けずに終わった。復習しましょう。


No.2103 ±1s Game

 解説AC。

 (コンテスト終了後)解説とほぼ同じことも考えたのだが、それで良いのか確信が持てずに愚直を書いたりしていた。

No.2104 Multiply-Add

 解法は自力で分かった。

 ユークリッドの互除法の要領で(a, b)→(x, 0)に、(c, d)→(y, 0)にしたとき、xとyが一致していればOK。(a, b)→(x, 0)→(c, d)のように変形すれば良い。

 ただ、最初から片方が0のときの場合を考えておらずWAを出してしまった(テストケースを見て気付いた)。気を付けねば。

キーエンスプログラミングコンテスト2022(AtCoder Beginner Contest 274)

 Eまで五完。

コンテスト後のツイート

F - Fishing

 一応、自力AC。

 イベントソートという方針は合っていたが、同時に出入りがあったり、0秒ちょうどに出ていくものを忘れていたりしていた。

 また、PyPyで通すのは結構厳しく、FractionをソートしたりしてはTLEが取れない。出入りする時間にある程度大きな整数をかけて誤差を小さくし、tupleを一次元化してからソートしたら通った。

G - Security Camera 3

 解説放送を見てAC。

 コンテスト中、フローだと思ったし、「燃やす埋める」のスライドなどを見に行ったりしたがグラフを構築できなくて、うーん。

 ただ、この問題は、二部グラフの最小点被覆と見るのが分かりやすかったか。けんちょんさんのqiitaの内容はしっかり抑えたい。

 また、グラフ構築の際、

・何を頂点にし、何を辺にするか

 を考え、

・上手くいかなかったら逆(今まで頂点にしていたものを辺に、辺にしていたものを頂点に)も試してみる

 などをすれば解けた気もする。

 類題を解いておこうと思って、これを解いたが(一応、解説は見ないで解けたが)かなり苦戦した。フローのグラフ構築は難しい。

2022年10月21日金曜日

パナソニックグループプログラミングコンテスト2022(AtCoder Beginner Contest 273)

 Eまで五完。実装難の問題が多くて辛かった。

コンテスト後のツイート


F - Hammer 2

 解説AC。

 区間DPらしい……確かに!
 区間DPと言われれば解けた。DPだろうとは思ったのに、区間DPを思いつかなかったのひどい。
 実装が間に合わなかったのなら仕方ないけど、解法を思いつかなかったのはまずい。

G - Row Column Sums 2

 DPだというツイートを見て、冷静に考えたら解けた。

 上の行から見て、残りの行についての和が0の個数、1の個数、2の個数を持てば良さそうだが、ちょっと考えれば「残りの行についての和が1の個数」だけ持って、残りの和がいくつかを管理すればDPが回ることが分かる。
 これで計算量が二乗になる。

 Nの制約からDPを考えるのは自然だし、RやCが2以下という制約から、それぞれの個数を持ちたいと思うのも自然ですね。

2022年10月20日木曜日

AtCoder Regular Contest 151

 ABの二完で終わり、レートを大きく落とした。B・Cで答えが合わず、愚直を書くのに時間を費やしたりしているのが厳しい。

コンテスト後のツイート

C - 01 Game

 自力AC。

 実験などして、同じ数字に挟まれている部分はturnが奇数個、別の数字に挟まれている部分はturnが偶数個増えることは分かった。

 なので、あとは両端について分かれば良い。
 真似っ子戦略ができそうだが、今一つ分からず愚直コードを書いたら、

・両端以外のturnが偶数個のときは、両端の空きマスが同じ個数のときのみ後手の勝利
・両端以外のturnが偶数個のときは、両端の空きマスの個数が1個差で、大きい方が奇数個のときのみ後手勝利

 と分かった。
 前者は真似っ子戦略を考えれば当然。
 後者は両端を「二個以上減らすことはできるけど、一個減らすことはできない」ことを使う。同じ数字を隣におけないため、一個減らそうと思っても不可能なのだ。
 なので、二個減らす回数の偶奇により、勝者が変わることになる。

 本番は、後者のとき、「両端の空きマスの個数が1個差」であれば後手が勝利していると勘違い(実験コードの分析を間違った。上記の理屈にも気付かなかった)したためWAが一個出てACできず。

 これは時間がなくて焦っていたせいですね。もうちょっと余裕があればACにたどりつけてそう。

D - Binary Representations and Queries 

 解説AC。

 問題内容を把握するのに時間がかかってしまい、解説を読んでも「なんでこんなに解かれるの?」という気持ちだったが、多少整理すると「確かにそこまで難しくないか」とも思えてきた。

・Xが異なればクエリの順番を入れ替えてもOK

 と気付くのが重要。
 これは、言われれば確かにそうか、という気持ちになる。

 これさえ気付ければ、各Xのクエリは二者で足し合うだけなので、最初の数字を1としてシミュレーションすれば良い。

E - Keep Being Substring

 解説AC。

・XとYに共通部分がある→一番長い共通部分をsuffix arrayとLCP配列を使って探す
・XとYに共通部分がない→一文字にした後、Yのどれかの文字へ変形するのが最適。最短経路問題になる。

 言われてみればそう難しくない。

 ただ、一番目について、同じことを考えたのだが、最長の共通部分の求め方が分からなかったし、解説を読んでもLCP配列が何かすぐに思い出せなかった。文字列アルゴリズムは適宜使えるようにしておきたい。

2022年10月19日水曜日

Codeforces Round #826 (Div. 3)

 Eまで五完。Rustで解いていたら、Dまででかなりの時間がかかってしまい、EからPyPyに。が、Fが解けずに終了。Fは考察から間違っていた。


F. Multi-Colored Segments

 一応自力ACした。

 [l, r, c]についてlでソートしたとき、最も大きいrと、それとは色が違うものの中で最も大きいrを管理する。
 ……というようなことを二回(lについて左から、rについて右から)で解けると思ったのだけど、WAが出て困った。

 結局、l, rそれぞれについて、大きい順・小さい順でソートして、計四回似たようなことをしたらACしたが、それで良いのかよく理解していない。

G. Kirill and Company

 解説ACしたが、解説を理解するのにも、実装にも苦労した。

 まず、

・ある車を持っている友人のがいる頂点を使ったとき、どんな車のない友達の集合を運べるか? という候補を知りたい。

 これは、BFSしながらDPして調べられる。
 DP配列としてはベキ集合を持つ。つまり、問題文の図にある頂点5なら、{{0, 1}, {0, 2}}を持つようにする。(0, 1, 2は車のない人のindex。たとえば1は2に住んでいる)
 BFSして、車のない人の家を通るたび、今までのDPの各集合にその人のindexを追加していく。
 なお、実装上は、{{0, 1}, {0, 2}}でなく、{3=(1<<0)|(1<<1), 5=(1<<0)|(1<<2)}を持った方が良い。

 これをした上で、

・車を持っていく人を順に見て、どんな集合に対処できるか?

 を見ていくDPをする。
 公式解説にあるように、これはbit DPというよりはナップザックDPに近い。

 
 解説を読んだ際、前者を処理した後どんなDPをすれば良いか分からず理解に時間がかかってしまった。自然なDPなのだが、bit DPだろう、と思っていると盲点になりやすいかもしれない。


Codeforces Round #828 (Div. 3)

 E2が解けずに終了。

コンテスト後のツイート

E2. Divisible Numbers (hard version)

 解法ツイートを参考にAC。

 制約を考えると、約数・倍数の関係で絞るしかない。a*bの約数を使うはず、というところから進まなかった。

 正しい方針は、a*bの約数xをa~cで利用したいなら、a+1以上でxの倍数のうち最小のものを使うべき。これは求められる。同様に、yは、b+1以上でa*b/xの倍数のうち最小のものを試す。

 a~cの範囲でxを決めたとき最適なyを求めるためにはどうするか? という考え方はE1でも使っていたのだから、約数の関係を利用して同じようにすれば良かった。多少焦っていたにせよ、これくらいは気付きたかった。

2022年10月16日日曜日

Codeforces Global Round 23

 Cまで三完と悲惨な出来。


D. Paths on the Tree

 解法ツイートを見てAC。本番中1500人近くも通していたから簡単なのかと思ったら、解法も実装も難しくてびっくりした。

・各頂点の重複度の最大値と最小値が高々1しか離れない

 と気付くのがポイント。

 これは直観的にそうだよね、と思いたい。

 頂点xの重複度がyで、子の数がcのとき、xの子たちの重複度は、y/cの切り捨てか切り上げになる。これを繰り返しても、(頂点1の重複度である)kを、pathをたどったとき現れる子の数c_1, c_2, ...の積で割ったものの切り捨てまたは切り上げになる。割り算の式から不等号を導けば、証明できたが、そんなことをしなくてもまあ直感的に(あるいは知識として)正しいと分かっておきたいもの。

 これを利用して木DPすれば解けるのだが、実装もなかなか大変だった。
 

E1. Joking (Easy Version)

 解法ツイートを見てAC。

 0, 1, 2の3要素が残ったとして、

・{1,2}を聞く
 →”NO"なら{1}を聞く
   →"YES"なら{1,3}に、"NO"なら{2,3}に絞れる

 →"YES"なら再度{1,2}を聞く
   →"YES"なら{1,2}に絞れる。"NO"なら最初に"NO"が来たときと同じ手順を踏む

 とすれば三回で2/3くらいになってACできる。

 試行錯誤するしかないけれど、Aと¬Aを質問するのは意味が変わらない、ということには早く気付くべきだった。そうすれば、三等分するという方針には早くたどり着けたと思う。(が、三等分してからも難しい。コンテスト中も三等分することは一応考えたけど、その後が思いつけていないので……)

2022年10月15日土曜日

yukicoder contest 364 (Do you know Cherry Contest?)

 Eが解けずにマラソンへ行き、マラソンが10位。 通常(アルゴ)のコンテストにマラソン問題が混じっているのは好き。

コンテスト後のツイート

No.2101 [Cherry Alpha N] ずっとこの数列だったらいいのに

 解説AC。

 イベントソート(平面走査)だとは思ったが、何を管理すれば良いかが分からなくなってしまった。

・元の数列の値(減り終わったら0に更新する)
・減り始める時間
・減る途中のものの個数

 を持って、減り始めるときと、減り終わるときにupdateするようにすれば、答えを求めることができる。

 イベントソートという方針自体はすぐ思いついたので、時間があれば解けたとは思うが、何を管理すれば良いか考えるのはいまだに苦手。とはいえ、解けなくてはいけない問題でした。

 なお、PyPyだと(意外と)制限時間が厳しく、セグ木の関数で内包表記を使っているとTLEが取れなかった。PyPyだと内包表記が遅いのには注意。

2022年10月14日金曜日

ユニークビジョンプログラミングコンテスト2022 夏(AtCoder Beginner Contest 268)

  ABCEFの五完。

コンテスト後のツイート



 G - Random Student ID

 解説放送を見てAC。

 あんまり自分で考察しなかったけど、考察ができてもTrie木を使うことを思い付けたかどうか。Trie木を使わなくても上手くソートすれば解けそうだけど、実装で苦戦してしまいそう。

Ex - Taboo

 解説放送を見てAC。

 Aho-Corasick法を勉強しました。
 もっと難しいかと思っていたけれど、結構理解しやすいアルゴリズムでした。
 


Codeforces Round #827 (Div. 4)

 Rustで出て全完。時間はかかったが、Rustで全完できたのは良かった。
 →システムテストも全部通ってた。結構Hackが出てたので心配していたけど、通って安心。

コンテスト後のツイート




2022年10月13日木曜日

AtCoder Regular Contest 149

 Cまで三完。

コンテスト後のツイート


D - Simultaneous Sugoroku

 解説AC。
 いわゆるマージテクではなかった。

・Xの範囲が小さいので、区間[1,10^6]の全ての答えを求めても良い
・区間を最小値・最大値で管理する

 の二つがポイント。

 ただ、一つ目を思い付けば二つ目は自然か。
 Xの最大値が大きくないことに注目して、データを扱いやすい形で持ちたい、と考えれば一つ目の考え方も自然。

 そもそも数学では、「一般化した方が扱いやすくなる」問題は多いのだから、一般化できないか? と考えてみるべきでした。

 なお、テストケースが弱い模様。
 木の根から答えを反映させるって処理をサボって、各座標ごとに子孫がどこへたどりつくか調べるのを投げてみたら通ってしまいました。

2022年10月12日水曜日

yukicoder contest 341

 ABの二完。


No.1917 LCMST

 解説AC。

 一見手がかりのない問題だけど、最小全域木を作る方法は普通はクラスカル法かプリム法なわけなので、

・最小全域木を作る方法としてクラスカル法を用いよう、そのために、辺の候補を絞り込もう

 と考えるのが重要。

 そして、最小公倍数が問題になっているのだから、約数・倍数の関係を用いて絞り込むのだろうな、と考えれば(証明はともかく)解説の方法を思い付くことは可能そう。

 難しいけど、多分こうだろうな、という考察を推し進めていけば思いつけない問題ではなかった。

2022年10月11日火曜日

Codeforces Round #825 (Div. 2)

 Cまで三完。

D. Equal Binary Subsequences

 解放ツイートを見てAC。

 二個ずつ同じ文字にしよう、という方針を思い付ければそう難しくないが、色々な方針がありそうなため難しい。難しいけど、色々試す中では思いついても良いよねぇ……。

 二個ずつ同じ文字にするためには、別の文字であるペアから、010101……となるものを選んでrotateさせれば良い。

2022年10月10日月曜日

AtCoder Beginner Contest 272

 Fが解けず。

コンテスト後のツイート

F - Two Strings

 解説AC。

 コンテスト中、Suffix arrayを見てこれを使うのでは? と思い、S、TをSuffix arrayを作るようにソートすれば、尺取りで解けそうと考えた。が、同じ文字が続く場合や、SとT(を回転させたもの)が一致するときの処理が上手くできなかった。

 Suffix arrayをもっと上手く使えないか? と考えるべきだった。

 SやTを回転させたもの全てを調べたいので、S+S、T+TにSuffix arrayを使う。
 さらに、SとTを直接比較したいので、S+S+T+TにSuffix arrayを使う。
 そして、同じ文字が続くときの処理のため、S+S+"a"*N+T+T+"z"*NにSuffix arrayを使うと答えが得られる。

2022年10月9日日曜日

AtCoder Regular Contest 150

 Cまで三完。

コンテスト後のツイート

D - Removing Gacha

 解説AC。

 深さの逆数は考えたのに、(深さの逆数+1)を今までの答えに掛けるのかな? とか考えて分からなくなってしまった。深さしか答えに寄与しないというのは、まあ直感に違わないのに、解けなかったのは悔しい。



2022年10月8日土曜日

Dytechlab Cup 2022

 Dまで四完。

コンテスト後のツイート

E. Ela Goes Hiking

 解説AC。

 左から1~x番目の蟻のうちx番目の蟻が勝つ確率を考えるのがコツ。この考え方は、漸化式を立てよう、という気持ちでも思いつくかもしれない。
 で、この確率は、x番目(が左端でないなら)が左を向いており、そのすぐ左に、右を向いた蟻が連続していて、自分と合わせて合計でx/2匹以上の蟻に合成されるような場合となる。

 さらに、x番目の蟻が全体で勝利する確率は、

・1~x番目で勝利する
・x+1番目以降で勝利する蟻がいない

 こと。

 ただし、x番目の蟻が1~x番目の中で勝ち残る、という条件の元では、x番目の蟻は左を向いているので、[x+1,2*x]番目の蟻が勝つことはない。ので、2*x+1番目以降の蟻が勝利しない確率を掛ければ答えが求まる。

2022年10月4日火曜日

yukicoder contest 313

  Eまで五完でした。Fも解けなきゃいけなそう。方針は合ってそうだが……。


No.1677 mæx

 (今更だが)自力AC。

 構文解析+DP(メモ化再帰)。
 昔書いたDPのコードがあったので、それを利用してACした。
 各"("に対応する","や")"がどこかを前計算しておけば、それを利用してDPできますね。

2022年10月2日日曜日

yukicoder contest 362

 Cまで三完。

 Dまでは、計算量云々するパズル的な問題ではなく、数学は知っているけどプログラムはしたことない人にも解いてもらえるような教育的な問題が出題されていました。
 Eはパズルっぽいですが、計算量ではなく、論理式に関するものですね。


No.2089 置換の符号

 置換「3 1 2」を見て、どういう定義だっけ? と思い、やめてしまった。(いくらAHCで疲れていたとはいえ、ひどい)

 1 2 3が3 1 2へ移るような置換という意味ですね。
 置換を互換の積に直せば良いので、実装してAC。転倒数の偶奇と一致するのは知りませんでしたが、言われてみればなるほど。

 いや、それにしても置換が何なのか分からなくなったのはなぜなんだろう? (3,1,2)みたいに書いてあれば分かったのか?

No.2090 否定論理積と充足可能性

 自力AC。

 手元で計算したら、

・$((\neg a \vee \neg b ) \wedge c) \vee ((\neg d \vee \neg e ) \wedge f) $

 のようになったので、左辺が$\bot $になるためには、$a=b=c$が必要(右辺も同様)と分かった。

 つい変形してしまったけど、プログラムで書くなら全部の真偽を試す方が早いですね。


estie プログラミングコンテスト2022(AtCoder Heuristic Contest 014)

 プレテスト114位、システムテスト126位でした。

コンテスト後のツイート



 この感想ツイートが長くなったので、こっちにまとめておきます。 


 序盤は、「オセロっぽいな」と思い、オセロの評価値として「自分が置ける位置の個数」が有名なことにならい、「次に作れる長方形の個数」を評価値にしようとしました。が、これで長時間回してもあまり伸びない。なので、それに代えて、

・長方形の周囲の長さ

・次におく頂点のweight

・長方形を作ったとき、新たに作れるような長方形の個数

 あたりを評価値に。


 最終的には、

・次におく頂点のweight/(長方形の周囲の長さ^(1~4のランダムな数))

 にしました。(それをheapqに突っ込み、上位三つのうちからランダムに採用)

 解説放送を見ると、weightは取り入れなくて良かったらしいので、それを消して回して実行してみたけど、うちの環境だと点数は伸びません……。(PyPyだし、実行回数が足りないのか? と思い、10倍の時間回したので比較したら多少は伸びたが、50ケースで+100万もなさそう)

 解説放送で言っていた「枠」という概念にはたどり着けなかったけど、まあそれっぽいことは考えていたとは思う。

 「枠」は思いつけたとしても実装に反映できたか自信ないし、評価値については及第点かなぁ。


 山登り・焼き鈍しについては、

・部分的に残して作り直す

 としていました。答えの列のある長方形を見て、それを作るのに必要なものたちだけでやり直す、という山登りです。


・最終スコアが大きい答えの、ランダムな長方形一つ

 を残すのに加えて、weightの大きい頂点までいったものを採用したいと思っていたので、

・(スコアは悪くても)weightの大きい頂点(長方形)

 を残してやり直すことも実装しました。

 解説放送では、部分的に壊してやり直すと言っていて、そっちかー、という感じに。

その方が自然な山登りだけど、大きいweightのものを残したいと思ったので、考えなかった。

 どのくらい差があるのかは分からないけど、weightが大きい頂点を残したい、と思ったのは筋が悪かったのかな……。


 感想書いたけど、何を反省すべきかよく分からない!

 高速な言語(C++かRustで書くのは考えた)で書いていれば気付けたことはあったかもしれないけど、気軽に色々試すなら慣れているPythonの方が良い、と思ってPythonで書いているので。

 最後、C++に書き換えようと思ったとき、書き換え時間の見積もりがまずくて終わらなかったのは良くないけど、そんなことを反省しても、という気がするので。