2022年12月28日水曜日

Codeforces Round #841 (Div. 2) and Divide by Zero 2022

　Cまで三完。Eは通したかった。

コンテスト後のツイート

D. Valiant's New Map

　二次元Sparse table（か、二次元セグメント木）でやるしかないと思ってコンテスト中書いたがWA。
　クエリ計算のところで、二点のminではなく、四点のminを取るよう修正したらMLEになりました。

　昔、二次元Sparse tableを書いたときそれだけで数時間かかったことを思えば成長。一旦Sparse tableを取ったあと、そのそれぞれの要素についてもう一度Sparse tableを取ると考えたら、それほど詰まらずに書けました。このままライブラリ化しても良いかも？
　この感じなら、二次元セグメント木も書けそうな気がしてきました。

　ただ、この問題はそういうデータ構造を使わなくても解ける問題でした。毎回二次元累積和を取る解法でAC。

E. Graph Cost

　約数包除くでgcdの個数を列挙した後、大きい方から貪欲にやればOK。
　という解法は分かっていたけど、約数包除の実装でミス。時間がなかったので、ベン図など書かずにこんなものかな、と実装したらダメ。ちゃんと図を描いたら解けました。
　
時刻: 0 件のコメント:
ラベル: ,

2022年12月25日日曜日

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

　E飛ばしてGまで六完。Eも最後に解法を思い付いたので、解きたかったね。

コンテスト後のツイート

E - Don't Isolate Elements

　自力AC。

　終了一分前くらいに、上の二行の表裏を管理してDPすれば良いと気付いた。結構実装の大変な問題なので、コンテスト中にACするのは厳しかったかも。
時刻: 0 件のコメント:
ラベル:

2022年12月23日金曜日

HHKBプログラミングコンテスト2022 Winter(AtCoder Beginner Contest 282)

 　Fまで六完。

コンテスト後のツイート

　ツイートの「スライド最小値」は「Sparse table」の間違いです。

G - Similar Permutation

　解説AC。

　コンテスト中に、この問題の解説を見直し、同じようなDPをするしかないな、と思い、それを累積和か何かで高速化するんだろう、とは思った。
　ただ、高速化の方針が分からず、とりあえず計算量を無視して書いてみたが答えが合わず終了。

　答えが合わなかったのは添え字のミスで、自分のコードを見れば二次元累積和を使えることは分かった。考えていたときは、それでも計算量五乗になってしまい間に合わないと思っていたが、（解説および）自分のコードを見たら四乗にできることが分かった。

　正しい方針を思い付いているのだから、解き切らないと。

Ex - Min + Sum

　解説放送を見てAC。

　Cartesian Treeという単語は知らなかったけれど自然な解法ですね。計算量解析の部分はちょっと難しいですが。

　ただ、Cartesian Treeを使って分割統治する方針だと自分の実装だと通らず、

import pypyjit
pypyjit.set_param('max_unroll_recursion=-1')

　というおまじないを書いて通りました。この高速化を書いたの初めてです。
時刻: 0 件のコメント:
ラベル:

Codeforces Round #834 (Div. 3)

　Eまで五完。


F. All Possible Digits

　自力AC。

　少なくとも、p以内に答えが見つかる（１の位が一周するので）。今までに使った数字を範囲の形で持てば、全ての数字を使っているかをチェックすることはできる。
　ケアすべきは、「最初」「１の位が使われていない最大値に到達したとき」「繰り上がったとき」「繰り上がった後、１の位が使われていない最大値に到達したとき」。これらを実装すれば良い。

　コンテスト中は、パッと見て桁DPとか思って飛ばした記憶があるのだけど。全然違った。

G. Restore the Permutation

　自力AC。

　「小さい数字をできるだけ前に置く」という方針で考えたくなるがそれだと上手くいかず（この方針でも可能だと思うけど、実装の仕方が分からなかった）、「大きい数字をできるだけ後ろに置く」という方針を取ると簡単だった。

　小さい方から考えて上手くいかないなら大きい方からも考えてみよう、と思わなくてはいけませんね。
時刻: 0 件のコメント:
ラベル:

2022年12月20日火曜日

Codeforces Round #840 (Div. 2) and Enigma 2022 - Cybros LNMIIT

 　ABDの三完。Cを飛ばしたのは正解だったけど、Eを解き切れなかったのは良くない。

コンテスト後のツイート

C. Another Array Problem

　同じ隣接2マスに二回操作を行うと両方とも0になることを利用すると、配列の長さが4以上なら全体を最大値にすることができる……と気付けるかどうか。

　愚直を書けば気付けたかと思ったけど、愚直を書いたつもりで「同じところは二回やらない」みたいな実装にするとダメ。結構ハマりやすいかも。

E. Node Pairs

　たくさんWAを出したけど一応自力でAC。

　ツイートで方針はあっているけど、頂点数2だけでなく、もっと頂点数が多い完全グラフも複数回使うことがあるので、個数制限のないナップザック問題のようにして解けばOK。

　最初、頂点数の多い完全グラフから貪欲に使っていけば良いのでは？　と考えたため、大体一回ずつしか使わないという考えから抜けられなかったのがまずかった。

　
時刻: 0 件のコメント:

Codeforces Round #839 (Div. 3)

　全完。結構時間はかかったけど、まずまずの出来か。

コンテスト後のツイート


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

2022年12月14日水曜日

Codeforces Round #837 (Div. 2)

　Cまで三完。


D. Hossam and (sub-)palindromic tree

　解法ツイートを見てAC。

・二頂点i, jに対して、DP[i][j]=頂点iと頂点jを端点としたときの最大スコア

　として、頂点iとjの距離が小さい方から更新していけば良い。遷移も二乗で収まる。

