naoya_t@hatenablog

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

過去問探訪

AtCoder Regular Contest 059

agwたんが埋めてたAtCoder過去問800点問題を一発AC出来て気持ちよかった

Codeforces: Manthan, Codefest 17

出てないけどagwたんから聞いた問題 B. Marvolo Gaunt's Ring http://codeforces.com/contest/855/problem/B真ん中の値を固定(1〜N)して左右をO(log N)でどうにかするのかなあと一瞬思ったんだけど サンプルケースを見ながら、ああ同じ数字を3回使ってもい…

CSAcademy Round #40 (Div. 2 only)

CS Academy agwたんと話してて、Dだけ見ようと思ったんだけど折角なのでA〜Cも見てみた (そして、解いたやつをvirtual participationに放り込んだ) 4問解くのに2時間弱かかってたので多分4完だけど、時間切られて焦りながらやるのとは違うんで参考記録

TCO17 Algorithm Round 2C

れじったけど起きられなくて タイムシフト参戦結果 --- 0pt(出てたら青落ち確定だったか)

HourRank 22

HackerRankさんのところのやつ タイムシフト参戦、というか後から(本番は1時間で3問らしいのでタイムリミット1時間で)問題を覗いてみた。

Codeforces Round #422 (Div. 2) [Virtual participation]

昨夜参戦できなかったCodeforces Round #422に朝からvirtual参戦(8:05am〜) いつも通りC→B→A、と行きたかったんだけど Cの制約を突破する糸口が掴めずパスしてB→Aの後Cに戻って解いて、まだ時間がたっぷりあったのでDへ。Virtual participationって、実際…

ARC077(タイムシフト参加)

昨夜爆睡中に開催されたAtCoder Regular Contest 077にvirtual参戦。時間内(1時間40分だよね?)に解けたのはDまで。Eは計算が合わず、食事後に修正して提出。 ↑始めたのが20:45過ぎ

ARC006-D アルファベット探し

みょんみょんがツイートしてたやつ競プロ全然やったことない人でも、業務でやってるならこれくらいは書けてほしいな、と思う問題がこの辺なんだけど、ちょっとハードル高いかもなあ、とは思ってる。https://t.co/yxKa9oIwUM— chokudai(高橋 直大) (@chokudai)…

Codeforces Round #419 (Div. 2) [Virtual participation]

れじってたけど起きられなかった回。 今日もC→B→A(→D)の順で。

Crayfish Scrivener (IOI 2012, day 1)

6月は永続データ構造強化月間(そういうことにしました)、ということで qnighy先生の Re永続データ構造が分からない人のためのスライド で紹介されていた、IOI 2012の"Crayfish Scrivener"を解いてみたメモ。

Codeforces Round #417 (Div. 2) [Virtual participation]

当日出られなかった回。Virtual participationというやつを初めてやってみた。(6/3)> Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests."…

SRM623 DIV1 Medium<450> : CatchTheBeat

DIV1 Medium Random Challenge第5回。

SRM562 DIV1 Medium<500> : CheckerFreeness

DIV1 Medium Random Challenge第4回。

TCO2015 Round2A DIV1 Medium<600> : FoxMeeting

DIV1 Medium Random Challenge第3回

SRM450 DIV1 Medium<500> : StrongEconomy

DIV1 Medium Random Challenge第2回。

SRM554 DIV1 Medium<500> : TheBrickTowerMediumDivOne

DIV1 Medium Random Challenge第1回。

DIV1 Medium Random Challenge

SRMのDIV1 Mediumの問題の中から、Practice Roomに入っていて、かつEditorialが存在するものをランダムに1問選んで解く DIV1 Medium Random Challenge というのを考えた。25分ぐらい考えて方針が立たなかったらEditorialを読む。方針が立っていたらそのまま…

SRM692 DIV1

参加してないけど3年前に書いたこんな記事 naoyat.hatenablog.jp のせいでagwたんから2-SAT教えてって無茶振りされて、とりあえず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がち…