×
[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。
次はyukicoder No1と言ったな、あれは嘘だ。
007！
実は見たことがない。
ちょっと人生損している感じがするから見てみたいと結構前から思っている。
初めて同じコンテストを通して解いた。
全てACが出るまで3時間半くらいかかった。
ゲーム配信を眺めながら解いていたからまじめに頑張れば2時間半くらいだったかもしれない。
D問題は方針通り解いてWAしてから他人の回答を見たが、結局何の意味もなかったから実質1人で解き切ったと言っても良いだろう。
むしろ他人の答えと自分の回答の違いを見つけるのに時間を食ったので、他人の回答が見られない状況の方が早かったまである。
A 植木算
https://atcoder.jp/contests/abc007/submissions/3862921
B 辞書式順序
https://atcoder.jp/contests/abc007/submissions/3862989
この2つはまあ問題ない。
A問題はここまで典型的な植木算とは思わなくて衝撃を受けた。
B問題はちょっと無駄なことをしようとしてしまったのを反省。
bbbbb→aaaaaなんてしなくてもa以外ならaを出力すれば良いとすぐに気づくべきだった。
一種のいじわる問題と感じた。
ここまでで30分ほど。
C 幅優先探索
https://atcoder.jp/contests/abc007/submissions/3863401
一目見て「幅優先探索だ！」って思ったよね、書いてるんだもん。
1年前に水たまりがどうのっていう問題を解いたことがある気がするが、ある程度知識がついてから与えられた盤面に対して何かをする問題は初めてだった。
そもそもDP以外の探索問題は全探索以外やったことがないので、dxdyとかどうやって使うんだっけとかは少し調べたが、特に問題なく書けた。
ダイクストラ法を実装した経験が生きてキューを使った実装をかなりシンプルに書けた気がする。
1文字ずつ入力を受け取るにはどうしよう、という部分に一番時間を使った。
cin.ignore()使うのかなとか色々調べたが、char型に代入して行けばいらないらしい。
じゃあcinで改行をchar型に入れられないのか？
ひいては半角スペースも同じじゃないのか？
この辺りは要勉強。
ここまでで1時間15分ほど。
A,B,Cと3連続AC。
簡単な問題でもどこかしらミスをすることが多かったので、嬉しいと共に少し成長を感じた。
D 禁止された数字
WA
https://atcoder.jp/contests/abc007/submissions/3864683
AC
https://atcoder.jp/contests/abc007/submissions/3864750
問題のD問題
あまり調べていないがDPで解くのが主流っぽい？
0~9,0~99,0~999,...と分けた場合の4と9の数は関数で表せることをすぐに確認できたのでそれを使って解く方針にした。
当初下の桁から余りを使って数えていたが、それだと上位に4がある場合にうまくいかないことにほぼ完成してから気付いた。
1234567なんかの場合に、一番下の桁だけを考えた場合に0～7は直接4を含まないが、実際には1234560～1234567なので4を含むということだ。
上から順に書き換えるように直し終わってWAした時点で2時間半ほど。
ここからが分からなかった。
結論を言えばpow関数の誤差。
例えばこんなプログラムを書く。
途中から1どっか行くのおかしくない？？？
曰くpow関数でlogを使っているから整数のべき乗でも誤差が乗るらしい。
誤差のせいで切り下げで-1されるなら、+1してない方は999...になるべきじゃないのか・・・？
整数型にキャストしたら正しい答えが出るのおかしくないか・・・？
全く分からないが疑いようのない結果に文句を言っても仕方がないから受け入れるしかない。
powで得られる値は実際には僅かに小さくなっているが、それ単体で評価すると正しい値になり、さらに演算を加えると誤差が表面化するということだろう。
幸い10のべき乗ではlong long型の上限までは明示的にキャストすることで正しい値になることが確認できたので、学びを得られたということで。
ついでに実験してunsigned long long型(i=19まで)でも大丈夫だった。
環境によって変わるのは勘弁して欲しいけど違いそうな気はする。
とりあえず日をまたがずに全部解けてよかった。
よく分からないWAが出るときに、問題文の条件を見返してみたり、どっかで誤差出てるんじゃないかって探してみたり、ちょっとこなれてきた感はある。
解く方針の探し方は問題ないが、その方針の問題を見つけられてないのは改善点。
後は、変数名どうしようとか、どう書けば変数使いまわしてコスト抑えられるかなとか、プログラミングに慣れてないが故の問題もなんとかしたい。
ただ今回の場合は、問題を解くのに専念し知り得ぬ誤差の問題がなかったとしたら、2時間以内で解けていた可能性もある。
コンテスト参加も見えてきたか。
007！
実は見たことがない。
ちょっと人生損している感じがするから見てみたいと結構前から思っている。
初めて同じコンテストを通して解いた。
全てACが出るまで3時間半くらいかかった。
ゲーム配信を眺めながら解いていたからまじめに頑張れば2時間半くらいだったかもしれない。
D問題は方針通り解いてWAしてから他人の回答を見たが、結局何の意味もなかったから実質1人で解き切ったと言っても良いだろう。
むしろ他人の答えと自分の回答の違いを見つけるのに時間を食ったので、他人の回答が見られない状況の方が早かったまである。
A 植木算
https://atcoder.jp/contests/abc007/submissions/3862921
B 辞書式順序
https://atcoder.jp/contests/abc007/submissions/3862989
この2つはまあ問題ない。
A問題はここまで典型的な植木算とは思わなくて衝撃を受けた。
B問題はちょっと無駄なことをしようとしてしまったのを反省。
bbbbb→aaaaaなんてしなくてもa以外ならaを出力すれば良いとすぐに気づくべきだった。
一種のいじわる問題と感じた。
ここまでで30分ほど。
C 幅優先探索
https://atcoder.jp/contests/abc007/submissions/3863401
一目見て「幅優先探索だ！」って思ったよね、書いてるんだもん。
1年前に水たまりがどうのっていう問題を解いたことがある気がするが、ある程度知識がついてから与えられた盤面に対して何かをする問題は初めてだった。
そもそもDP以外の探索問題は全探索以外やったことがないので、dxdyとかどうやって使うんだっけとかは少し調べたが、特に問題なく書けた。
ダイクストラ法を実装した経験が生きてキューを使った実装をかなりシンプルに書けた気がする。
1文字ずつ入力を受け取るにはどうしよう、という部分に一番時間を使った。
cin.ignore()使うのかなとか色々調べたが、char型に代入して行けばいらないらしい。
じゃあcinで改行をchar型に入れられないのか？
ひいては半角スペースも同じじゃないのか？
この辺りは要勉強。
ここまでで1時間15分ほど。
A,B,Cと3連続AC。
簡単な問題でもどこかしらミスをすることが多かったので、嬉しいと共に少し成長を感じた。
D 禁止された数字
WA
https://atcoder.jp/contests/abc007/submissions/3864683
AC
https://atcoder.jp/contests/abc007/submissions/3864750
問題のD問題
あまり調べていないがDPで解くのが主流っぽい？
0~9,0~99,0~999,...と分けた場合の4と9の数は関数で表せることをすぐに確認できたのでそれを使って解く方針にした。
当初下の桁から余りを使って数えていたが、それだと上位に4がある場合にうまくいかないことにほぼ完成してから気付いた。
1234567なんかの場合に、一番下の桁だけを考えた場合に0～7は直接4を含まないが、実際には1234560～1234567なので4を含むということだ。
上から順に書き換えるように直し終わってWAした時点で2時間半ほど。
ここからが分からなかった。
結論を言えばpow関数の誤差。
例えばこんなプログラムを書く。
for(int i=10; i<=20; ++i){
printf("----- i=%d -----\n",i);
printf("%f\n",pow(10,i));
printf("%f\n",pow(10,i)+1);
printf("%lld\n",(long long)pow(10,i)+1);
}
----- i=10 -----
10000000000.000000
10000000001.000000
10000000001
----- i=11 -----
100000000000.000000
100000000001.000000
100000000001
----- i=12 -----
1000000000000.000000
1000000000001.000000
1000000000001
----- i=13 -----
10000000000000.000000
10000000000001.000000
10000000000001
----- i=14 -----
100000000000000.000000
100000000000001.000000
100000000000001
----- i=15 -----
1000000000000000.000000
1000000000000001.000000
1000000000000001
----- i=16 -----
10000000000000000.000000
10000000000000000.000000
10000000000000001
----- i=17 -----
100000000000000000.000000
100000000000000000.000000
100000000000000001
----- i=18 -----
1000000000000000000.000000
1000000000000000000.000000
1000000000000000001
----- i=19 -----
10000000000000000000.000000
10000000000000000000.000000
-9223372036854775807
----- i=20 -----
100000000000000000000.000000
100000000000000000000.000000
-9223372036854775807
途中から1どっか行くのおかしくない？？？
曰くpow関数でlogを使っているから整数のべき乗でも誤差が乗るらしい。
誤差のせいで切り下げで-1されるなら、+1してない方は999...になるべきじゃないのか・・・？
整数型にキャストしたら正しい答えが出るのおかしくないか・・・？
全く分からないが疑いようのない結果に文句を言っても仕方がないから受け入れるしかない。
powで得られる値は実際には僅かに小さくなっているが、それ単体で評価すると正しい値になり、さらに演算を加えると誤差が表面化するということだろう。
幸い10のべき乗ではlong long型の上限までは明示的にキャストすることで正しい値になることが確認できたので、学びを得られたということで。
ついでに実験してunsigned long long型(i=19まで)でも大丈夫だった。
環境によって変わるのは勘弁して欲しいけど違いそうな気はする。
とりあえず日をまたがずに全部解けてよかった。
よく分からないWAが出るときに、問題文の条件を見返してみたり、どっかで誤差出てるんじゃないかって探してみたり、ちょっとこなれてきた感はある。
解く方針の探し方は問題ないが、その方針の問題を見つけられてないのは改善点。
後は、変数名どうしようとか、どう書けば変数使いまわしてコスト抑えられるかなとか、プログラミングに慣れてないが故の問題もなんとかしたい。
ただ今回の場合は、問題を解くのに専念し知り得ぬ誤差の問題がなかったとしたら、2時間以内で解けていた可能性もある。
コンテスト参加も見えてきたか。
PR
コメント