　ただ、実装の仕方が悪いのか、PyPyでは通せず、Rustでも制限時間ギリギリの時間になってしまった。
時刻: 0 件のコメント:
ラベル:

2022年12月12日月曜日

デンソークリエイトプログラミングコンテスト2022 Winter(AtCoder Beginner Contest 280)

　Fまで六完。

コンテスト後のツイート

E - Critical Hit

　ACはできたけど期待値DPで立式できなかったのは反省。
　最初DPで解こうとしたのに、DP[i]=i回で倒せる確率　とか考えたせいもあって立式できなかった。

・DP[i]=体力iからの攻撃回数の期待値

　とするとよかったようだ。最初の攻撃がクリティカルかどうかで場合分けして立式することができる。

G - Do Use Hexagon Grid 2

　解説放送を見てAC。

　x, y, x-yを管理すれば二次元でマンハッタン距離を考えたときと同様にできることは分かったが、二次元のバージョンがそもそも分からなかった。

　「x座標の下限、y座標の下限」を固定して考えるのだけど、そのとき、下限上にある代表点を決めれば重複なく数えられる、というのがポイントか。
　これで重複なく数えられるというのは気付きにくかった。

　なお、実装も大変。
時刻: 0 件のコメント:
ラベル: ,

2022年12月11日日曜日

yukicoder contest 369

　Bまで二完。


No.2132 1 or X Game

　解説AC。

　二連続で「-X」を行えないというルールのため、愚直を書くのが面倒くさい。かといって、自力で周期を導出するのはなかなか大変。
　また、周期が分かっても意外と実装しにくく答えを合わせるのが大変。

　だから、難問とは言えないかもしれないけど、ACしにくい問題に思えるのだけど……。

No.2134 σ-algebra over Finite Set

　解説AC。

　集合の「かつ」「または」「補集合」という演算について閉じているので、それらに関して独立な要素の個数を数えて、その2ベキが答えになることは分かった。
　が、要素の個数の求め方で迷走してしまった。（xorの掃き出し法とか使えるのかと）

　実際は、各要素について、それを含むような最小の集合を求めれば良い。それらの個数を数えればOK。
　言われてみれば難しくないけど、線形独立性と混乱したのが敗因。
時刻: 0 件のコメント:
ラベル:

2022年12月10日土曜日

AtCoder Beginner Contest 281

　Fまで六完。

コンテスト後のツイート

G - Farthest City

　解説AC。

　頂点1に距離が近い頂点から決めていくDP。

・DP[rest][last]で、決めていない頂点がrest個で、最後に決めた（今までに決めた中で距離が最も長いもの）の頂点の個数がlast個であるようなものの個数

　とすると遷移が求められる。

　そういうDPだと言われれば解けるけど、コンテスト中は何をすれば良いか分からなかった。

　制約からDPを疑うのは自然で、DPしようと思うなら、1から近い距離の頂点から決めようと思うのは自然。そう考えれば、自然な解法のはずなのだが。
時刻: 0 件のコメント:
ラベル:

yukicoder contest 371 (Asakatsu Presents)

　Dまで四完。


No.2157 崖

　自力ACだけど時間がかかった。

　普通に考えると三乗のDPになるけれど、それをどうやって高速化するか、という問題。

　まず、各D[i]をソートしておき、

・DP[i][j]=D[i][j]を使うときの、最小のfの値

　としたとき、

・DP[i][j]のままいけるのは、D[i+1]の値が、D[i][j]以上D[i][j]+DP[i][j]以下のとき
・それ以降は、D[i]の差に従って増えていく

　なので、前者を（双対）セグ木を使って更新。後者は別の配列を用意して求めた。


　実装大変だった割にたくさん解かれているなぁ、と思ったら、答えで二分探索すれば実装が楽だった模様。答えで二分探索は最初考えたけれど、なぜかできない気がしてやめてしまった。
時刻: 0 件のコメント:
ラベル:

AtCoder Grand Contest 059

　B一完でした。

コンテスト後のツイート

A - My Last ABC Problem

　（ツイッターで検索した範囲では）他に誰もしていない誤考察をしていた。「二色の連続部分列があれば、その二色のうちどちらか一色へ一手で変えられる」という。はっきり間違いですね。
　これに基づいた愚直解法を書いていたので、合うわけがない。

　愚直を書くときは、変な考察を交えず、本当に愚直になっているか確かめるべき、というのが教訓かなぁ。しかし、実際のところは、初手でこういう勘違いをしてしまうと、コンテスト中に気付くのは難しい気もする。

　正しい解法は、色が切り替わる箇所を二つずつ減らせる、というもの。端点についての考察は必要だけど、直感だけでいったら初手これを考えるだろう（解けなかった人でもこれを考えた人は多いはず）、というものでした。
時刻: 0 件のコメント:
ラベル:

2022年12月6日火曜日

yukicoder contest 368

 A一完でした。


No.2125 Inverse Sum

　解説AC。

　整数問題なので因数分解して右辺を定数（今回なら、N, Mを含まないP, Qのみの式）にしたくなる気持ちは分かる。
　因数分解の難易度が結構高い気がするけど、大学受験数学で十分出題されうるものか。

No.2126 MEX Game

　これは自力AC。

　後手は、Aにxが一個だけあり、MEXがxより大きいとき、それを別の数にすることで、MEXをそこまで減らせる。
　逆に、先手としては、0, 1, 2, ...がずっと複数個存在するような操作をすれば良い。
時刻: 0 件のコメント:
ラベル:

2022年12月2日金曜日

yukicoder contest 370

　Dまで。

コンテスト後のツイート

No.2144 MM

　解説AC。

