n次の連立方程式などABC133

概要

ABC133をA~Dまで、pythonでの正解例を見ながら解いていった。

目標

1. まずは自分でどういう方針で行けばいいのかを考えてから、コードを読む（こういうことをしたいけど、どう描くんだろうと思ったときは、それを明示的に意識する）
2. コードを読んだ時に、こういう考え方をしたら、自分もこんなコードが書けるな。みたいな学びを書くようにする

実践

ABC133
自分でA~Dまでは友達と一緒にといたので、答え合わせの気持ちで読む。
A　min(n*a,b)を出力する。
自分のコードと同じ
B
ポイント　自分が悩んだ点

• ２重配列をどう受け取るか
  • リストのリストで処理。（固定長で挿入、欠失がないので、配列の方が良さそうだけど、全体の計算時間には英kyほうがないからかな。）
  • p = [list(map(int,input().split())) for _ in range(n)]
• 整数かどうかの判定はどうする？
  • 僕はint(n) - n == 0 で判定した
  • math内のceil (切り上げ）、floor(切り捨て）で判断する。
  • ceil(n)==floor(n)

C [l,r]内の２つの整数の掛け算で2019 の剰余が最小になるものをさがす。

• 単純に全てでループを回すとTLE(計算時間制限）に引っかかる
• 僕の方針
  • r-lが2019以上なら必ず[r,l]に2019の倍数があるので積の余りの最小値は0になる。
  • 2019未満の時には、ループを回す。4*10^6なので大丈夫そう。
  • ループの境界条件などで色々と時間がかかった。
• 方針は同じ
  • ループを回して、最小値を更新していく。
• tips: 2019は素数でないので、3*673 r-lが673以上なら必ず積が割切れる事は証明できる。計算量が1/9倍になる。

D n(n=奇数)の連立方程式を解く問題

• 僕の方針
  • 考えつくまでだいぶ時間がかかった。
  • なぜ偶数ではダメなんだろう？　
  • 偶数だと奇数番目、偶数番目のダムに入る総和が等しくなるという制約条件があるので、nこの変数にn-1個の式になり、式が１つ足りな苦なり、数学的に解けない。
  • `Ans[i]=sum[a]-2*(sum[a[j] if i-j %2 == 0 )で良い気がしていた。
  • が、それだと、i以外の全ての要素を消せてないことに気づいた。
  • また、計算量も毎回のnのloopを回るので間に合わない。o(n^2)
  • １つを求めたら、あとは、連立法廷sきから連鎖的に求められる。o(1)*n
• 方針は最後の僕のものと同じ。」
  • 配列をspace 区切りで出力するときに、print(*Ans)で可能なのはすごい。

感想

100分ぐらいかかったので、想定より時間がかかった。
主な原因はD問題で問題で問われていないことを考えたり、そもそも方針が思いつかなかって悩んでいたこと。
10分経って進捗が（新たな方針が立つ気配がなかったら）解説を見るべき。

あとは、以外に、解説を見ながらならd問題でも難しくは思わなかった。
今回が簡単だったのもあるかもだけど、考察力に比べて実装力が圧倒的に足りていないのが推測できる。