総合内科専門医受験記録

総合内科専門医の受験を記録します

Atcoder、厳しい

Atcoder problemsで下から解いてっていま茶色真ん中ぐらいの問題埋めてるんだけど、時々詰まる問題出てきて、解説ACしなきゃいけないようなことが増えてきた。
知識が足りてなくて解けないならまだいいんだけど、手元にあるアルゴリズムで解けてないのはまずい。
このまえのABC337も惨敗だし。うーん。水色は無理か？

ARC167-A - Toasts for Breakfast Party

atcoder.jp


これで灰色diffとはほんまARCは魔境ですわ。

まずAをsortして、N個の配列から(N-M)のペアを適当に選ぶ。そうするとN-M個のペアと、N-2*(N-M)=2M-N個のソロができる。合わせてM個。それを皿にのせる。
そのうちの2つのペアの組み合わせはAa≦Ab≦Ac≦Adとしたときに
① (Aa+Ab)^2+(Ac+Ad)^2
② (Aa+Ac)^2+(Ab+Ad)^2
③ (Aa+Ad)^2+(Ab+Ac)^2
の3通りが有る。①-③と②-③の不等式評価をするとこの3つの組み合わせで③がもっともアンバランス度が低い組み合わせとなる。

これをすべてのペアについて検討して、すべての2ペアを③のように組み替えると、一番値の小さいのと、一番大きいもののペア、2番目に小さいのと、2番めに大きいもののペアというような組み合わせが最適となる。
で、あとはN-Mのペアの選び方だが、配列Aにおいて右側にソロが固まるように、ペアのやつらは左側に固まるようにするのが一番値が小さくなる。（これはほぼ自明でいいと思うが、ちゃんとやるなら一つのペアと一つのソロを見て、ソロを一番大きなやつに割り振ると一番アンバランス度が減るのを確認する）

なので最適解は左から1と2N-2M番目、2と2N-2M-1番目・・・N-MとN-M+1番目のペアと、2M-2M+1、2M-2M+2・・・Nのソロをそれぞれ二乗したものが答え。


これ直感で多分そういう組み合わせが一番小さいとはおもうけれど、きっちり証明するのは絶対に灰diffじゃないと思う

緑コーダーになった＋1000AC達成

コンテスト自体はうまくいかんかったけど、比較的にタイム早くて3完で緑タッチできた。

2月に始めるときにまあ緑ぐらいまではいけるだろうとは思ってたけど、ちょっと実力的にこの辺りで停滞しちまったな。
動的計画法やグラフの勉強全然してないもんな。
1000AC達成したのも虚無埋め。
虚無埋めはプログラム慣れてない俺には意味のある訓練だった。800ACぐらいからめんどくさくなって基本入力を範囲for文、出力を3項演算子で書くようになった変化があった。

まだ通せてない問題の解説は聞けば理解できている部分もあるし、アルゴリズムで勉強する部分が残っているから水色は行けるんじゃないかと期待はしてるんだが、そんな甘くないかも。
まあもうちょっと頑張ります。。

競プロってなんでWSL環境でやってんの？

evimalabの人がとてもわかり易い環境構築の動画を出してたから俺もWSL2に切り替えてみた。
www.youtube.com

ただ、WindowsでMinGWでコンパイルしてたときと一体何が違うのかがわからん。
まあ長いものにはまかれろの精神で、いったんこれでやってみるか。。

「小谷の蟻の問題」を解く

小谷の蟻の問題というのがある。
ja.wikipedia.org

要は1x1x2cmの直方体の角からアリが表面を歩いたときに、一番遠い場所はどこか？という問題だ。
これが点対称の角が答えでないから面白い。

これの解法をいくつか見たんだが、なんかピンと来ないので、座標ゴリ押しで解いた俺の解法を載せておく。
以下直方体は下のようにA~Hを定義し、アリはAにいるものとする。

■なぜGが最も遠い場所でないのか
答えの点が面EFGHのどこかにあるのは自明だろう。（側面のある点と仮定するならその直上の辺EFGHと交わる点が更に遠いので矛盾）
このとき、最短距離の候補が２種類有る点がキモである。
具体的に言えば、下図において左と右で長さが違うということだ。

