0.はじめに
A問題からなんか歯ごたえがあり、それでもBまではすんなり解けましたが
Cが解けず時間切れ、Dもちんぷんかんぷんでした。
ビギナーとは・・・。
ただ、レイティングは1しか下がらなかったので、他の人も
難しかったんだろうなと思いました。
C,Dは試験の翌日解説等参考にしながらなんとか解けました。
- A - Find Takahashi
Aから配列を使う問題か・・・と思いつつさっと実装しテスト。
したら、最も高い橋の高さではなく何本目が一番高いかという
問題であることに気づきなかなか難しいな！となりました。
とはいえ、まぁ、最高値を更新した番号を覚えて置き
表示することで解決。
https://atcoder.jp/contests/abc275/submissions/36037869
2. B - ABC-DEF
Aに比べたら簡単だけど、Python以外だと型とかめんどいのかなと思いつつ
ササっと回答
https://atcoder.jp/contests/abc275/submissions/36041382
- C - Counting Squares
てこずりました。そして時間切れ。
例題の入力形式にある斜めの正方形が正方形ということにしっくりこず
これを正方形というのは無理があるのでは？という質問を投げかけようと
思ってしまいました。
考え方(最初は2次元表を作り判定・・・等無駄に複雑でしたが最終的に以下に)
1)インプットしながら、"#"のx,y座標を配列Dに保存
→x行-y列順に蓄積される
2)Dの各x,y座標から2つを順に組み合わせ辺とし、各辺について
正方形の条件を満たす他2点がないかをチェックし
存在する場合カウント。
ざっくり↑の考え方で回答したところ半分くらい不正解
試験時間では原因はつかめなかったけど、一旦寝て
翌朝試行錯誤して以下に気づく。
例題にある斜め正方形に対応したチェックをしていましたが
..1......
2........
...3.....
.4.......
例）座標1(1,3)-座標2(2,1)の辺をもとにした四角形頂点の求め方
(1)座標１と座標２の行列それぞれの差を求める
行の差1-2=-1
列の差3-1= 2
(2)座標１と座標２の対となる点の座標を求める
座標1の行に列の差を加え、列に行の差を加える
座標1(1,3)→座標3(3,4)
座標2の行に列の差を加え、列に行の差を加える
座標2(2,1)→座標3(4,2)
逆パターンもあることに気づきそれを加えることで解決しました。
.#.......
...#.....
#........
..#......
例）座標1(1,2)-座標2(2,4)の辺をもとにした四角形頂点の求め方
(1)座標１と座標２の行列それぞれの差を求める
行の差1-2=-1
列の差2-4=-2
(2)座標１と座標２の対となる点の座標を求める
座標1の行に列の差を加え、列から行の差を減らす
座標1(1,2)→座標3(3,1)
座標2の行に列の差を加え、列から行の差を減らす
座標2(2,4)→座標3(4,3)
加えて、辞書に正方形としてカウントした頂点の組み合わせを
記憶し、重複してカウントすることが無いようにして解答表示。
9*9の枠の制限があるのでTLEにならず完了でした。
色々無駄がありそうな実装になりましたが、まぁ通りました・・。
https://atcoder.jp/contests/abc275/submissions/36081873
4.D - Yet Another Recursive Function
試験時間に問題を見るも、ちょっと解き方が分かりませんでした。
試験後にかいせつをみてもメモ化再帰？？字面は見覚えあるけど
実装方法が分からず、ググってもピンときませんでした。
ただ、”https://docs.python.org/ja/3/library/functools.html”
こちらのサイトでメモ化再帰の関数”lru_cache”は
一回求めたinとoutの組み合わせを
辞書に登録する的なことが書かれていたので
自分なりに実装してみました。
dict={} #登録用辞書
def f(n):
if(n==0):
return 1
elif(n in dict): #引数が辞書にある場合は辞書の値を返す
return dict[n]
else:
r=f(n//2)+f(n//3)
if(n not in dict): #引数が辞書にない場合は辞書に登録しておく
dict[n]=r
return r
#--
N=int(input())
print(f(N))
関数の説明だけだと、理解できませんでしたが自分で
関数を作ることで、理解できるようになりました。