競技プログラミングにハマるプログラマのスレ 9 [無断転載禁止]©2ch.net

■ このスレッドは過去ログ倉庫に格納されています
1仕様書無しさん
垢版 |
2017/04/25(火) 11:02:10.22
プログラミングコンテスト(プロコン)やオンラインジャッジや競技プログラミング(競プロ)やCTFなどを楽しんでる競技プログラマ(競プロer)の雑談スレ
競プロイベントや競プロ問題や有名競プロerや競プロでよく使うアルゴリズム等について語りあったり、競プロ関連の質問相談なんでもおｋ
競プロ初心者でググっても解説読んでも分からないことがあったらスレの競プロの先輩方に訊いてみるのも手だよ(分かりやすい解説サイトとか書籍とか教えてくれるかもしれないよ)
次スレは>>950

# オンラインジャッジ・コンテストサイト
## 日本語
yukicoder https://yukicoder.me/
AtCoder https://atcoder.jp/
AIZU ONLINE JUDGE (AOJ) http://judge.u-aizu.ac.jp/onlinejudge/
## 英語
TopCoder
Single Round Match (SRM) 関係リンク集 http://codeforces.com/blog/entry/21879
Marathon Match (MM) https://community.topcoder.com/longcontest/?module=ViewPractice
※TopCoderは初参加までの手順が煩雑です。まずはググってみて、それでも分からなかったらスレで聞こう！
Codeforces http://codeforces.com/
Google Code Jam https://code.google.com/codejam/
Facebook Hacker Cup https://www.facebook.com/hackercup/
CodeChef https://www.codechef.com/
HackerRank https://www.hackerrank.com/
Project Euler http://odz.sakura\.ne.jp/projecteuler/ https://projecteuler.net/

>>2にテンプレ続く
2017/05/13(土) 04:40:23.80
AtCoderにそんな糞問が出るようになったらおしまいだ
2017/05/13(土) 05:12:51.92
現状だと問題傾向をどう変えてもC++最強は変わらなさそうだけど
anacondaが入るとPython最強の問題も出題出来るようにはなるね
2017/05/13(土) 05:57:18.17
Java/C#/Go辺りでも通るように設計されてない問題は現代でも許されてないよ
2017/05/13(土) 06:22:33.53
そういえばこの前yahooのプロコンか何かでC++のClangでやると10^10の愚直解が通ってしまうとかいう問題があったような
2017/05/13(土) 07:42:38.64
>>583
Crystal や Nim もその辺に加われるようになればさらに面白いね

俺は今はD言語で参加してるけど、余計なマクロ群を書かなくていいのでキレイな感じがして
書いてて気持ちいいよ
2017/05/13(土) 09:08:53.87
オーケーグーグル、今日の競プロスケジュール
2017/05/13(土) 09:52:57.48
>>593
30分でABC全完
2017/05/13(土) 10:06:54.05
ABCに初参戦する
とりあえずC問題完遂を目指す
2017/05/13(土) 11:06:17.67
>>594
ハードルたけぇなw
2017/05/13(土) 18:30:02.61
よしこーなー
2017/05/13(土) 20:48:05.53
1問しかできなかった｡ﾟ( ﾟஇωஇﾟ)ﾟ｡
2017/05/13(土) 20:57:10.10
今夜は全完の予感がする
2017/05/13(土) 22:41:01.06
3問しかできなかった｡ﾟ( ﾟஇωஇﾟ)ﾟ｡
2017/05/13(土) 22:43:08.83
Dは解けそうな気がしたが気がしただけだった(´・ω・｀)
602仕様書無しさん
垢版 |
2017/05/13(土) 22:45:02.98
Dがいくつか通らないまま終わってしまった・・・・
2017/05/13(土) 22:47:00.74
ABCにRubyに初参戦
2問しか出来んかった･･････
三問目の問題がTLEに阻まれてどうしてもクリアできんかった

正解者のコード見て、最後の時に上手く処理かませると時間短縮できるのかこれ
普通にputs ans[k-1]と何が変わるのか分からんぞいぞい
2017/05/13(土) 22:50:06.25
>>603
O(sum(b))でソートしたの？
2017/05/13(土) 22:51:47.77
あ、O()はいらんわ
配列に sum(b) 個いれたのかな
606仕様書無しさん
垢版 |
2017/05/13(土) 22:53:35.64
Cが終わった瞬間に二次元配列でやればいいと気づいた
悔しい
2017/05/13(土) 23:01:40.33
WAがめっちゃ生えるコンテストだった…
608仕様書無しさん
垢版 |
2017/05/13(土) 23:13:28.56
ベルマンフォードまでは一瞬で思いついたけど正解できなかった・・・・。
BF２回でよかったのかorzorzorzorz
2017/05/13(土) 23:14:12.98
>>604
コード自体はこんなん
http://ideone.com/a6A5jW