　一個おきの階差が+1, -1されるんだなぁ、というところから考察が進まず。
　交代和、もしくは偶数項・奇数項の総和を考えれば良かったのですね。一項おきの何かに注目するという着眼はあったのだから、もっとそこを追及しなくてはいけなかった。

　その後の解説の方法は綺麗だけど思いつくのは難しそう。DPでも解けるらしいので、そちらの方が現実的か。
時刻: 0 件のコメント:
ラベル:

2022年12月1日木曜日

Codeforces Round #836 (Div. 2)

 　遅刻してA一完。Bでハマってしまった。


B. XOR = Average

　nが奇数のときは[1]*nで良い。
　コンテスト中20分以上考えたが、nが偶数のときを思いつかなかった。最後の二要素で辻褄合わせをする……みたいな方針を考えたが上手くいかなかった。

　結論からいうと、[1,3]の後に[2]を続ければ良い。

　二要素で条件を満たすものがあれば、後にずっとその値を続ければ良いですね。言われてみれば当たり前。

E. Tick, Tock

　解説ツイートなどを見てAC。

・矛盾するかの判定→重み付きUnion-findで行、列ごとに管理
・答えを求める部分→A[i][j]が-1なら行iと列jをUnionして、連結成分数を見る。全体の連結成分が1よりいくつ大きいかを求めて、hをそのベキ乗したのが答え

　とした。

　矛盾するかの判定は自分で考えたこともあり、二度手間になっている気がするけどもっと楽にできるのかな？　よく分かっていない。
時刻: 0 件のコメント:
ラベル:

2022年11月30日水曜日

AtCoder Beginner Contest 278

 　Fまで六完。

コンテスト後のツイート

G - Generalized Subtraction Game

　解説AC。
　
　真似っこ戦略は考えたがGrundy数を考えなかった。
　Grundy数さえ思いつけば自然に解ける（計算量が若干不安だが）し、ゲームなのだからGrundy数を考えるのは自然だった。

　ただし、実装はなかなか大変。
　最終的には、sys.setrecursionlimit(10**7)が必要なことに気付かず苦戦してしまった。これがなくてもREではなくWAが返ってくるため気付きづらい。
時刻: 0 件のコメント:
ラベル: ,

2022年11月27日日曜日

Codeforces Global Round 24

　Cまで三完。


D. Doremy's Pegging Game

　「N/2個連続で消した時点で終了」だから、最後に消す頂点とその幅を固定して、残りの頂点から何個消すかを選べば、二項係数と階乗で計算できる。

　「残りの頂点から何個消すかを選べば」というところでハマっていた。残りの頂点からも、N/2個連続で選んではいけないので、選び方を求めるのにDPが必要で、計算量三乗かかるんじゃないか、と。
　しかし、最初に選んだ箇所がN/2以上なので、残りの頂点はN-(N/2+2)以下だから、そういう事態は起きない。だから、組み合わせで計算すれば良いと分かる。

　普通はハマらないような箇所でハマって解けなかったのはおかしい。

E. Doremy's Number Line

　ツイッターで解法を検索してAC。

　どういう問題か理解するのが難しいが、整理すると、

・A[0]>=kならOK、A[0]+B[0]<kならダメ
・それ以外の場合、k-B[0]に色が塗れれば良い。そのためには、A[i]+B[i]>=kとなるようなiがあれば良い。
・一番最初に色を塗る際は、A[i]が大きいものを使いたいので、A[i]+B[i]>=kなるiのうち、A[i]が小さいものから使っていく。

　という感じになる。

F. Doremy's Experimental Tree

　解説ツイートを見てAC。

・Fを大きい順に見て、F[i][j]が繋がっていないなら、iとjは直接つながれている（Union-findで結ぶ）
・重さW[i][j]を知るためには、F[i][i]とF[i][j]を比較する

　一点目がポイント。小さいループの方がFの値は大きくなるので、これが分かる。

　ただ、PyPyだと時間の制約もメモリの制約も厳しく、ACまでは非常に苦労した。もうちょっと定数倍の良い解法がありそう？
時刻: 0 件のコメント:
ラベル:

トヨタシステムズプログラミングコンテスト2022(AtCoder Beginner Contest 279)

　Dまで四完。


E - Cheating Amidakuji

　取り除かったときの結果と比較して何かする、という方針は考えたのだけど、うまくいかないと思ってやめてしまった。
　一つ取り除いたとき、最終結果とどう変わるか、と考えるのが重要だった。

　……というか、考えなくても分からないと厳しくって。

　一つ除いた場合とそうでない場合とを実験して比較して……というような手段を取れば確かに分かるのだろうけど、この問題はそこまでするような難しい問題ではないと思う。最終結果との比較でできるのかな？　と思ったら、解法のやり方でいけるのかな？　と思えて欲しいところ。
　そう思えなかったのは、頭が働いてなかったということなのかね。

F - BOX

　適切にUnion-findを使えば解けるということはコンテスト中から分かっていた。

　が、実装難しくないですか？　何を持てば良いか整理した後で、一時間以上実装にかかっている。
　コンテスト中に通すのは厳しかった気がする。こんなに解かれているのが不思議。

G - At Most 2 Colors

　自力AC。

　「自分と違う色が最も最近現れたのはいつか？」を持てば二乗DPになる。そこから、累積和を使って（セグメント木を使うこともできそう）高速化する。

　Gとしては簡単だし、今回のEやFと比べると簡単な気がする。Eは発想問題だから人によるかもしれないけど、Fよりは明らかに簡単では。
時刻: 0 件のコメント:
ラベル:

2022年11月23日水曜日

HACK TO THE FUTURE 2023 予選（AtCoder Heuristic Contest 016）

 　最終144位でした。

コンテスト後のツイート


　クリークに分解したのを上手く戻せたら……という方針でやっていて、どうもうまくいかないため、残り二日あたりで各頂点の辺の個数だけを見る方針に切り替えた。

