読者です 読者をやめる 読者になる 読者になる

naoya_t@hatenablog

いわゆるチラシノウラであります

TopCoder

SRM620

SRMに連続参戦するの久しぶり。o— +0/-0 211.96pt 331st 1527→1577 とりあえず黄色キープ #srm620— naoya t (@naoya_t) May 10, 2014 とりあえずレーティング少し上げた。(Volatility少し下げたか) 黄色キープ。 === 250-500-800て。(Hardは開いてない) …

SRM619

久々に参加するSRM。こないだのTCO R1CでVolatilityが上がってるから、ここで良い点を出せばスムーズに黄色に戻れるかも?(0完だと逆に急降下のおそれが)でox- +0/-0 232.80pt 178th 1433→1527 黄色に戻れたヤター— naoya t (@naoya_t) May 5, 2014 去年の8/1…

2014 TopCoder Open Algorithm Round 1C(無事通過しました)

今度こそ通過 ooo +0/-0 1352.95pt 80th 1320→1432レーティングも少し取り戻せました。 Round2でお会いしましょう! (Round2はチャンス3回:(A)5/18 (B)6/8 (C)7/6 それぞれ日本時間の日曜1am*)

2014 TopCoder Open Algorithm Round 1B〈タイムシフト参戦記〉

registerしておきながら寝倒したので、翌朝Practice Roomでタイムシフト参戦してみた記。 Round1Cでお会いしましょう。200-600-900て何 Easy (200) SpamChecker 問題ちゃんと読んでなかった。一瞬でもスコアが負になったらSPAMでいいのね。600を通してたのが…

2014 TopCoder Open Algorithm Round 1A

GCJ QRの最中の開催。GCCが動かないの忘れたままregisterしちゃって 慌ててXcodeをインストール。 コーディング時間開始30秒前にインストール完了!

SRM593

駄目ぽよ Easy (250): HexagonalBoard 高々3色 最大クリークサイズか、 サイズ2のクリークを繋いでぐるっと回ってきたら3色要る場合があるよね (要するに二部グラフにできるかどうか) 126.39点→WA 提出コード:

SRM588

久々のSRM参戦かも。いつの間にかPythonが入っていたりC++11になっていたり。 250-450-1100compileしたら「typeof is 何」って言われたのが今日のハイライト。慌てずにautoに書き換えてコンパイル通った #srm588— naoya t (@naoya_t) August 12, 2013 typeof…

SRM585

寝倒した…ので過去問としてチャレンジ Easy ("TrafficCongestion", 250) treeHeight treeHeight >= 2 のとき: 葉にあたる町が 2^(treeHeight) 箇所ある 葉を左から入って最初の町で右折してすぐに葉へ。これで 2^(treeHeight-1) 台消費 で下2段が消えるので…

2-SATと強連結成分分解

ふと2-SATの事が気になって、復習がてらPractice RoomでSRM464のDiv1 Medium問題を開いてみた。(ちなみにSRM464には出場している)SAT (充足可能性問題, SATisfiability problem) についてはここの読者の皆さんはご存知とは思います。NP完全問題でおなじみ…

SRM584

7/10 20:00JST〜250-600-900 こういう時って250の早解き勝負らしいです青と黄色だけの部屋。チャレンジフェーズゆるゆる。 Easy ("Egalitarianism", 250) union-findで全員が同じ島にいることを確認(いなければ-1) メンバー相互間の距離を全部出すやつある…

SRM575

Easy ("TheNumberGameDivOne", 250) 1e18までの素因数分解とか無理っしょ 別途シミュレーションしてみて規則性を探る系

SRM583 (new compilers) DIV 1

Practice Roomsの#893にそんなタイトルのがあったので覗いてみる。 問題はSRM583と同じで、コンパイラが昨日のTest SRMと同様の構成らしい。Pythonが使えるのでPythonで書いてみようか。

Test SRM

unratedなSRMがあったので出てみた。 The solutions are executed at Amazon EC2 m1.medium VMs.Compiler versions:C++ – g++ (GCC) 4.4.6 20110731 (Red Hat 4.4.6-3) Compilation options: --std=c++0x -W -Wall -Wno-sign-compare -O2 -s -pipeJava – jav…

2013 TCO Marathon Round 3 "CirclesSeparation"

