ARC029-B「高橋君と禁断の書」と、GitHubの練習

シェアする

  • このエントリーをはてなブックマークに追加

こんにちは、お久しぶりです。

最近は就職活動とアニメ視聴とプログラミングで忙しい日々を過ごしております。

今期アニメはまだ数作品しか見ていませんが、「亜人ちゃんは語りたい」「政宗くんのリベンジ」「風夏」はとりあえず視聴継続です。はやみんの少年声いいですね。

あと、「AKIBA'S TRIP」はイヤホンズがタイアップしているアニメということで、内容如何にかかわらず、しばらくは視聴確定です。

さて、最近、エントリーシートでアカウントの提出を求められたことから、GitHubというものを始めてみました。

バージョン管理するような公開ソフトウェアは作っていないので、活用できるかは不明ですが、使い慣れるために少しづつ活用していこうと思います。

ということで、とりあえず練習として、AtCoder(プログラミングコンテストのサイト)で提出したコードの管理を行おうかと思います。

ついでにブログへの埋め込みと解説・感想記事の作成も。

手始めに、解説スライドと異なる解法でACした問題について自分の解法を紹介したいと思います。

ARC029-B「高橋君と禁断の書」

この問題は、箱を表す長方形の中にノートを表す長方形が収まるかどうかを判定する問題です。

ARC029-B「高橋君と禁断の書」

入力例の箱3のように、斜めにしないと入らない場合の判定に頭を使います。

縦・横で入る場合は(min(a, b) <= min(c, d) && max(a, b) <= max(c, d))で判定できます。

また、斜めにしても明らかに入らない場合を(min(a, b) > min(c, d) || a*a + b*b > c*c + d*d)で判定しておきます。

短い辺を比べたときに、ノートよりも箱の方が短い場合は、必ず入りません(ノートの短辺を直径とする円が箱に収まる必要があるため)。

また、対角線を比べたときに、ノートよりも箱の方が短い場合も、必ず入りません(ノートの対角線が箱に収まる必要があるため)。

これらの場合を除いたとき、次のような図を考えることで、判定ができます。

箱の中心(対角線の交点)を中心とし、ノートの対角線の長さを直径とする円を書きます。このとき、必ず円と箱の枠は右上部分で2回交わります。

このとき、図の青い角と赤い角に対して「赤<青」が成り立っていれば、ノートは箱に収まります。

したがって、角1と、青い角=90°-角2-角3を比べれば判定できます。

これを実装したのが下のソースコードになります(th1, th2, th3はそれぞれ角1, 角2, 角3。thはθ=thetaの頭文字のつもり)。

GitHubのコードをgist-itで表示するのは、少し見にくいですかね。やっぱりGist使った方が良いかな。

それでは、今日はこの辺で。

https://github.com/furuya1223/AtCoder/blob/master/Submissions/ARC029/arc029b.cpp

スポンサーリンク
レクタングル(大)
レクタングル(大)

シェアする

  • このエントリーをはてなブックマークに追加

フォローする