　結論からいうと、どちらでも上位を狙えた模様。
　ただ、クリーク判定は他の方の解説など見てもいまいちやり方が分かっていないので、辺の本数だけ見る方針に早い段階で切り替えた方が上位に入る可能性は高かったか。

　辺の本数だけ見る方針でもTOP10に入れたらしい。
　ここで重要なのは、確率epsのノイズが入ったときどういう辺の個数の分布になるか、というところ。そのあたりの考察が甘かった。（クリークを考えたときや、epsが小さい場合でも、そのあたりをきちんと考えるのが大事だったみたい）

　この辺、ちゃんと考察を立式して考えるべきだった。まあ、上手い式が浮かんでいないから立式できていないのだけど、式を探す努力もしていなかった気がする。

　また、ノイズに強い「良いグラフを探す」というのは、結構序盤から時間があったらやろうと考えていて、結局最後までできなかった。この辺もできていればもうちょっと違ったかも。

　時間いっぱいやり切ったつもりだったけど、そう考えると結構やり残しはあるなぁ。
時刻: 0 件のコメント:
ラベル:

2022年11月22日火曜日

AtCoder Regular Contest 152

　AHCで疲れていたので、unratedで参加してAだけ解いて終了。


B - Pass on Path

　自力AC。

　どの休憩所からスタートし最初に進む方向を右・右、右・左、左・左と決めると、二分探索を使えばどこでぶつかるかが分かるので、それぞれ計算していく。というコンテスト中に思いついた方針で解けた。
　結構実装が大変。コンテスト中は、方針は思いつけても実装する気力がなかった。

　……と思ったが、「二人は同じ休憩所からスタートする」ものだと思って解いていた。別な休憩所からスタートしてもOKだとACしてからツイッターを見て気付いた。
　同じ休憩所からスタートして良いというの、あんまり明らかに思えないので、正しく読解していたら解けなかったかも……。

C - Pivot

　自力ACしたが、大量にペナを出してしまった。

　「通常の状態」と「反転した状態」を分けて考え、それぞれの変化はgcdになりそう……といったあたりは結構すぐ思いついたので、それをきちんと詰めれば答えにたどりついたのだが。きちんと詰めるのがなかなか大変だった。

D - Halftree

　自力ACしたが、時間がかかってしまったのでコンテスト中解けた気がしないなぁ。

　Nが偶数のときは作れない。
　Nが奇数で、NとKのgcdが1のときは、Kおきに順番に繋いでいけばOK。

　それ以外のとき。右へいくと+1、下へいくと+Kすると考えると、縦をgcd、横をN/gcdとしたグリッドとみなすことができる。
　このグリッドが縦横ともに奇数なことを利用して、木を作っていく。

　3*3での木の作り方を考えて、それをコピーしていく……と考えた。3*3のマスで木を作る（「N」の文字におまけがついたようなやつにした）。
　これをそのままコピーするとサイクルができてしまうので、一番上の行の以外では一ヶ所辺を減らせばOK。

E - Xor Annihilation

　解説放送を見てAC。
　問題文の読解が困難だったけど、maspyさんのツイートで理解しました。

・ボールの重み全部のxorは0である
・累積xorを考える
・ボールが合体することは、累積xorの一項が消えることに対応する

　というところまで気付けると、解説のような立式ができる。

　一つ目、二つ目は考えたが、三つ目に気付けなかった。
　ただ実験するだけでなく、「累積xorを使うと何か上手い性質が見つかるのでは？」と予想して実験するのが大切か。
時刻: 0 件のコメント:
ラベル:

Codeforces Round #835 (Div. 4)

　全完。Fでミスして時間かかってしまったけど、それ以外は良し。

コンテスト後のツイート


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

2022年11月12日土曜日

大和証券プログラミングコンテスト2022 Autumn (AtCoder Beginner Contest 277)

　Eまで五完。

コンテスト後のツイート

F - Sorting a Matrix

　解説AC。

　行については、最小値・最大値を見てソートするのはOK。
　その後、列について考えるとき、ある行の二つの列で大小関係があるときに辺を張り、ループしたらダメ、としたい。が、辺の本数が多くなりそうで困っていた。

　こういうとき使うのが、超頂点を加える手法ですね。
　ただ、最近、この問題で使った方法とは超頂点の使い方が違うのが難しい。「同じ数字たちをまとめるために超頂点を使う」という手法はなじみがなかった。
　（とはいえ、超頂点を使うこと自体を考えなかったのはダメ）

　なお、答が一致した後もTLEを取るために苦戦した。

G - Random Walk to Millionaire

　解説放送を見てAC。

　Xの二乗とは何か？　と考えたとき、「どこでレベルアップしたか？」の組み合わせと考えてDPへ持ち込む。
　考え方は分かるのだけど、この問題でこの手法を使うとは。

　ただ、この問題ではDPくらいしかやりようがないし、DPを高速化しようと思ったらXの二乗というところを上手く使うしかない。そう思えば、この変形をするしかない、と考えるのは自然だとは思う。

　しかし、元々積で与えられているものを分けて考えるというのはピンと来なくて。難しい。
時刻: 0 件のコメント:
ラベル: , ,

2022年11月8日火曜日

AtCoder Beginner Contest 276

　Fまで。

コンテスト後のツイート

G - Count Sequences

　解説放送を見てAC。

　単調増加な数列の個数を二項係数で考えるのはコンテスト中にも考えたが、二項係数でどうにかしようと思ったとしても、その後の処理もなかなか技巧的で難しい。
　かといって形式的ベキ級数を使う方法もそんなに簡単には見えないため困る。でも、形式的ベキ級数で立式はできるようになっておきたい。
時刻: 0 件のコメント:
ラベル:

