ICPCを埋め始めましたよっと。 問題 このゲームには1番から N 番までの N 個のステージがあり，任意の順に攻略することができる． また，1から N まで番号付けられた装備があり，それらの装備を使用することでステージの攻略時間を短縮することができる． ゲ…

virtual。 結果 2完。Aは場合分けをややこしく考えていてバグらせた。Bの方が簡単。Cはひたすら実装がしんどかったが考え方から違った感じ。 A. Wilbur and Swimming Pool 座礁軸に平行な辺を持つ長方形の頂点の4つのうち、いくつかが失われた。もとの長方形…

今回はコンテスタントとして参加。 結果 初の全完。イェイ。 今回は☆3までだったのでなんとかなったという部分もある。 No.349 干支の置き物 12種類の干支の置物がある。それぞれの個数が与えられたとき、同じ種類の置物が隣り合わないように横1列に並べるこ…

virtualで参加。 結果 時間内にACできたのはAだけ。1:30くらいで降参してEditorialを見ました。 A～CはすべてPythonで解けるくらい実装は軽かったので、しっかり解きたかったところ。 A. Patrick and Shopping Problem - A - Codeforces 通り方はすべてで4通…

ロリハの練習問題として。 問題 Substring | Aizu Online Judge 制約 解法 ローリングハッシュ。となることを利用すると、各クエリに対してでハッシュが求まる。 前のハッシュに足したり引いたりで事足りるのでは？という考えも浮かぶが、ロリハは普通には割…

問題 TopCoder Statistics - Problem Statement 集合aは異なる正の整数からなる。aの部分集合に含まれる任意の要素の組(A, B)に対し、|A-B|を要素とする集合をDとする。Dがk-smoothとなるようなaの部分集合の最大の要素数を答えよ。ただしk-smoothとは、集合…

行列累乗は半環なら普通の演算以外でも使えるよ！という問題。 問題 数列 A はすべての要素が 32 ビットの符号なし整数で表現でき、その値は次のようにして決まる。 はじめの K 項 A1, A2, …, AK は入力で与えられる。 A とは別に K 項の数列 C1, C2, …, CK …

立命館大学競技プログラミング合宿(RUPC)2016に参加したので、参加記を書くアレします。 参加した理由 直接のきっかけは、@DarseinさんがRUPCのツイートをRTしていたのを見たことです。オンサイト楽しそうというのはDDPC等への参加者を見ていてずっと思って…

想定解賢いなあ…という感じ。 問題 D: ロボット - AtCoder Beginner Contest 027 | AtCoder 数直線の原点にロボットが置かれている。 はじめ、ロボットの幸福度は 0 である。 このロボットに命令列が与えられる。 命令列は次の 3 文字のみからなり、先頭から…

ひっかかったので書いとく。 問題 Problem - A - Codeforces 解法。 問題をよく読む。終了条件は「チャージが0になったとき」だけではない。 Game continues while both joysticks have a positive charge. Hence, if at the beginning of minute some joyst…

本番ではkenkooooさんにお任せしていた問題。 問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day1&pid=C 解法 次の例を考える。 a+b+b+b+c+c+c+d+d+d = 1*a+3*b+3*c+3*d (15文字) 左辺が入力、右辺が掛け算のみを用いた短縮形…

