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

naoya_t@hatenablog

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

Practice Room

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完全問題でおなじみ…

SRM575

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

SRM583 (new compilers) DIV 1

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

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で出てこないのがある) たぶん自分の使い方…

SRM581

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

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

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

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

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