2022年11月6日日曜日

yukicoder contest 367

　Bまで二完。


No.2119 一般化百五減算

　順番に中国剰余定理を使っていけば良いのは分かったが、TLEが取れなかった。

　TLEの原因は、割る数が大きくなり過ぎることを忘れていたため。割られる数が大きくなったときをケアするだけなく、割る数の方が大きくなったときについてもきちんと調べなくてはいけなかった。

No.2120 場合の数の下８桁

　教育的な問題。やり方を全然覚えていなかった……。

　2ベキ、5ベキ、それ以外で分ける。
　2ベキや5ベキを除いた部分は、$2^8$や$5^8$をmodとしたとき可逆になっているため、オイラーのトーシェント関数を使えば「何乗すれば逆数になるか？」が分かる（なお、Pythonならpow(x,-1,mod)でOK）ので、計算可能。それぞれ計算し、中国剰余定理によって復元できる。
時刻: 0 件のコメント:
ラベル: ,

2022年11月2日水曜日

AtCoder Beginner Contest 275

　Fまで六完だが遅解きだった。

コンテスト後のツイート

G - Infinite Knapsack

　解説放送を見てAC。

　凸包を使うのが久しぶりだったので、自分の昔の提出に取りにいった。（ライブラリに入れます）
　ただ、凸包の線分の両方の頂点が、y=xに対して片側にある場合に計算してはいけないことに気付かず、誤差のせいか？　などと思ってWAを重ねてしまった。何を求めているかちゃんと考えないと。
時刻: 0 件のコメント:
ラベル: ,

2022年11月1日火曜日

Codeforces Round #819 (Div. 1 + Div. 2) and Grimoire of Code Annual Contest 2022

　Cまで三完。約20分遅れで書き終ったEはコンテスト後、ACしました。その後、剽窃が発覚しunratedに。

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


 D. Edge Split

　解説AC。
　これを飛ばす判断は間違ってなかったと思う。

　赤、青それぞれが連結な木になるよう色を塗れば良い、と思い、それをどう実装すれば良いか分からなかった。
　が、実際は連結性はいらなかった！　赤、青それぞれが森になっていればOK。

　実装はDFS木の性質を使うと良い。
　DFSで全域木をとって、残り三辺がサイクルになると困るが、DFS木の後退辺が親子関係にあるので、サイクルの一辺の色を変え、代わりに根へ付け替えれば良い。
　（という説明は、tatyamさんのツイートそのままです。これを思いつかないと実装で迷走しそう）
時刻: 0 件のコメント:
ラベル: ,

2022年10月30日日曜日

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

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

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

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

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以上の組があるとまずいのはほぼ明らかなので、数え上げの問題。
　どう数えるかで困っていたら、最大値に着目というツイートが目に入ったため解くことができた。
時刻: 0 件のコメント:
ラベル:

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へ行くべきでしたね。題意を理解するのにちょっと時間がかかる問題なので避けてしまったけど、ちゃんと検討すべきだったかなぁ。
時刻: 0 件のコメント:
ラベル:

2022年10月27日木曜日

AtCoder Regular Contest 148

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

コンテスト後のツイート

E - ≥ K

　解説放送を見てAC。

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

　今回は、

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

　というもの。

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

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で書こうとしたはずなので、もうちょっと慣れて、速く書けるようになりたい。
時刻: 0 件のコメント:
ラベル:

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を出してしまった（テストケースを見て気付いた）。気を付けねば。
時刻: 0 件のコメント:
ラベル:

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

　Eまで五完。

コンテスト後のツイート

F - Fishing

　一応、自力AC。

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

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

G - Security Camera 3

　解説放送を見てAC。

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

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

　また、グラフ構築の際、

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

　を考え、

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

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

　類題を解いておこうと思って、これを解いたが（一応、解説は見ないで解けたが）かなり苦戦した。フローのグラフ構築は難しい。
時刻: 0 件のコメント:
ラベル: , ,

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以下という制約から、それぞれの個数を持ちたいと思うのも自然ですね。
時刻: 0 件のコメント:
ラベル:

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配列が何かすぐに思い出せなかった。文字列アルゴリズムは適宜使えるようにしておきたい。
時刻: 0 件のコメント:
ラベル:

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だろう、と思っていると盲点になりやすいかもしれない。


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

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でも使っていたのだから、約数の関係を利用して同じようにすれば良かった。多少焦っていたにせよ、これくらいは気付きたかった。
時刻: 0 件のコメント:
ラベル:

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を質問するのは意味が変わらない、ということには早く気付くべきだった。そうすれば、三等分するという方針には早くたどり着けたと思う。（が、三等分してからも難しい。コンテスト中も三等分することは一応考えたけど、その後が思いつけていないので……）

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

2022年10月15日土曜日

yukicoder contest 364 (Do you know Cherry Contest?)

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

コンテスト後のツイート

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

　解説AC。

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

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

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

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

　なお、PyPyだと（意外と）制限時間が厳しく、セグ木の関数で内包表記を使っているとTLEが取れなかった。PyPyだと内包表記が遅いのには注意。
時刻: 0 件のコメント:
ラベル: , ,

2022年10月14日金曜日

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

 　ABCEFの五完。

コンテスト後のツイート



 G - Random Student ID

　解説放送を見てAC。

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

Ex - Taboo

　解説放送を見てAC。

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


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

Codeforces Round #827 (Div. 4)

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

コンテスト後のツイート




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

2022年10月13日木曜日

AtCoder Regular Contest 149

　Cまで三完。

コンテスト後のツイート


D - Simultaneous Sugoroku

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

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

　の二つがポイント。

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

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

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

2022年10月12日水曜日

yukicoder contest 341

