A問題の解決
AtCoder Beginner Contest 275
A問題、Find Takahashi
問題文、AtCoder村にはN本の橋があり、I本目の橋の高さはHIです。
ここで、AtCoder村にあるN本の橋のうち、どのI異なる2本の橋も高さが異なります。
AtCoder村で最も高い橋は何本目の橋か出力してください。
入力例1、Nが3、Hが50、80、70で出力例は2、80の2本目の橋が一番高いので2ですね。
Nイコールインプット、Hイコールリストのマップイントインプットドットスプリット、
プリント、Hドットインデックス括弧マックスHプラス1で多分出るはず。
Hの中で一番大きい値をとって、それのインデックス数、何番目にあるんですかというのをとって、
それは0インデックス始まりなのでプラス1することで1本目2本目という言葉が出てきます。
正解したのでB問題いきます。
B問題、ABC-DEF
問題文、皮膚整数ABCDEFがあり、A×B×C大なりイコールD×E×Fを満たしています。
A×B×C-D×E×Fの値を998244353で割った余りを求めてください。
やるだけかなこれは。
やるだけだと多分エラーになりそうですが、一旦やるだけやってみましょうか。
まず割るものWにしておこう。
Wイコール998244353。
入力例が235124。
ABCDEFイコールマップのイントインプット.スプリット。
A×B×C-D×E×F。
A×プリント。
A×B×C-D×E×F。
割る。
割るじゃない。
%W。
22。
22ですね。
入力例2は1755647。
入力例3は0。
入力例はクリアしたので提出してみましょうか。
多分どっかしらでエラーが起きると思うんですけどね。
あーACしましたね。
はい、じゃあC問題いきますね。
C問題の実装
カウンティングスクエアーズ問題文。
2次元平面があります。
1以上9以下の整数RCについて、
SRのC番目の文字がシャープであるとき座標RCにポーンが置いてあり、
SRのC番目の文字がドットであるとき座標RCに何も置かれていません。
この平面上の正方形であって4頂点すべてにポーンが置いてあるものの個数を求めてください。
S。
4頂点。
平面上の正方形。4頂点すべてにポーンが。
4頂点。
だから00と。
ってことですよね。
左。
ん?あ。
座標を11、12、22、21を頂点とする正方形は4頂点すべてにポーンが置かれています。
座標48、48、1234、48、56、77、69を頂点とする正方形も、
はぁ、正方形の形でシャープが置かれている間隔があるものの個数を数えろ。
ですね。
これはどうしたらいいんだ。
長さ9の文字列。
長さ9の文字列なので、
00スタートの徐々に長さをプラスしていく、99までプラスしていくぐらいしか思いつかないですけどね。
えーっと。
その足し方がちょっとわかんないな。
っていうかそうか。斜めもあるからとなるとちょっとややこしいですよ。
んー、ちょっと思いつかなさそうなんで解説を見ていきますか。
いいよ。
この問題は様々な解法が考えられますが、
適当に実装すると同じ正方形を2回数えてしまうといった問題が起こることがあります。
ここでは実装方針の一例を紹介します。
まず正方形を列挙する必要があります。
これは正方形の頂点のうち1個を決め打ち、
次にその頂点を端の点とする辺のうち片方を決め打つことで可能です。
次に正方形を重複して数えない方法を説明します。
これには例えばstd://setを用いて正方形を集合として管理すればいいです。
これ多分C++だよね。
C++の実装例があるので、
これをちょっと、
いやでもなんかわかんない文字あるな。
4文の中にauto&v://sって書いてる。
なんじゃこりゃ。
ちょっと他の解説も見てみましょうか。
ユーザー解説が2つあるので。
公式解説より計算量は悪くなりますが、
あまり難しいことを考えずに実装できる解法を紹介します。
まず問題の制約より、
ポーンが置かれているのはx座標、y座標が1以上9以下の整数であるような座標に限られます。
このような座標のうちの4点を決め打つと正方形が1位に決まるので、
4点の組み合わせを全探索し、
その4点からなる正方形があるかどうかを判定すればよいです。
4点の座標が与えられたときに、
その4点からなる正方形があるかどうかの判定方法には様々ありますが、
比較的簡単に判定できる方法の1つは、
2点間の距離を用いた次のような判定方法です。
4点のうちの2点間を結ぶ6本の線分について、
その長さを小さい順に並べたものをD1からD6とする。
このとき全てが成り立っていれば、この4点からなる正方形があると言える。
D1からD4までは同じ値。
D5とD6が同じ値。
D5は√2D1。
√2×D1かな。
これは辺の長さを実際に全て求めることによって定数時間で判定可能。
上の3つの条件を実際に判定する場合は整数の範囲内で判定できるよう、
定規の条件式の代わりに両辺を2乗した
D5の2乗イコール2×Dの2乗
2×D1の2乗を判定するとよいです。
つまり
全列挙すつつってことかな。
もう一つ解説があったので、それを読んで最後にしたいと思います。
2点を決めたとき、頂点を右回りに見たとき、その2点が連続するような正方形は1位に決まります。
そこで2点を全探索することを考えます。
しかしそのままだと、例えば図がいっぱい書いてくれてますね。
上の図のABの2点を選んだとき、BCの2点を選んだときで同じ正方形を数えてしまいます。
そこで正方形の右斜め下向きの辺に注目。
これは真横を含まず、真下を含むことにすれば、どのような正方形にもちょうど1つ存在します。
したがって2点を選ぶとき、2点目を最初に選んだ点から見て、右下の位置にある点だけから選ぶことで、か不足なく正方形を数えることができます。
2点を決めたとき、残りの2点の座標は数を参考にうまく求める必要があります。
Pythonの実装例があるので、これを社交して今日は終わりにしようと思います。
別窓で出して見ながら書いていこう。
Itertoolsをインポートしていますね。
インポート。
Itertools。
s="list.input.for○○inRange9&s="0".
for.
i1,j1,i2,j2
in Itertools.productのレンジが9のrepeat="4".
ちょっと画面が見えない。
こうすることでコメントアウトで解説が書いてありますね。
i1,j1から右下の向きにi2,j2がある。
ではフォー文の中へ行きます。
i2大なりi1&j2大なりイコールj1&sのi1番目がシャープだったら
i1&sのi2,j2番目もシャープだったら
diイコールi2-i1
djイコールj2-j1
i3イコールi2プラスdj
j3イコールj2-di
i4イコールi3-di
j4イコールj3-dj
i0イコールi3-9&0イコールj3-9&0イコールi4-9&0イコールj4-9
&sのi3,j3番目イコールイコールシャープ&sのi4,j4番目イコールイコールシャープだった場合アンサーはプラスイコール1。
プリント&アンス
イターツールズ
di、djは差ですね。
斜めを求めてるんだこれは多分。
ちょっとこれは数学知識な感じもしますね。
ACしたので今日はここまでにしておきます。
ではまた次回お疲れ様です。