TCO13MMR3 (6/5〜19) に参戦しました。MM参加は通算6回目。 [6/26更新] 最終順位36位。\TシャツGET☆-(ノ゚Д゚)八(゚Д゚ )ノイエーイ/ http://community.topcoder.com/longcontest/stats/?module=ViewOverview&rd=15683

SRM576

危うく三日坊主になるところでしたがこの回は 256-576-900 という変態的な配点です Easy("ArcadeManao", 256) プラットフォーム検出(UnionFind): 水平方向にXが隣接している時だけunionSet 各プラットフォームから梯子で昇降できるプラットフォームへの距離…

SRM577

Easy ("EllysRoomAssignments", 250) 最初、トップから20人ずつ取ってて数あわないなあとか思ってた →case 4で{11人,10人}に分かれるのを見て間違いに気づいた。 サンプルケースが親切なので、言われたとおりにやるだけの問題。

SRM578

Easy ("GooseInZooDivOne", 250) ローカルで大丈夫っぽかったので投げてみたら、最大盤面(50x50)を'v'で埋め尽くしたケースでTLEが出た。ローカルでそのケースをやっても -O2 なら333msecで終了するのになんで?もしかして:サーバ激遅

SRM579

Div1Easy過去問を1日1問解いてみるやつ WAだったらもう1問、にしようか Easy ("UndoHistory", 250) さくっと書いてサンプルケース通ったやつを投げてWA {"absolutely", "abs", "absolute"}で引っかかるし。 バッファの続きから行ける場合にバッファを使って…

SRM580

リハビリの為、飽きるまで1日1問解いてみようかと Easy ("EelAndRabbit", 250) Spaghetti Sourceの区分木(segment tree)を使って書こうと思ったらうまく行かなかった。 (半開区間で探索していた罠は躱せたがqueryで出てこないのがある) たぶん自分の使い方…

コードテンプレート加筆 + TZTesterの文言変更

assert() を使おう SRMがドジっ子アピールの場となっている現状を打破すべく #define NDEBUG $BEGINCUTS #undef NDEBUG $ENDCUTS #include <cassert>を追加。 全体だとこんな感じ→ https://gist.github.com/naoyat/5821991これでローカルテストの時だけassert()が使え</cassert>…

SRM撃墜大好きっ子に贈る:二分探索問題の撃墜 〜慎重に撃墜ケースを検討すべき一例〜

SRM582 Easy(250) "SpaceWarDiv1" 問題意訳 魔法少女(複数)と敵(複数)がいる。 魔法少女は自分と同等以下の敵を倒せるが、1人倒すたびにソウルジェムが濁っていく。 敵は全て倒したいが、ソウルジェムの濁りが特定の少女に集中し魔女化してしまうのを避…

SRM581

朝、起き抜けにやってみた Easy ("SurveillanceSystem", 250) 鳩ノ巣原理みたいなやつ。なんか時間かかった答え合わないなー、問題文に読み落としてる制約とかあるのかなー、 と思ってうんうん唸ってた朝食後に見直したらExpected:とReceived:を逆に解釈して…

SRM583