　ABの二完。


No.1917 LCMST

　解説AC。

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

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

　と考えるのが重要。

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

　難しいけど、多分こうだろうな、という考察を推し進めていけば思いつけない問題ではなかった。
時刻: 0 件のコメント:
ラベル:

2022年10月11日火曜日

Codeforces Round #825 (Div. 2)

　Cまで三完。

D. Equal Binary Subsequences

　解放ツイートを見てAC。

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

　二個ずつ同じ文字にするためには、別の文字であるペアから、010101……となるものを選んでrotateさせれば良い。
時刻: 0 件のコメント:
ラベル:

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を使うと答えが得られる。

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

2022年10月9日日曜日

AtCoder Regular Contest 150

　Cまで三完。

コンテスト後のツイート

D - Removing Gacha

　解説AC。

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



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

2022年10月8日土曜日

Dytechlab Cup 2022

　Dまで四完。

コンテスト後のツイート

E. Ela Goes Hiking

　解説AC。

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

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

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

　こと。

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

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

2022年10月4日火曜日

yukicoder contest 313

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


No.1677 mæx

　（今更だが）自力AC。

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

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

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$が必要（右辺も同様）と分かった。

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


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

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

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

2022年9月26日月曜日

yukicoder contest 361

　B一完。


No.2078 魔抜けなパープル

　解説AC。

　魔法を使う回数で全探索というのを本当に思いつけなかった。kの魔法とk+1の魔法を使うとき～とかは考えたのに……。
　

No.2080 Simple Nim Query

　一番右端の1個じゃないindexを調べればいいよね？　と出したけどWA。
　結局、解法はあってて、全部1のときの答えを逆にしていたのでした。一番最初に書いたところなので、そこが間違っているとは思わなかった……。
時刻: 0 件のコメント:
ラベル:

2022年9月25日日曜日

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

　Eまで五完。

コンテスト後のツイート

F - Transportation

　解説AC。

　最小全域木を作る問題なので、クラスカル法かをプリム法を使うしかない。（一応、他にブルーフカ法というのもあるが、あまり使わない）
　空港・港とあるが、それぞれを使う・使わないで四種類ありそう。

　コンテスト中、ここまで考えて、止まってしまった。

　あとは、「超頂点を作って空港や港を処理する」というのを思いつかなくてはいけない。見たことないなら仕方ないが、何問も類題を解いているのに思いつかないのはまずい。
　ただ、超頂点を作る、という手法を思いつかずに問題を落としていることは結構多い気がする。自分の苦手な方法なのかもしれないので、気を付けよう。

　なお、PyPyだと制限時間がきつい。毎回グラフを構築していると間に合わないため苦労した。

G - Sequence in mod P

　解説放送を見てAC。

　B=0ならBaby-Step Giant-Step法が使えるので、それを応用できないか、と考えると大体そのまま解ける。Baby-Step Giant-Step法をよく覚えていなかったのは問題だけど、まあ平方分割ですね。
　ACするためには、A=1やA=0の場合をケアしないといけない。
時刻: 0 件のコメント:
ラベル: , ,

2022年9月24日土曜日

Codeforces Round #822 (Div. 2)

  Cまで三完。


D. Slime Escape

　コンテスト中は主に区間DPを考えていて解けなかった。
　コンテスト後、解説を読んでもよく分からなかったけど、ちゃんと整理したらACできた。

　左右どちらに進むにせよ、得できるなら得をしたい。
　ので、累積和と、累積minを考え、累積和がプラスになった箇所について、「いくつ以上のHPがあれば得できるか」を調べる。

　それを貪欲に取っていけば良い。

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

2022年9月22日木曜日

UNICORNプログラミングコンテスト2022(AtCoder Beginner Contest 269)

　Fまで六完。

コンテスト後のツイート

G - Reversible Cards 2

　解説放送を見てAC。なるほど、という感じ。

　コンテスト中、表と裏の総和がMという条件を使うのだろう、とは考えたが、二乗のDP解も、種類数がルートで抑えられるというのも分かっていなかった。
　後者はともかく、前者のDP解法が見えなかったのはまずい（二乗DPが思い浮かべば、それを高速化しよう、ということで後者が見えるかもしれない）。まず、計算量が悪くても解ける方法がないかを考えなくてはいけなかった。


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

2022年9月19日月曜日

Kick Start Round F 2022

　全完できたが苦労した。実装大変でした。

コンテスト後のツイート


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

2022年9月17日土曜日

yukicoder contest 360

　A一完。Bが分からなかった。

No.2071 Shift and OR

　解説AC。

　コンテスト中、Nが16以上なら答えが$2^16-1$になることにはすぐ気付いたが、その後が分からなかった。正当性のない、maxを持つbit DPを（コンテスト後に）投げてWA。

　正しい解法は、もっとシンプルに、A[0]からA[i]までで、何の数字が作れるかを持つDP。遷移先が高々16個なのでこれで計算量も間に合う。
　言われてみればこれで良いけど、気付きにくい気がする。

No.2072 Anatomy

　自力AC。

　後ろから見てUnion-find……と、すぐ思ったのだが、なぜかそれで上手くいかない気がして時間がかかってしまった。

No.2073 Concon Substrings (Swap Version)

　一応自力AC。

　indexを3で割った余りについて、c, o, nの個数を考えるのは良い。ただ、その個数だけ見たのでは作れない場合がありそう？　というのがこの問題の胆。
　どういうとき作れないか分からず戸惑ったが、答えがNになるのは、concon...と並ぶときだけだと気付いた。他の場合が作れることが分からないままACしたが、冷静に考えれば当たり前か。

No.2074 Product is Square ?

　解説AC。

　Nの二乗が通る制約なのでそれを利用できないか、と考えるべきでした。
時刻: 0 件のコメント:
ラベル:

