あさかつ09/15 無駄に複雑な計算をしてしまって。冷静に問題を見よう
09/15
— hiroendore (@hiroendore) 2020年9月14日
1. できるだけ500円玉を使ってからできるだけ50円玉を使う
2. 無駄に等比級数の和の公式とか使ってしまってバグらせて時間かかった件・・・ひとまず単純なシミュレーションでTLEするか確かめるべきだった。K=0でTLEしてしまってそこを良く考察できず焦った
#あさかつ考察
あさかつ09/14 4完できたらからよし？
09/14
— hiroendore (@hiroendore) 2020年9月13日
1. アルファベットを順にみていって出てこないやつがあったら出力
2. 前解いた。配列の10番目の要素がピン番号0だけど、(ピン番号-1)ですべて表せるなと気づいた
3. 前解いた。辺を小さい順に並べて、二辺を選ぶ。二辺の和の長さより小さくなるようなインデックスを二分探索
#あさかつ考察
ABC178 マンハッタン距離は45度回転...?
hiroendoreさんのAtCoder Beginner Contest 178での成績：2682位
— hiroendore (@hiroendore) 2020年9月13日
パフォーマンス：1046相当
レーティング：648→698 (+50) :)
Highestを更新しました！#AtCoder #ABC178 https://t.co/0TzETxfhvg
この調子でいけばあと三回ぐらいで緑？まあ調子が悪い時も含めて後６回ぐらいは必要か。
ABC178
— hiroendore (@hiroendore) 2020年9月13日
A. 0なら1、1なら0
B. すみっこ同士をかけた４通りのうちの最大値
C. 全部 -（0がない）-（9がない）+（0も9もない）
D. 配列の取りうる長さを考えて1~N//3、それぞれの場合について、まず3を足した後に残りの数を振り分けることを考える
ABC178
A. 0なら1、1なら0
B. すみっこ同士をかけた４通りのうちの最大値
C. 全部 -（0がない）-（9がない）+（0も9もない）
D. 配列の取りうる長さを考えて1~N//3、それぞれの場合について、まず3を足した後に残りの数を振り分けることを考える
E. 考えて調べたが良く分からなく、なんか集中力も途切れてきたので終わった。解説を読んだ。良く分からんけど調べてもうちょい考えたらいけたのかもしれない。（希望的観測）
Dとかも結局場合の数の計算コピペしちゃったよ。一応逆元を求めるのが大事というのはわかっているけど正直実装できない・・・
マンハッタン距離は45度回転？
— hiroendore (@hiroendore) 2020年9月13日
マンハッタン距離について線対称に移動するような考え方を教えていただいた。
すみません、訂正します。
— 露草@競プロたのちい (@constant_drops) 2020年9月13日
4パターンもいらず、元の座標と、元の座標を全部x軸に対して線対称にしたのの2パターンをみて、それぞれのx+yの最大値-最小値を出せばいけました！https://t.co/S6P0odON3X
せっかくだからマンハッタン距離について数式的な意味でも図形的な意味でも理解できればいいな。
今回はアルゴリズム色が強いというよりは数学場合の数ごり押しみたいなやりかたをしてしまった。
Dは一応想定解DPだったらしいし。
あさかつ09/13 小数点の扱いとDP
09/13
— hiroendore (@hiroendore) 2020年9月12日
1. N//10 + 1個10個セットだけ買うのが安いか、N//10個10個セットを買ってN%10個ばら買いするのが安いか
2. 掛け算するたびに10**9+7で割っていく
3. 前も解いた。前も解けなかった。Bを整数にするのにint(B*100)じゃ通らないケースがある。保障されないだろうがどんなケース？
#あさかつ考察
3問目の浮動小数点の扱いについては詳しく書かれた解説記事があった。
float(0.29)*10 = 28.99999..など、浮動小数点で表した際に整数部分が1減る場合があることに注意。
あさかつ09/12 不等式の同値変形の条件には気を付けよう（両辺の二乗）
09/12
— hiroendore (@hiroendore) 2020年9月11日
1. (D-1)//A_i + 1をたしていく
2. 前解いた
3. 最初に馬鹿正直にやって、まあ精度的にむりなんだろうなと思う→すべて整数にすれば制度の問題をクリアできると思い計算したがなんか一つだけテストケースがWAになってしまい・・・
解説を読んだらc-a-b>0という条件忘れ
#あさかつ考察
09/12
1. (D-1)//A_i + 1をたしていく
2. 前解いた
3. 最初に馬鹿正直にやって、まあ精度的にむりなんだろうなと思う→すべて整数にすれば制度の問題をクリアできると思い計算したがなんか一つだけテストケースがWAになってしまい・・・
解説を読んだらc-a-b>0という条件忘れ
#あさかつ考察
うーん、なんか不等式の操作と同値条件みたいなものがごちゃごちゃになっていたな・・・2*sqrt(a*b)< c-a-bで、2*sqrt(a*B)>0なんだから、c-a-bも正だろ？みたいな。中学生からやり直すしか・・・
まあ振り返ると単純だが、このあたりコンテスト中にドツボにはまるとやはり抜け出せなさそうだから踏んどいてよかったミスということで。
5. 少し問題の考察だけした。解説を読んだ。二分探索なのね。二分探索を応用した問題ってこの前もあさかつであったけど案外解けていない（後半の問題ということもあるけど）これは午後にでも写経しておくかな・・・
不等式の同値変形の問題
二分探索もやっとかないと。
あさかつ09/11 デバッグのプリントは標準エラーに
09/11
— hiroendore (@hiroendore) 2020年9月11日
1. 違う文字になったらans++
2. 各点を見て行ってそれが"."だったら無条件に壁を塗って"#"なら隣り合う"#"も塗って壁全体が塗れたらOK
3. ３つの組み合わせで安直に解いてTLE。２つa, bを選んでa+bよりもちいさくなるようなcの数を二分探索で数えてやるようなことをやる。
#あさかつ考察
09/11
1. 違う文字になったらans++
2. 各点を見て行ってそれが"."だったら無条件に壁を塗って"#"なら隣り合う"#"も塗って壁全体が塗れたらOK
3. ３つの組み合わせで安直に解いてTLE。２つa, bを選んでa+bよりもちいさくなるようなcの数を二分探索で数えてやるようなことをやる。
#あさかつ考察
今日はやたらデバッグプリントを残したまま提出してWAになることが多かった・・・金曜日はやっぱ少し疲れてんのかな
こんなことをつぶやいていたらアドバイスをいただいた
標準エラー出力に出すようにすると，消し忘れても安心です．print(f'x={x}', file=sys.stderr)
— yamate11 (@_yamate11) 2020年9月11日
明日から使ってみよう。