あんまりratingが落ちる心配とかせずに出れるだけ出たほうがいいかも、と思い、引き続きSRMに出てみた。 Easy ("TravelOnMars", 250) 解けた。 速解き系なのに提出のんびりしすぎ。ダイクストラのライブラリをコピーしてきて試すのに時間かけすぎ Medium ("T…

SRM582

久しぶりにSRMに出てみた。 Easy ("SpaceWarDiv1", 250) 二分探索が間違っている事に気づいたのに(あれ、これでも通るんだーとか思っちゃって)再提出せず 区間 [1, LONG_LONG_MAX] で二分探索したらいけない理由は、1のケースを拾いそこねるからではなく、…

2013 TCO Marathon Round 2 "FragileMirrors"

TCO13MMR2 (5/1〜15) に参戦した話を書きたいのだけれどコルンさんの とりあえず、今回のTCO13MR2は、マラソンマッチ入門にちょうどいい気がする。初めての人向けというか。そのぐらい入り口のハードルは低い。上級者向けに奥が深いかどうかはまだ分からない…

SRM541 - Redcoderキラーセット

o-- 96.62点 434位 1575→1586 writerは@semiexpさん。開戦前のアリーナで (」・ω・)」うー!(/・ω・)/にゃー!」 とか連投してたら日本人が次々(」・ω・)」うー!(/・ω・)/にゃー!言い始めて楽しかった。感染力高い。 naoya_tさん這い寄られすぎでは— …

TCO12 Algorithm Online Round 2A

4/22(日) 1:10am〜 上位50人が通過、という事でやる前から通過あきらめムード Challenge Phaseの最後の3分がChallengeできなかったらしくてRoundの有効性について審議中 ChallengeそっちのけでMedium問題考えてたわけですが x-- 0点 462/1362位 Easy(300) Sw…

SRM540 - Easy落ちまくり回

Room41 - LayCurseさんの部屋 Challenge Phaseでは落とされなかったけれどSystem Testで落ちて0点 1655→1600 Easy(250) ImportantSequence.cpp 途中でオーバーフローの可能性に気づいてlong longに切り替え 50000000000000000LLとか打ってるけどゼロの数かぞ…

2012 TCO Algorithm - Round 1B

TopCoder Openの第1ラウンド(予選みたいなもの)の2回目。 1回目を寝倒したので今回は頑張って起きて参加。日本時間1amから。赤い人から灰色の人まで満遍なく揃ったRoom1。 EasyとMediumが通って 204.52 + 451.30 = 655.82点。部屋2/24位、全体122/1948位 …

SRM537(欠席回)の問題を解いてみた

275-500-925て何その配点... Div1 Easy(275) KingXNewCurrency 場合分けして考える A,B,Xの相互間のGCDで? 綺麗に整理できない。なんか漏れそう。 範囲も[1..200]とかだし総当たりでよくね? (ちょっと多めに取って)[0,39999]の範囲でpA+qBで表現できる数…

「問。次のDiv1 Medium提出コードはWAなのに撃墜されませんでした。編集距離1でACにしてください。」(SRM536 配点:50)

Easy(250): AC Medium(500): WA Hard(1000): opened 14/20 in the room, 513/860 in Div1 1610 -> 1568500 はChallenge phaseまで耐えたけれどfailed system test。 編集距離1で通るような話だけれど(凡ミスではなく)考えが足りなかったせい。 Easy (250):…

GCD - cafelierさんのコードから

cafelierさんの500のコード見てたら LL gcd(LL a, LL b) { while(a) swap(a, b%=a); return b; } あ、そうか。swapってそう使えるのか。短くていいな。

SRM534 − 今日は出ましたがrating減

Easy(250): ◯ Medium(500): 撃沈 Hard(1000): 開いた 12/20 in the room, 414/717 in Div1 1652 -> 1610なんか最近EasyはDP有りで、Mediumはかなりうまく書かないとTLE/MLEになるぎりぎりの設定になってる印象。 Easy (250): EllysCheckers こういうNim系が…

SRM533 - 深夜開催のSRMがちょっと辛い今日この頃

最近ちょっと早寝早起きサイクルになってるので2amからとかちょっときついですね。というわけでSRM533の問題を見てみた話。配点的には250-500-1000ですが・・・ 出てたら430位ぐらいでレーティング横ばい〜微減、かな。 Div1 Easy(250) CasketOfStar 250がち…

SRM532 - 寝倒した先日の問題を見てみた

300 - 450 - 1000 ってまた気持ち悪い配点だけれど、本番じゃないしMediumから手をつけてみようかと。 Div1 Medium(450) DengkleBuildingRoads まあどう見てもDPなんだけど BAD END 必ず偶数、ってことはオイラー路だよね… なんか輪ゴムを釘に巻いていくパタ…

nCk mod mの計算(※mは素数とする)

TopCoder用コピペメモw 1つだけ求めたい場合 x/y mod m をフェルマーの小定理で typedef long long LL; const LL MOD = 1000000007LL; // LL add(LL x, LL y) { return (x + y) % MOD; } // LL sub(LL x, LL y) { return (x - y) % MOD; } LL mul(LL x, LL …

SRM531 - 1年3ヶ月ぶりのTopCoder参戦

1/31 21:05〜 久しぶりすぎて緊張する300-500-1000だ Easy300点は不吉 Div1 Easy(300) : NoRepeatPlaylist DPで解けるか?…なんか可能なstateの数が多すぎて手に負えない M曲ずつブロックにして…違うな。それだと連続するかもしれない とりあえずM=0の場合を…

SRM530:出てないけど問題を見てみた

TopCoder SRMには1年ぐらい参加してなくて、今使ってるMacBook Airではまだ一度も参戦してないので動作環境整備から。TopCoderに参加して何が良いかっていうと、単にパズルとして面白いってのもあるんだけれど、自分より若い人達が優秀であるという事実(そ…