で、スレと他人のコード読んで気付いたわ
これ2次元配列かハッシュ使ってやれば
バカ正直に配列に全部入れる必要ないやん、俺アホだ
なんで気付かなかった
2017/05/13(土) 23:24:52.91
>>609
これ途中でbreakしてしまうとTLE以前にWAになると思う
aが小さい順で入力されるならいいけど、その制約はないから
2017/05/13(土) 23:27:51.84
10^10個の配列とかMemory Limit Exceeded だろ
2017/05/13(土) 23:36:18.25
Cの2次元配列やハッシュを使った解法って
どうやるのでしょうか…？
613仕様書無しさん
垢版 |
2017/05/13(土) 23:44:53.80
>>612
説明下手だけど(数値、挿入回数)で二次元配列作って、数値の部分で昇順ソートした後、挿入回数の部分がK番目のとこ探す感じだと思う
2017/05/13(土) 23:49:24.42
ハッシュじゃなくてバケットソートのことだと思う
2017/05/13(土) 23:55:15.31
>>613>>614
ｱｱ! 分かりましたありがとうございます
613に似ていてpairを使って解いていました
614は解説にありましたね
2017/05/13(土) 23:55:16.48
解説の疑似コードが二次元配列の方法
分かりやすいと思うからrubyで書き換えてみたら
2017/05/13(土) 23:57:06.08
http://ideone.com/GsIrCT
二次元配列で書き直したらすんなり通ったわ
しかしsort!とsort_by!で2.4倍ぐらい実行速度が変わったから驚くわ

しかしsort!がびっくりするぐらい遅い（これでも一応テストケースは通るけど）
ちょっとした書き方の違いですげえ差が出るんだな
プログラム初心者としてはまだまだ勉強不足って実感できちゃうのが辛い
2017/05/14(日) 00:09:35.85
ABC久々に（初めて？）出場した。何とか全完できた。
娘が嫁と風呂に入ったスキをついて出場。娘が上がってくるまでに解き終わらず、体拭いたり、保湿クリーム塗ったりしながら、DでWAになった理由を考えていた。
Bellman Fordの実装の詳細忘れてて、勉強になった。
負（正）の閉路があったとしても、目的地にたどり着く経路上に、その閉路が無ければ、影響しない、っていうのが、盲点だった。
2017/05/14(日) 00:11:55.34
トップの人は10分で4完……
努力してもそこまで到達できる気がしないぞ
見た瞬間に答えが分かってコーディングしながら
その間に次の問題読んでるんじゃなかろうかｗ
2017/05/14(日) 00:59:20.15
少なくともサンプルのチェックはしてないだろうな…
2017/05/14(日) 01:25:19.38
>>617
sort_byは最初に全部mapするから評価値への変換がO(n)回なんだろうな
2017/05/14(日) 01:37:59.65
使う標準ライブラリのデータ構造/アルゴリズムは
計算量を調べておくのがいいよ

