Cでカスみたいなやらかしをして80分溶かした...
AB2完。Cは解説AC。
A - Vasya and Triangle
AGC036-Aを思い出したが自力で解くことにした。三角形の座標から面積を求める公式に従って考えて既約としたときに分母を にできなければ不可能というのは分かって、 [tez:2] の時は分子を
で割った商と余りを管理して頑張った。実装がちょっと重たい。
B - Vasya and Good Sequences
立っているbit数の和が偶数以外にもどれかが過半数を占めないというのになかなか気づかなかった。反省。
C - Putting Boxes Together
として考えると
つに揃える問題になる。あと、座標
に重さ
のが
個あるとすると真ん中のが存在するところに揃えたくて、個数をセグ木に乗せて頑張ればいい。
揃える場所を決めればそれより左と右に分けて座標の総和が分かればいいので個数と総和を持つセグ木でいい。
というのはすぐ思いついたが、右端に揃えるのが最適となる場合の処理が甘かった。大反省。
僕は言語学の知識はないので参考となるものはなにもありません。
去年適当にやって銀取れたので今年もやるかみたいなノリで申し込む。前日ぐらいにJOLの存在を思い出し、JOL2020-1のアラビア語を解く。普通に難しくて今年はまずいな...と思うなど。
とりあえず問題を全部見る。どうみても難化している気がしてまずいぞとなる。
大問1を軽く考える。おそらく大きい記号で子音、小さい記号(>)で母音を示しているようなのだが、>が上の文字にかかっているか下の文字にかかっているかすらわからない。5分ほど考えても進展がないので飛ばす。
大問2を見る。接頭辞を前につけるのかなと思ったがmaeがmemaeになるとか書いてるし1個ある間違いもそれっぽそうなのがない。仕方ないので飛ばす。
大問3を見る。いつものみたいな感じなのでしばらくはここに粘着することを決める。ある程度は理解できたが動詞の語尾に関する規則がさっぱり見えず、和訳は部分点があるっぽいので穴埋めできるところだけを埋める。ここら辺で45分とか50分とか経っていて流石に焦る。大問4と5に軽く手をつけるもサッパリなので大問1に思い切って戻る。
戻ってしばらく考える。母音の数と文字数が一致していることを思い出し、6,7とa,cが対応するだろうとなる。ここでどっちがどっちだろうと考えていたが、唐突に下から見る発想が思い浮かび、それに沿って考えるとうまくいった。8,10とh,iの決定で少し迷った覚えがある。文字が似すぎていて同じか違うのかわかりにくかった。(vみたいなやつとか)
そのノリで大問2を考える。まあ母音子音が大事だろうというノリで母子と対応付けるとうまくいった。この2問は初見はサッパリだったが戻ってきたら天啓が降ってきてびっくりした。
大問4を見る。Xの定義中にXを使う再帰的な定義はやめろ。ざっと眺めて気づいたのはmwanacheがおそらく子供を意味していそうということ。jua AでAのみたいな感じだろうとあたりがつく。しょうがないのでそれに沿って埋めてみる。埋め終わった後にamao/akwelumeとacimweni/cemwaliの違いってなんだとなるとvandu/vakongweが相違点だなあとなり、おそらく性別を意味してるのではとなる。その辺をまとめて書いた。理解しきれてないので抜けはさすがにありそう。
大問3は適当にそれっぽく見えたのをまとめた。言語Ⅲへの訳は捨て。
大問5も同じ感じ。nran使いすぎだろどうなってるんだあれ。
今年は厳しいなあと思いつつTwitterを見る。みんな難化していたといって安心。
面接対象も怪しいかなと思ったら入っていて一安心。去年と同じで面接の問題は簡単でよかった。
CodeforcesのGood Bye 2021に深夜出たらレートが99吹き飛んだ。競プロできません...
しかもEはs<tなら0にするところをs<=tにしていた、最悪。
APLOに出れるので一安心。無精進では銀が限界ですね。
#556 を走った。Bが重たかったなあ。
AB2完。Cは解説AC。
A - Prefix Sum Primes
以上の偶数は見なくていいから途中は
をいっぱい並べたいという発想になって
の個数で最初と最後に持ってくる数を場合分けしようとか思ったけど、途中で
を最初に置いて後は
を全部やって、
を全部やるみたいなのが実装楽だと気付けた。
B - Three Religions
制約の You can assume that no religion will have description longer than 250 characters. が露骨にヒントっぽいので 乗のDPを考えると
で作りたい文字列の前からそれぞれ
文字目までを取るのにindexは最適でどれだけいるかみたいなのが思いついた。
遷移を書くのが少し面倒だった。
C - Tree Generator™
これ面白かった。木の 間の距離って
なのはそうで、
は括弧列の部分和
で簡単に求められるのだが、
は
間に対応する括弧列の区間で最小となるものに一致するというのが思いつかなかった。
これが分かればセグ木に今の深さ、 として
そして
を乗せればいい。
を書くのが面倒だった。
今回は #485 を走った。C,Dが割と辛かった。
codeforces.com
AB2完。C,D,Eは解説AC。
A - Fair
制約の が露骨にヒントっぽいので多始点BFSを
回すれば通った。
B - Petr and Permutations
転倒数の偶奇とswap数の偶奇は一致するというよくある典型。 を
で2secで出すの、少し攻めすぎじゃない？
C - AND Graph
これ面白い。 なら
が
の否定
に包含されてる (
)という言い換えすら思いつかなかったのは反省。
個の頂点集合
と
個の頂点集合
を用意して
から
への有向辺を張って、
から
に
が
から
bit削ってできるなら有向辺を張って、
から
への有向辺を張ると、
から
へのパスがあることが
と同値になる。
で、 は交換則があるので、逆方向のパスも存在するっていうこと。なので、後はDFSなりBFSをすればいい。
のだが、グラフを陽に持つとMLEするので陰に持ちつつDFS内部で次に行ける頂点を探す必要がある。 にしてほしい。
D - Perfect Encoding
問題文の読解が難しい。要約すると
数列
に対し、
とする。
を満たす
のうち
が最小となるものについて
とりあえず最適な を考えると、
以上があるなら半分ごとに分割して損はないし、
が
つ以上あるなら
を
にしても損はしないので、最適解は
を
つ以下で、残りは
という形。
なので、 を満たす最小の整数
を求める問題を
回解けばいいのだが、
が
桁あるのが難しい。多倍長の掛け算は畳み込みで
でできるので二分探索+繰り返し二乗法で頑張ったのだがTLE。
結論としては、桁数を とすると
が
の前後になるので、ここの間だけ全探索すればよいという。これでもTLEしたが、原因は数を
進数で考えていたからだった。
進数で考えるすなわち
桁をまとめて畳み込みすると定数倍高速化が効く。
それにしてもきつかった。制約とTLが厳しい。
E - Prince's Problem
とりあえず素数ごとに分離する。LCAを考えるとパスの端点を の場合に帰着できる。オイラーツアーの順にセグ木に乗せるテクを使うと数列の範囲に対して
を取った場合の総和を求める問題になる。
ここで悩んでいたが、数列の値は の次数なので合計が
になる。これを利用して
以上のやつに加算して
との
はただの範囲和として求める。
以上のやつに加算して
との
はただの範囲和として求める。というのを繰り返せばよいとなって面白かった。
問題:
△ABCの内接円に対して辺BC,CA,ABのそれぞれ点D,E,Fが接している。
BC=a,CA=b,AB=c,s=(a+b+c)/2としたとき、AE=AF=s-a,BF=BD=s-b,CD=CE=s-cを示せ。
解答:
AF=x,BD=y,CE=zとしたときy+z=a,x+z=b,x+y=cが成立
これらを足し合わせてx+y+z=s
よってx=s-y-z=s-a
同様にy=s-b,z=s-cもいえるので題意は示された
問題:
点I'を△ABCのBとCの外角二等分線の交点とする。
このとき、I'は辺BCと辺ABのBからの延長上と辺ACのCからの延長上の全てに接する円の中心であることを示せ。
また、A,I,I'は同一直線上にあることを示せ。(点Iは△ABCの内心とする)
解答:
I'からBCに下した垂線の足をXとする
BX=BB'となるような点B'を辺ABのBからの延長上に取り同様に点C'も取る
この時△B'BI'と△XBI'はBB'=BX,BI'=BI',∠B'BI'=∠XBI'より合同であるのでB'I'=XI'
同様にC'I'=XI'がいえるのでこれらより点I'を中心として半径がXI'であるような円は条件を満たす
この円をωとする
直線AB',AC'はωの接線であるので∠B'AI'=∠C'AI'
よってI'は∠BACの二等分線上
Iは△ABCの内心より∠BACの二等分線上であるので示された
問題:
△ABCの内接円の半径をr,辺BCについてAと反対側にある△ABCの傍接円の半径をr'とする。
またBC=a,CA=b,AB=c,s=(a+b+c)/2とする。
r'=r*s/(s-a)を示せ。
解答:
Aと反対側にある△ABCの傍接円をωとする
ωの中心をI'とし、ωは直線ABにB'で接するとする
また△ABCの内心をIとし、△ABCの内接円は辺ABと点Fで接するとする
このとき△AFI,△AB'I'は∠AFI=∠AB'I'(=90°),∠FAI=∠B'AI'より相似
よってFI:B'I'=AF:AB'=(s-a):sであるのでB'I'=FI*s/(s-a)
B'I'=r',FI=rよりr'=r*s/(s-a)であるので示された