2022年9月13日火曜日

Codeforces Round #820 (Div. 3)

　実装が大変な回だった。なんとか全完。

コンテスト後のツイート


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

2022年9月3日土曜日

freee プログラミングコンテスト2022（AtCoder Beginner Contest 264）

　Fまで六完。

コンテスト後のツイート

G - String Fair

　解説放送を見てAC。

・後ろ二文字を持ってDP

　という方針を思い付けたなら、グラフの問題（最短経路問題）となり、負辺があるのでベルマンフォードを使って解くことができる。

Ex - Perfect Binary Tree

　解説放送を見てAC。

　ただのDPなのだが、遷移式を立てるのに非常に苦労した。特に工夫する方法もなさそうなので、落ち着いて、整理して考えるしかない。
時刻: 0 件のコメント:
ラベル: ,

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 件のコメント:
ラベル:

2022年7月31日日曜日

AtCoder Regular Contest 145

　Cまで三完。

　ARCは初手で実験することが多いのに、実験しなかったために失敗したのは良くなかった。Cは実験しなくても解けそうな気がしたため最初しばらく実験せず。Dは実験して良い性質が得られると思わなかった。

コンテスト後のツイート

D - Non Arithmetic Progression Set

　解説AC。
　良い整数集合を構築した後、最後の一個で調整する方法で解いた。

　初手で、貪欲にSを構築（実験）→oeisしてみる、もしくは、検索してみるべきだった。そうすれば、Sがどんな性質を持つかは分かったはず。（残り時間は30分ほどあったので、そうやって考える時間は残っていた）
　ACできたかは分からないが、実験もせずに終わったのはダメ。反省。
時刻: 0 件のコメント:
ラベル:

2022年7月30日土曜日

yukicoder contest 354 （オムニバス

　Cまで三完。


No.2024 Xer

　解説AC。

　Aをソートして、それが条件を満たすかどうか、だとサンプル4が合わない。

　ただ、このように必要条件で絞る方針は間違っていなかった。
　何でソートすれば良いかは、与えられた不等式から考えるか、実験して考えるか、くらいか。どちらにせよ思いつくのは不可能ではなさそう。時間があれば試さなくてはいけない解法でした。
時刻: 0 件のコメント:
ラベル:

2022年7月28日木曜日

AtCoder Beginner Contest 261

　Gを除く七完。

コンテスト後のツイート

G - Replace

　解説放送を見てAC。

　難しい。
　TからSに戻すと考えると区間DPにできるということが気付きづらいし、それだけだと一文字同士の処理で上手くいかないというのも気付きにくい。
　また、計算量が五乗になるのにTLEにならないというのも意外に感じた。

　一つ一つの考え方自体は難しくないのは確かなのだけど、ACした後でも簡単という気がしない。
　単純なDPでも、DPにもつ配列が二乗、三乗……となると途端に難しくなるから、こうやってちょっと複雑なことが組み合わさるとなかなか整理しづらくなるのが厳しい。
時刻: 0 件のコメント:
ラベル:

2022年7月25日月曜日

yukicoder contest 353 （オムニバス）

　Cまで三完。D、解説読んでも難しい気がしたけど、こんなに解かれるんだなぁ。


No.2017 Mod7 Parade

　解説AC。

　まず、10^x mod 7が6周期だということを押さえておく。そして、mod 7を考えるので、各数字のmod 7も高々7個。

　これを利用して、

・DP[i][j]で、桁数 mod 6がi個、答え mod 7がjとなるものの個数

　というDPを考える。
　下の桁から追加していくとき、その数字を追加するか、しないか、で遷移は二通り。なので、計算量も抑えられている。
　なお、上の桁からやると桁数を覚えなくても解け、計算量も下がる（というツイートを発見）。確かに！

No.2018 X-Y-X

　解説AC。

　かなり賢い解法に思えるが、隣接要素のxor（差）を考えるのは定石の一つだし、そうして帰着した問題を見ると、偶奇で分けて片方反転させるのも定石。
　迷うのは仕方ないけれど、色々試している間に解けるべきだった。

No.2019 Digits Filling for All Substrings

　これは自力でACできた。
　mod 3でDPすればOK。

　No.2017 Mod7 Paradeと似た解法だけど、こっちの方が大分思いつきやすく感じた。コンテストの問題順が、No.2019 Digits Filling for All Substrings→No.2017 Mod7 Paradeとなっていたら、似た解法の応用問題が後に出題されている、という感じで良かったと思うけれど、全体テスターがいないから仕方ないね。


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

2022年7月23日土曜日

Codeforces Round #808 (Div. 1)

　A一完で終了。Aはまあまあ早かったのだが。

コンテスト後のツイート

B. Difference Array

　解法ツイートを見てAC。

　sum(a_n)に関する制約があるのが怪しい。それを利用できないか考える。
　実際に操作をしてみると、すぐ、大半の要素が0になるのは分かる。ので、0の個数を管理して、他は愚直に操作すればOK。

・大半が0になること
・こういう問題では上手い方法はなくて、基本的には真面目に操作を行うしかなさそうなこと

　には気付いていたのに、解法へたどりつかなかったのは良くない。ただ、解法の鍵となる部分は分かっていたので、それ以上反省するのも難しい……。

C. DFS Trees

　解説AC。

　まず、ツイートした解法は間違っていました。問題で与えられたアルゴリズムを勘違いしていました（重みではなく、indexの小さい方からdfsするかと思っていた）。

　これを踏まえると、「MSTに入らないedge x-yについて、xとyの間にあるような頂点はダメ」だけでOK。これをどう実装するかが問題。

　これは、木上のimos法で解ける、という解法ツイートを見て、以下のようにできると分かりました。子孫全てにある値を足す、というのをimos法を使って処理しています。