昨日解けなかったDP。 問題 AIZU ONLINE JUDGE 解法 DP。本番は貪欲法(Tを昇順にソートして、今までにかかっている時間が最小のスキャナーに順番に入れていく)で挑んだが、これは「1,2,3,4,5,6,7,8,9」というケースでWAする。(正解は15, 15, 15だが、この貪…

本番でctylさんが解法を編み出し、自分が実装した問題。 問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day2&pid=G 解法 DP。int dp[xの残量][yの残量] = このx, yで実現できる最大のブタメソの最大個数とすればよい。交換人…

「制約の有効活用」 問題 企業内の上司・部下の関係が木構造で与えられる。各従業員は自分よりも番号の若いいずれかの従業員の部下である。従業員ごとに利益の額が設定されている(これは正にも負にもなりうる)。さて、何人かの従業員を解雇することで企業の…

どこからLCAなんて発想が出てくるの！？と思った人用。 問題 木に辺を追加したときの閉路長を各クエリに対して求めよ。 制約 頂点数: クエリ数: 解法 辺 を追加したときの閉路長は、もとのグラフにおける点 と点 との最短距離を とすると、 (追加する辺の長…

Div.1 Easy 4題目。 問題 https://community.topcoder.com/stat?c=problem_statement&pm=14129 以下の条件を満たす集合が存在するか判定せよ。 要素は互いに異なる正の整数 要素数 は偶数 集合は 個の偶数と 個の奇数からなる 要素はすべて 以上 以下 以上 ]…

kenkooooさんのブログにSRM681 Div.1 Easy FleetFunding - ゆらのふなびとの類題として載っていたので。 問題 N両編成の電車をM人の整備士で点検する。i人の整備士は最初X_i両目の車両にいる。車両の点検には時間はかからないが、隣の車両に移動するには1分…

Div.1 Easy 3題目。 問題 https://community.topcoder.com/stat?c=problem_statement&pm=14104&rd=16651 1からmまでの番号がつけられたm種類のパーツがある。宇宙船を1隻造るにはm種類のパーツすべてが1個ずつ必要である。また、パーツを生産するn個の工場が…

ちょくだいさんの本（↓）に載っていたので解いた。 最強最速アルゴリズマー養成講座 プログラミングコンテストTopCoder攻略ガイド作者: 高橋直大出版社/メーカー: ソフトバンククリエイティブ発売日: 2012/09/29メディア: 大型本購入: 9人 クリック: 319回こ…

問題 https://community.topcoder.com/stat?c=problem_statement&pm=14104 グラフ上にfriendship chainが存在するか判定せよ。ただしfriendship chainとは、異なる点A, B, C, D, Eに対し、AとB, BとC, CとD, DとEがそれぞれ隣接するようなグラフのことである…

前回のするめでめでたくDiv.1に上がれたので、今日からDiv.1Easyの問題を解いています。 次回何とか1完できることを目指して。 問題 https://community.topcoder.com/stat?c=problem_statement&pm=14174 石が縦に積まれたn個の山が、円状に隣り合って並んで…

yukicoderで出題していただいた問題の解説です。 問題 No.346 チワワ数え上げ問題 - yukicoder 与えられる文字列 の部分列(連続でなくともかまわない)のうち、"cww" となるものの総数を求めてください。 制約 解説 計算量を落とす過程に沿って説明していきま…

yukicoderで初めて作問させていただいたので、その問題の解説です。 解説にはC++, Pythonのサンプルコードをつけてあります。 質問等あればコメント欄か @yurahuna まで。 問題 No.345 最小チワワ問題 - yukicoder 与えられる文字列の連続した部分文字列のう…

他のブログを見て「なんで交差判定"2回"してるの？？」と思った人用の記事。 問題 abc016.contest.atcoder.jp 多角形と、線分が与えられる。線分により、多角形はいくつの領域に分断されるか。 解法 公式の解答を見ると、(求める数) = (線分と交差する辺の数…

解くのに3時間かかりました(弱い) 問題 abc025.contest.atcoder.jp 3*3マスの盤に、先手と後手が順に○と×を埋めていく。盤面が埋まったら次のように得点を配分する。横に隣り合うマス、縦に隣り合うマスの計12組のペアにそれぞれ得点が設定されている。各ペ…

想定解と違うっぽかったので書いておきます。（ダイクストラで解いた） 問題 abc022.contest.atcoder.jp グラフが与えられるので、地点1から出発し地点1に戻ってくるような閉路が存在するとき、その最小の重みの和を求めよ。そのような閉路が存在しないとき…

「やられた！」と思った問題。こんなんがCODE FESTIVALの決勝でも出るんだなあ…。 問題 yurahuna2016.contest.atcoder.jp 元問題はこちら code-festival-2014-final-open.contest.atcoder.jp 与えられる整数Aがパスカルの三角形に含まれるなら、その段数・行…

さてB問題。これが一番時間かかった。 問題 yurahuna2016.contest.atcoder.jp 元問題はこちら code-thanks-festival-2014-a-open.contest.atcoder.jp 石像が南北方向にR行, 東西方向にC列並んでいる。最初はすべて南を向いている。左上を(1, 1)とする。 儀式…

2月14日――世間では「バレンタインデー」と呼ばれ、恋に焦がれる者たちがチョコを渡しあう今日この日――私は22歳の誕生日を迎えながら実家で一人卒論を書いていました。 バレンタインらしいことも誕生日らしいことも特になく、しかも誕生日翌日が卒論提出日と…

「なるほど！」と思った問題。わかってしまえば簡単かも。 問題 arc009.contest.atcoder.jp 0～9の数字の、新しい大小関係が与えられる。この大小関係に沿って、与えられるN個の数を昇順にソートせよ。 解法 初めてこの問題を見たときは「比較関数を作って、…