言語によってはドキュメントに書いてなかったりするのかな
さすがにそれはないと信じたいが
2017/05/14(日) 01:42:00.75
10分で終わらせるようなガチ勢は多分、サンプルチェックが自動で済むようなシステム自作してる
2017/05/14(日) 01:45:53.52
>>622
LLとかだとあるほうが珍しい
実装を読むか実験か経験で補う
2017/05/14(日) 02:44:11.37
何人も作って公開してるから興味があればググれ
2017/05/14(日) 10:41:21.98
>>623
ファイルの変更をチェックして自動でコンパイル、実行、サンプル入力まで走らせるような感じかな
作ってみようかな
2017/05/14(日) 12:34:05.26
wata先生はGCJをRustでやってたのかw
2017/05/14(日) 13:11:37.85
自動サンプルチェックはoj.pyが便利
サイトによっては提出まで自動化できる
Topcoder限定ならGreedも便利
2017/05/14(日) 17:23:26.82
コンテストカレンダー見たら、競技プログラミングの時間帯が21時とか23時とか寝てる時間だから、競技プログラミングオンラインで参加できないんだけど
2017/05/14(日) 17:56:35.40
インドあたりに引っ越したら出られるんじゃね
2017/05/14(日) 18:20:50.28
https://github.com/kyuridenamida/atcoder-tools
2017/05/14(日) 18:36:34.92
>>630
インドなんて絶対住みたくない
2017/05/15(月) 00:52:04.91
>>631
さすがきゅうりさんは期待のホープだな
2017/05/15(月) 02:37:52.19
>>633
>>625
2017/05/15(月) 14:18:07.14
だいぶ前にこのスレにWindowsXPユーザがいたが、流行りのランサムウェアの被害にあっていてほしい
636仕様書無しさん
垢版 |
2017/05/15(月) 15:23:55.15
やっぱり時代はWindows10だな。
Bash on WindowsでLinux環境も楽々作れるし。
2017/05/15(月) 20:12:10.24
Bash on Windowsはまだ遅いのとstack limit増やせないんのがきついんだよね
競プロ目的にはまだ厳しいと思うのでVMWareを使っている
2017/05/15(月) 21:07:30.32
とりあえずyukicoder用自動サンプルチェックを作ってみた
639仕様書無しさん
垢版 |
2017/05/15(月) 21:09:43.41
chokudaiが生主みたいなことやってるんだけど
アイドルにでもなりたいのかな？
2017/05/15(月) 21:11:40.77
何年も前からやってるよ
641雪風
垢版 |
2017/05/15(月) 21:45:04.22
（絶対に言うなよ）
自意識過剰な奴が多い
2017/05/15(月) 23:33:04.89
生主ではないけど最近コンテスト中のスクリーンキャストは撮るようにしてる
2017/05/16(火) 01:34:35.73
学生も社会人も全員集合！ヤフー史上初のプログラミングコンテスト「みんなのプロコン」開催レポート #みんぷろ
http://linotice.tumblr.com/post/160544710799/20170511
2017/05/16(火) 04:25:21.89
>>643
なんか運動不足っぽいけど大丈夫かな？
https://68.media.tumblr.com/d71f9f191096122818f81de2f0190d6d/tumblr_inline_opqf55siuV1utbyrh_500.png
トップが成人病になってAtCoder終了したらしゃれにならないぞ
2017/05/16(火) 07:48:41.07
>>642
誰かに見せる目的で撮るの？それとも後で見返したりするために撮る？
2017/05/16(火) 09:33:49.33
>>645
自分の場合は見返す目的かな
どこでどのくらい時間を無駄にしたかを調べられるから便利かもしれないと思って始めた
今のところそこまで活用できているわけではないけど
2017/05/16(火) 17:44:03.76
>>646
見返す用か、なかなか動画見て無駄を改善するってのは難しそうだなあ
ゲームとかだと動画見て反省会ってのは有効だけど、競プロの場合は考える（＝動画的に変化が無い）時間のほうが長いだろうからどうなんだろうとか思った
強い人だと考える時間が短いから有効なのかな
2017/05/16(火) 18:37:57.71
スマホで参戦してるんだけど、PCだとリアルタイムに順位の変動見られたりする？
1分毎にJavascriptなんかで、フレンズの順位表が上下するみたいな
それ観ながら発奮するみたいな
2017/05/16(火) 19:13:28.25
>648
質問の趣旨とは違うけど、スマホじゃコーディングは厳しいから、PC使いなよ。
2017/05/16(火) 19:30:09.65
サイトの機能としては実装されてない
自動でブラウザ更新するようにすれば個人でできるとは思う
2017/05/16(火) 19:56:01.96
スマホでコーディングしてる人とか始めてみたわ
出来るのかあれ
652仕様書無しさん
垢版 |
2017/05/16(火) 20:34:25.26
ABC061のD問題 Score Attack
について質問です。

スタートからゴールまでの経路に含まれる可能性のあるノードを
BFSかDFSで列挙してから、ベルマンフォードを使うのでしょうか？
2017/05/16(火) 21:29:02.79
>652
解説読むと、
ベルマンフォードで、N-1回更新して、この時点での距離を記録しておき、
再度N回更新して、距離が変わっていたら負閉路あり、とする。