・頂点xとyのLCAがxでもyでもないとき、xの子孫、およびyの子孫に+1する。
・頂点xとyのLCAがxのとき、yの子孫に+1、xの子でyの先祖であるような頂点kの子孫に-1する。頂点kはダブリングを使えば求まる。

　一つ目の方法では、答え(findMST(i)=1となる)の候補となる頂点に+1しており、二つ目の方法では、答えにならない頂点に-1しています。ので、全て処理した後、値がmaxと一致している頂点たちがこの答えになります。


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

2022年7月22日金曜日

Codeforces Round #807 (Div. 2)

　遅れて参加してDまで。

コンテスト後のツイート

E. Mark and Professor Koro

　解説は理解したけど、PyPyではTLEが取れず。（一人ACしている人がいるけど、どうやっているのかよく分からない）

　結局、遅延セグ木を使って筆算の繰り上がりをシミュレートする問題になる。
　ただ、1が立っている最上位の桁などを二分探索で求めなくてはいけない。この辺、セグ木上の二分探索をちゃんと実装していればlog一個になるのだろうけど、自分の提出はlog二個のままです。（遅延セグ木の二分探索は、実装したことはあるけれどライブラリ化していなかった）
　log一個に直したら通る可能性はあるけど、他の提出が通っていないのを見ると、実装する気になれません……。
時刻: 0 件のコメント:
ラベル:

2022年7月20日水曜日

AtCoder Beginner Contest 260

　Eまで五完。

コンテスト後のツイート

F - Find 4-cycle

　解法ツイートを見てAC。

　Tが3000以下というのが怪しい。これをどう使うか、という問題。
　コンテスト中は、Tの二重ループでどうにかすることしか考えなかった。が、鳩ノ巣原理を使うならTの組に対して何かを割り当てることになる。

　その両面を検討しなくてはいけなかった。

G - Scalene Triangle Area

　自力AC。

　imos法を頑張る、としか言いようがない！
　斜めにimos法をしたり、その斜めの累積和を途中で切り上げたりするのを書かなければならず混乱するけれど、頑張るしかない。
時刻: 0 件のコメント:
ラベル: ,

2022年7月19日火曜日

AtCoder Regular Contest 144

　Cまで三完だが、遅かったためレートを下げた。解いている最中はそれほど遅い気がしなかったのに、順位は悪かったので、（自分では分からなかったが）体調が悪かったのかもしれない。

コンテスト後のツイート

D - AND OR Equation

　解説ACだが、今見返すとチャンスはあった。

　実験してoeis（これやこれなどが出てくる）と見比べれば${(1+x)}^N/{(1-x)}^{(N+2)}$の$K$次の係数と分かる。

・${(1+x)}^N$は、二項定理を使って展開
・${(1-x)}^{(N+2)}$は、$1/(1-x)=1+x+x^2+x^3+...$とできることを利用すると重複組み合わせにより二項係数になる

　を利用すれば求められる。
　ただし、二項係数を求めるとき、Kが998244353に近い値のときは気をつけて計算しなくてはいけない。（コンテスト中に、ここの処理まで上手くできた可能性はかなり低そう……）

　コンテスト中、形式的冪級数で表すところまではできていて、その後は多少技巧的ではあるが自分で思いつける変形だった。
　特に一番目、二項定理を使おうとも考えなかったのはひどい。形式的冪級数を使うならここは押さえねば。
時刻: 0 件のコメント:
ラベル: ,

2022年7月16日土曜日

yukicoder contest 352

　A一完。睡魔に襲われたせいでB以降あまり考えられなかったけど、眠くなかったとしてもBが解けたかどうかかなり疑問。 


No.2008 Super Worker

　解法ツイートを見てAC。

　まあ、何かでソートするんだろうな、とは考える。
　何でソートするか調べるために立式するのだが、そのとき、次にする二つのアルバイトを比較するのが重要。3項以上の和を考えるのではなく、次の二項の順番を違えた場合の式を比較する。そうすれば何でソートすれば良いか分かる。

　二項での比較でそうなるのは分かったけど、どうして三項以上でもソート順でいいのか？　というのがしばらく分からなかった。けどこれは、二項ごとに隣接swapを繰り返すとソート列が作れるというのと同じ理屈ですね。
時刻: 0 件のコメント:
ラベル:

2022年7月13日水曜日

AtCoder Beginner Contest 259

 　Fまで六完。

コンテスト後のツイート

G - Grid Card Game

　解説AC。（解説放送も見た）

　コンテスト中、いわゆる「燃やす埋める問題」ではないかと疑ったりもしたのだが、違うと思ってしまった。

・start→行のノードたち→列のノードたち→ゴール

　みたいなグラフを考えていたのだけど、

・start→行および列のノードたち→ゴール

　を考えるのが正解。「燃やす埋める問題」を思ったなら、そういうグラフを考えるのは当然なはずなのに、捨ててしまったのはまずい。
　こういうグラフ構築と、「燃やす埋める問題」では「Xを選択してYを選択しない場合のペナルティ」を見ていく、という点は頭に入れておきたい。

　その後の処理もテクニカルだけど、この系統の問題になれていれば突飛な考え方ではない気がする。類題経験を積んだ方が良さそう。

Ex - Yet Another Path Counting

　解説放送を見てAC。

　二通りの四乗の解法がある：

・同じラベルの二点全てについて二項係数を足す
・多点スタートのDPをする

　各ラベルの個数によりこれらを使い分けることで三乗になり、ACできる。
　コンテスト中は一番目の方法しか思いつけなかった。二つ目も見たことあったのに。
時刻: 0 件のコメント:
ラベル: ,
登録: 投稿 (Atom)