図の三角が点Gにある場合は左ではAG=√10、右ではAG=√8となるため、点Gの場合、最短距離は右図のような長方形を２回通るパターンが最短となる。

この三角を点Xとしたときに、確かに左図においてはAXよりAGの方が長いだろう。だが、実際にはAGの最短距離は右図なのであって、右図においては一概にどっちが長いかは言えないのである。そしてこの場合、AXの最短距離は左図なのか、右図なのかを場合分けする必要もある。

■解法
大筋の骨格としては
1.ある点Xにおいて、最短距離の候補を列挙し、その中で最も最短な経路を選ぶ
2.各最短経路がとれる領域において、その長さが最も長くなるものを選ぶ。
とする。
点Aを原点として、展開図をXY座標に展開する。

上記展開図では正方形EFGHは辺EFで接しているが、当然展開する前はFG,GH,EHで接しており、それぞれがその最短経路を持つ。なのでその4パターンをすべて合成した画像が下記である。

面EFGH上に点EからF方向にa,H方向にb離れた点をXとする。（0≦a≦1, 0≦b≦1）

先程の図にXの点を図示すると、下記の4点が最短距離の候補となる。それぞれX1,X2,X3,X4（黒点）とし、Aとの距離をD1,D2,D3,D4（緑線）と置く。このとき、Xの座標は、
X1(-b,2+a),X2(a,2+b),X3(-1-a,3-b),X4(1+b,3-a)となる。

しかし、上の図は恣意的であり、AFとEHの交点をM,AHとEFの交点をNとしたときに、X4が⊿EFM内、X3が⊿HEN内（下図灰色）の場合は辺FGまたは辺GHと交差しないため、X4、またはX3、その両方が存在しない場合があることに留意する。

それを点Xの領域として図示すると下記の様になる。


それぞれ4点の最短距離は
D1^2 = (a+2)^2+b^2 = a^2+4a+b^2+4
D2^2= a^2+(b+2)^2 = a^2+b^2+4b+4
D3^2=(a+1)^2+(b-3)^2 = a^2+2a+b^2-6b+10
D4^2=(a-3)^2+(b+1)^2 = a^2-6a+b^2+2b+10であるので、その大小関係は

D1<D2　⇔　4a<4b　⇔　a<b
D1<D3　⇔　4a+4<2a-6b+10　⇔　6b<-2a+6　⇔　b<-a/3+1
D1<D4　⇔　10a-6<2b　⇔　5a-3<b
D2<D3　⇔　4b+4<2a-6b+10　⇔　10b<2a+6　⇔　b<a/5+3/5
D2<D4　⇔　2b<6-6a　⇔　b<-3a+3
D3<D4　⇔　2a-6b<-6a+2b　⇔ 　a<b

となるため、例えばD1が最短距離となる条件はD1<D2かつD1<D3かつD1<D4を満たすa,bの領域である。D2～D4においても同様。
それを図示したものが下記。

よって点Xの場所によって４つの最短経路候補のうち最も短くなる経路が判明したので、その範囲の中で最も最大となる値を探す。
例えばD1^2はD1^2= (a+2)^2+b^2 の式から(a,b)=(-2,0)を中心とする円であることがわかる。点X1は上図ab座標平面の①の部分のみ動ける。よってその最大は図からa=3/4,b=3/4のときであることは明らか。
D2^2も(a,b)=(0,-2)を中心とする円であり、D2^2を最大化するa,bはa=3/4,b=3/4である。
D3^2は(a,b)=(-1,3)を中心とする円であり、D1,D2ほど自明ではないが、(a,b)=(1,1)と(-1,3)がなす直線は傾き-1であることからD3を大きくしていったときに(a,b)=(1,1)でb=aと接するので、これもa=3/4,b=3/4で最大化する。D4においてもD3と同様。

以上より、各最短経路において最大の値を取るのはいずれにおいてもa=3/4,b=3/4のときであり、その値は、D^2=(11/4)^2+(3/4)^2=130/16=65/8、D=√130/4の時である。

よって答えは、平面EFGHにおいて、点EからF方向に0.75進み、H方向に0.75進んだ点である。