後半はN回更新しなくても、一回更新するだけで、テストケース通ったけど、嘘解法なのかもしれない。
2017/05/16(火) 22:22:06.16
閉路が M-2 くらい長くて頂点の順序が逆順の時にWAになると思う
2017/05/17(水) 01:00:34.99
閉路の長さはn以下だから、Bellman-Fordのn回目の更新で負閉路は検出できる
どんな最短パスも長さがn-1以下なので、負閉路がないならn-1回目で止まる
2017/05/17(水) 01:17:48.80
>>655
経路に関係ない閉路はあっても問題ない
最終到達点に閉路が影響するかどうかを判定しなければいけない
2017/05/17(水) 01:47:36.67
スマホコーディングと聞いて失笑しつつGoogle Playで調べたらEmacsもVimもあったわ
どの程度需要あるんだこれ
658仕様書無しさん
垢版 |
2017/05/17(水) 01:55:22.85
こむぷーたーの難しい側面を隠したモバイルOSだけど、普及度が高くてかつ、
プログラミング行為の重要性が認識されている（）ので、そういう需要があるのではｗ
2017/05/17(水) 02:15:49.47
さすがにスマホサイズでコーディングはありえんからAndroidはモバイル限定じゃないって事かと思った
2017/05/17(水) 03:52:07.41
自ら打ち込んだ思考の柵に囚われてはいけない
2017/05/17(水) 08:48:06.90
>>656
閉路のある場所がわかるので、そのなかに頂点nに到達できる頂点が1個以上あるかどうか判定すれば良い
(辺の向きを逆にしたグラフでbfs)
もしかしたら解説とは違うかも
662仕様書無しさん
垢版 |
2017/05/17(水) 11:36:36.92
https://www.hackerrank.com/sinapusu2002-2
2017/5/17の12時から開催する個人主催競技プログラミングのコンテスト１５問。
流石に作りすぎておかしな問題も交じってるかもしれませんがよろしく。
（すいません作問しすぎて品質保証がちょっと怪しいです）
ハッカーランクという競技プログラムのサイトで開催。
ハッカーランクに登録してご参加ください。
663仕様書無しさん
垢版 |
2017/05/17(水) 16:27:34.64
キーボードを挿し込んだAndroidタブレットかもしれないだろ
2017/05/17(水) 19:57:18.30
>>662
どの程度のレベルの問題ですか？
2017/05/18(木) 05:48:48.39
最近レス先ミスってるのをよく見るが専ブラの不具合とかあんの?
2017/05/18(木) 05:56:55.74
や、バグってるのは俺が使ってるAndroidのブラウザのようだ
忘れて
2017/05/19(金) 22:35:33.46
次の ABC/ARC のD問題は部分点があるみたいだから
ちょっとだけレート上げられるかもしれん
完全に解ければ言うことなしだが勉強が足りない！！！
2017/05/19(金) 22:44:15.52
確かに部分点あるけど、Cが400点あるから実質D問題が2問あるようなものでいつもよりきつくないかこれ
2017/05/19(金) 22:54:44.80
部分点あるやつは難しいんじゃね？
解ける気がしない(´・ω・｀)
2017/05/19(金) 23:02:32.33
俺は C問題を落とさない
多分しないと思う
しないんじゃないかな
ちょっと覚悟しておこう
2017/05/20(土) 01:05:52.47
たまに難易度がC>Dみたいなときもあるから油断できない(´･_･`)
672仕様書無しさん
垢版 |
2017/05/20(土) 07:29:52.52
>>652
ベルマンフォードで
N-1回のループでの、ゴールまでのコスト
2N-1回のループでの、ゴールまでのコスト
この2つを比較して、等しければ、それを出力
等しくなかったらinfを出力すればよい
673仕様書無しさん
垢版 |
2017/05/20(土) 07:30:08.18
>>652
ベルマンフォードで
N-1回のループでの、ゴールまでのコスト
2N-1回のループでの、ゴールまでのコスト
この2つを比較して、等しければ、それを出力
等しくなかったらinfを出力すればよい
674仕様書無しさん
垢版 |
2017/05/20(土) 13:14:40.64
AtCoderの解説リンクは
解説PDFだけでなく
解説動画にもリンクを張ってほしい

YouTubeで解説動画探すの面倒なので
2017/05/20(土) 20:46:37.79
今日こそはランク上げるぞ！
2017/05/20(土) 20:57:30.12
よしこーなー
2017/05/20(土) 22:42:36.80
C問題は無事解けた
ほっとした
2017/05/20(土) 22:50:10.08
C, D 行けた。良かった。

次は、codeforces #415が、3:05amからだね。
仮眠を取るべきか、悩ましい。
679仕様書無しさん
垢版 |
2017/05/20(土) 23:11:03.32
チョコバーを深読みして定数オーダーのクソコードで解いたけど場合分けに苦戦してやたら時間食ってしまったorz
2017/05/20(土) 23:24:42.11
C問題は定数で解けるのか
Fも制約甘かったしDも典型だから、今回はAGCじゃないからかAtCoder本気出してないな
2017/05/20(土) 23:37:45.01
忘れてた。(´・ω・｀)
2017/05/20(土) 23:43:18.88
次はTCOだぞ
2017/05/21(日) 02:48:32.74
次はCodeforcesだぞ
2017/05/21(日) 02:56:22.54
流石に眠いぞ
2017/05/21(日) 03:04:47.18
よしこーなー
2017/05/21(日) 03:13:58.85
TCOもアットコも寝過ごしたゾ…
2017/05/21(日) 05:54:36.35
同じく寝過ごした、
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況