"競技プログラミング問題"カテゴリーの記事一覧
-
×
[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関数の誤差。
例えばこんなプログラムを書く。
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.00000010000000001.00000010000000001----- i=11 -----100000000000.000000100000000001.000000100000000001----- i=12 -----1000000000000.0000001000000000001.0000001000000000001----- i=13 -----10000000000000.00000010000000000001.00000010000000000001----- i=14 -----100000000000000.000000100000000000001.000000100000000000001----- i=15 -----1000000000000000.0000001000000000000001.0000001000000000000001----- i=16 -----10000000000000000.00000010000000000000000.00000010000000000000001----- i=17 -----100000000000000000.000000100000000000000000.000000100000000000000001----- i=18 -----1000000000000000000.0000001000000000000000000.0000001000000000000000001----- i=19 -----10000000000000000000.00000010000000000000000000.000000-9223372036854775807----- i=20 -----100000000000000000000.000000100000000000000000000.000000-9223372036854775807
途中から1どっか行くのおかしくない???
曰くpow関数でlogを使っているから整数のべき乗でも誤差が乗るらしい。
誤差のせいで切り下げで-1されるなら、+1してない方は999...になるべきじゃないのか・・・?
整数型にキャストしたら正しい答えが出るのおかしくないか・・・?
全く分からないが疑いようのない結果に文句を言っても仕方がないから受け入れるしかない。
powで得られる値は実際には僅かに小さくなっているが、それ単体で評価すると正しい値になり、さらに演算を加えると誤差が表面化するということだろう。
幸い10のべき乗ではlong long型の上限までは明示的にキャストすることで正しい値になることが確認できたので、学びを得られたということで。
ついでに実験してunsigned long long型(i=19まで)でも大丈夫だった。
環境によって変わるのは勘弁して欲しいけど違いそうな気はする。
とりあえず日をまたがずに全部解けてよかった。
よく分からないWAが出るときに、問題文の条件を見返してみたり、どっかで誤差出てるんじゃないかって探してみたり、ちょっとこなれてきた感はある。
解く方針の探し方は問題ないが、その方針の問題を見つけられてないのは改善点。
後は、変数名どうしようとか、どう書けば変数使いまわしてコスト抑えられるかなとか、プログラミングに慣れてないが故の問題もなんとかしたい。
ただ今回の場合は、問題を解くのに専念し知り得ぬ誤差の問題がなかったとしたら、2時間以内で解けていた可能性もある。
コンテスト参加も見えてきたか。PR -
今回は最新問題。
解き始めたのは当日だが参加はしていない。
性格上コンテストに参加するのはかなり先になりそう。
コード①
https://atcoder.jp/contests/caddi2018b/submissions/3853552
コード②
https://atcoder.jp/contests/caddi2018b/submissions/3853928
コード③
https://atcoder.jp/contests/caddi2018b/submissions/3853945
一応解説は軽く目を通したが、初見で思い浮かんだ解き方と同じで嬉しい気持ちに。
ただ解説の書き方が難しすぎて一瞬こんな問題解けねぇと思った。
コード①
今回の挑戦は素因数分解のプログラムを探すことから始まった。
普通に2で割れるだけ割って・・・ってやってたら遅いでしょさすがに?って思いながら調べてたらまさかのこれが正解だった。
入力値大きいしこれだとTLEだろうと2で割るのをやめて2のn乗3のn乗と割っていく関数を作成したものの、ところどころ間違えたりTLEだったり。
回答例見るとみんな普通に素因数分解してるしn乗しなくていいや。
コード②
間違いが全く分からない。
他人のコード見て間違い探しするも分からない。
for文で最終的な答えを求めているコードを発見。
試しにその方式で書いてみるとあっさりAC。
?????
割り算で誤差が出るのか?整数だぞ?切り下げじゃないのか?
むしろforの条件式にn入れるのって自然ではないのでは?
この方式思いつかないと答えでないってこの世界ついていけそうもない、なんて考えていた。
コード③
お前n乗じゃなくて×nしてるやんけ!!!
ということで、自分で思いついた書き方でACできた。
頭に思い描いたコードを間違いなく書けるようになってきた思ってたのにどこか間違ってるんだろうなぁ・・・、とそこそこ落ち込んでいた。
そういう次元じゃない間違いだったから少しホッとした。
自分らしいミスといえば自分らしい。
余談
最初に思いついたn乗で割っていくのを正しく書き直すとTLEだった。
条件式一緒な時点でそこそこ遅いpowを同じループ数繰り返すのは無駄。
条件式にn乗したものを使えばいけそうな気がするんだけど、うまい入れ方が分からなかった。
そもそも早くなる可能性が存在しない可能性まであるからとりあえず置いておく。
もう1つ余談。
この問題をやったのと同じ日にダイクストラ法を調べていて、初めてcontinueなんていう関数を知った。
この問題の他人のコードを調べている時に、素因数分解を行う関数でcontinueを使っているのを見て結構な未来を感じた。
もともとループ内で無駄な宣言を省こうと考えて書いていたのだが、continueを入れるだけでずいぶんとすっきり見やすくさらに速度アップと来た。
繰り返し文では積極的に使っていきたい。
同時に、参照渡しした引数に結果を代入する形式からmap型の戻り値を持つ関数に変更した。
どちらが早いかは知らないが、複数の値を持ち得る戻り値にできることを忘れていた。
しばらくプログラムを書いていなかったため、頭に学生時代のCの「戻り値は1個だけ。複数戻したかったらポインタ型引数。」しか残っていなかった。
どう考えても戻り値設定した方が見やすいから忘れないように・・・。
次回はyukicoder No1のリベンジの予定。
ダイクストラ法の関数は作成済み。 -
ダイクストラ法は置いておいて、ひょんなことから目についたこの問題を解いてみた。
AOJは1度だけ挑戦したことがあるけど結局解けていなかった気がする。
テストケースが連続で入力されるせいで出力のタイミングが分からない、テストケースを確認しようとするもなぜか表示されない、簡単な問題だったからアルゴリズムは間違えていないはず、と何かがおかしいとやめた記憶がある。
今回ACを取るまでに、テストケースは入力ごとに出力すればいい、テストケースを連続で入力してまとめた場合は量が多いから表示されない、ということが分かった。
すなわちアルゴリズムを間違えていたのだろう・・・。
コード①
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3298606#1
まずは失敗作。
URLがどっか行っちゃったからACした後わざわざジャッジし直した。(失敗作のコードまでCtrl+Zで遡れるAtomすごい)
(1つの頂点を除いた三角形の面積>四角形の面積)になればその四角形は凹であると言えるはず。
最初はこの方針の回答を目指した。
三角形の面積は、ヘロンの公式を使って求め、割り算やら平方根を除いて誤差が出ないようにして大小関係の把握のみに努めた。
今回の一番の大仕事、三角形との面積の比較は頑張ってbit演算で実装した。
というのも、1年の時を経てまた競プロやってみようかなと思ったのが、このbit演算による部分が大きいからだ。
特にnext_combinationはすごい。蟻本読んでちょっと感動した。
1年前に蟻本買っててよかったと思ったね。別に数学的にすごいことをしているわけではないけど、確かにその操作したら組み合わせを列挙できるよね、という感じ。早くbit演算でなにか実装してみたい気持ちが強かった。そこでこの問題。対角線の長さ計算を一度に抑えて、選んだ三角形ごとに持ってこれないかな、と考えていたらbitが使えるんじゃないかと。
頂点の組み合わせのbitをキーにしたmapに保存し、うまくループを回せばできそうだと考えた。結局ACできなかったからbit演算部分が合っているか分からないものの、bitを利用した実装を経験できたのは経験値としてでかい。
四角形の面積は、四角形を半分に割ってそれぞれヘロンの公式を使って足そうという考え。
・・・だったのだが、そもそも凹ならそれじゃ計算できない。
割り方によって正しい答えと間違った答えが出る。
ということに書き終わった後に気づいたので第2作。
コード②
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3298517#1
もはやbitをキーにしたmapである必要はないが名残ということで。
今回は先程の気づきを活かし、三角形に分けて四角形の面積を求めた場合、分け方によって違いが出れば凹、という方針。
三角形の面積は、先程と同様ヘロンの公式を使って求めた。
誤差を減らせるように割り算や平方根を減らしたつもりだが、それでも誤差があるのかACには至らなかった。
そこでEPSを使って誤差を打ち消そうとしたのだが、それでもACには至らない。
辺の長さの計算に平方根を使っているとは言え、そこまで誤差が出るのだろうか。
どこかでコードを間違っているような気がしなくもない。
コード③
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3298582#1
どんどんコードが短くなっていく。
そもそもヘロンの公式なんて使わなくても良かったのではな方針。
外積使えば面積出せるじゃんに気づいて割り算平方根なく誤差なく気持ちよくAC。
外積が負の値も取れるとか、そもそも外積どうやって出すんだっけとか色々忘れてて苦労した。
今回の収穫は、bit演算の経験と、数学的知識使えば簡単正確に書けるねってこと。
地味に作り始めたライブラリにヘロンの公式も追加しておいた。
コード②に関しては、誤差の影響がどの程度なのか分からないものの、実装としては間違ってないと思っているので、全然違うだろって部分あったら教えてほしいです。 -
コード
https://yukicoder.me/submissions/304205
確か初めての競プロはyukicoderだったので、再開ということで初心に戻って雑に★2~★3あたりを解いていこうの巻。
やったことある感じがする、DPかな?という第一印象。
この場合のDPの書き方がすぐに出てこなかったから、誰かが愚直に書くのも勉強になるよと書いていたのを思い出しDFSで書いてみるもWA。
町nまでコストcで行くための関数をsolve(n,c)とすると、solve(n-i,c-[iからnまでのコスト])を1≦i<nで回して最小を取ればいいのではという方針。
今度は配列数を多めに取ってもだめだった。
解説曰くダイクストラ法で解くらしい。
高校の頃の記憶を掘り返してダイクストラ法を考えるのもしんどいし、一度勉強し直してから解き直そう。
今の知識量だと再帰でも解けるだろうとは思うけれど、ダイクストラ法でないと解けないのかもしれない。
やはり一度その辺りの知識をつけるのが良いか。
12/16 23:30 追記
コード
https://yukicoder.me/submissions/304478
問題文を見落としていた。
スタートの町とゴールの町が同じでも道は2種類以上あるかもしれない。
これに対応するためにVectorを3重にしたらTLE。
テストケースを見る限り答えは合ってそう。
もうちょっと良い対応の仕方があると思うんだけど思いつかない。
もはや経験不足しか感じない。
次はダイクストラ法を学ぶ。 -
コード
https://abc017.contest.atcoder.jp/submissions/3789176
競プロ初記事は初心者らしくACできない記事。
解説見ながらとりあえず愚直に書いてTLE。
しゃくとり法使って書くも、既に出てきた数字を探すのにfind使ったせいでどうも遅いが一応AC。
納得できずに高速化を図るもACが出ない。←今ココ
単純にdpの更新方法の認識が間違っている気がするけど、一度ACできた=アルゴリズムは間違っていないはず。
もう手が出ない。
12/15 6:00追記
AC取れた。
https://abc017.contest.atcoder.jp/submissions/3789283
サプリメントの総数N<サプリメントの種類Mがあり得るということか。
味の種類とはいえ普通総数の中で数えるだろう・・・。
確かにN≧Mとは書いていないけれど、これは単純に文脈から読み取れる内容ではないのか。
学校のテストならさすがに文句言いに行くレベル。
気づけたのはなんとなくVectorの要素数を最大限まで持っていった場合になぜかAC取れたから。
とりあえず配列系は要素数最大まで取るのが正義なのだろうか。
累積和使ってさらに高速化もしてみたいけどまた今度。