Div.1 Medium 初AC！ 問題 TopCoder Statistics - Problem Statement ロボットに以下の命令を送ることができる。 その場で左(右)に向きをx度変える(xは1以上359以下の整数) 前(後ろ)に距離xだけ進む 使える命令文(「左に50度曲がる」など）が与えられるので…

気づけばとても簡単な問題。 問題 TopCoder Statistics - Problem Statement いくつかの格子点が与えられる。原点からスタートし、与えられたすべての格子点を1度以上通り、与えられた格子点のどこかで終了するパスを考える。このようなパスのうち、長さの偶…

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個の山が、円状に隣り合って並んで…