AtCoder Beginner Contest 275 メモ(A-D)
今回の結果
3AC
B問題が考えても解けず、A,C,Dの3AC。
C,Dが両方解けて順位は過去最高、Highestも更新。
少しずつ上がってきたけど緑はまだ遠い。
A - Find Takahashi
Difficulty: 14
参加中に考えたこと
最も高い橋が何番目かを求めたいので、高さの最大値とそれが何本目かの情報を保持して、１つずつ順番に高さを比較して最大値が更新される時にそれぞれを更新してあげる。
chmaxマクロは値の更新をしつつ更新されたかの結果を返すので、trueを返したら何本目かの情報を更新してあげると最も長い橋が何番目かを取得できる。
B - ABC-DEF
Difficulty: 147
参加中に考えたこと
各値が最大
最終的に求めたい答えが 998244353 で割った余りなので先に
考察・感想
Pythonだと桁あふれの考慮なくそのまま数式の処理ができる問題。
C++とPythonとで難易度が全然違うんだけど、パフォーマンスには言語ごとの差って考慮されてないですよね。。？
C - Counting Squares
Difficulty: 760
参加中に考えたこと
方針を立てるにあたってまず検討できそうな事柄を整理する。
- 二次元平面の広さは
9 \times 9 O(N^3) O(N^4) - 1つの頂点が複数の正方形の頂点になることがある
- 入力例１のようにxy軸と平行でない正方形については、x軸とy軸にそれぞれいくつ移動するかの値を持つことで事足りる。三角関数は必要ない。
- 正方形を数える際に重複が生じないようにする、または最後に重複分で割る
1点目と2点目から全探索の方向性で進めて問題なさそう。
3点目の、正方形をどうやって探すかという点については、 ポーンが置いてある座標について2点を選び、正方形を作れるかを判断していく方向でいけそう。
点A
C(X_A + d_y, Y_A - d_x), D(X_B - d_y, Y_B + d_x) C(X_A - d_y, Y_A + d_x), D(X_B + d_y, Y_B - d_x)
この2種類についてそれぞれ点C,Dにポーンがあれば正方形があることが分かる。
（最初はBからC,Dの位置を求めようとしたが B→C→Dと辿ってDの位置を探すのが複雑になると思った）
4点目については、正方形ができたらsetに格納すれば重複なく数えることはできそうだが、重複込みで数えた後に重複分の数を割る方法を取ることにした。
全探索で調べた時に1つの正方形についていくつ重複が発生するかは、頂点が4つあり、各頂点について右回り、左回りの2つあるので
入力例1,2がACし、あとはTLEにならないかを全て # にしたデータで確認して問題なかったので提出してAC。
考察・感想
点C,Dを求める時に、9x9の平面に収まらないときは収まるようにする必要があり、max(0,min(8,x)) と書いていたが、 C++17 だと clamp関数 というのがあるのを解説を見て知った。
公式の解説は左回りで固定してる。
そっちのほうがC,Dは一意になるので処理はこっちのほうが簡単になりそうと解説のコードみて思った。
D - Yet Another Recursive Function
Difficulty: 606
参加中に考えたこと
f(0) = 1 f(k) = f(\lfloor \frac{k}{2}\rfloor) + f(\lfloor \frac{k}{3}\rfloor)
これを再帰関数で書けばいいだけ？
条件の2つ目は小数点以下を切りすてるのでそれぞれ整数のまま計算すればこれはできるので、以下のように書けばよさそう。
return f(k/2) + f(k/3);
これだけだとC問題のレベル。。
制約の、
これで
Discussion