問題ページ D - 2017-like Number 考えたこと f(A) = (1からAのうち条件を満たす数) とすれば f(r) - f(l-1) として計算できるのでf(A)を前計算する 10^5までの素数をエラトステネスの篩で列挙して、条件を満たす数を1~10^5までで探せばよさそう 条件を満た…

問題ページ C - Special Trains 考えたこと 乗れる電車のうち一番はやい電車に貪欲に乗っていけばよさそう t秒目に駅に来た時 s + k*f >= t を満たす最小のkの電車に乗ればいい 変形すると k >= (t-s)/f k = max(0, ceil*1と決定できるのであとは貪欲にえい …

問題ページ C: 節約生活 - AtCoder Regular Contest 007 | AtCoder 考えたこと 愚直に全探索するとO(N^N)になりそう 多少枝刈りできそうだし10^10なら通るのでは？と思って投げるとTLEじゃなくてWA 全てのテレビが付くまでは視聴できない時間が合ってもいい…

問題ページ C - 器物損壊！高橋君 考えたこと N回見た拡張dijkstra d[y][x][何回壊したか] = (最短距離) でdijkstraをする #include <bits/stdc++.h> using namespace std; typedef long long ll; #define int ll typedef vector<int> VI; typedef vector<VI> VVI; #define FOR(i, a,</vi></int></bits/stdc++.h>…

問題ページ C - 平均値太郎の憂鬱 ( The melancholy of Taro Heikinchi ) 考えたこと 数式を書いてみると X/Y = (N(N+1)/2 - M) / N N = Y/2, M = (Y^2+2Y-4X)/8 N,Mが整数かつN < Mの条件を満たすような(X, Y)の組を探す N<Mの条件を満たす間(X, Y) (2X, 2Y) (3X, 3Y) … について探索していく これで出すとTLEしたのでMがマイナスになる部分を枝刈りする (kY)^2 + 2kY - 4kX > 0 を満たすように整数kを選ぶ k =</mの条件を満たす間(x,>…

問題ページ C: 暗闇帰り道 - AtCoder Regular Contest 003 | AtCoder 考えたこと 最小の最大化なので2分探索をする 経路の明るさvを達成できるかどうかをO(HW)くらいで判定できればよさそう d[y][x] = (座標(y,x)に到達できる最短の時刻t) としてdijkstraを…

問題ページ E: Papple Sort - AtCoder Regular Contest 088 | AtCoder 解法 文字列Sに文字aが11個存在すれば左の5個は回文の左半分に属し、右の5個は回文の右半分、真ん中の1個は回分の中央に属する。同じ文字を入れ替えたとしても操作回数が減らせることは…

MMで初のratedコンテストの参加だった。 概要 ワイヤーと色が決められているタイルで構成されている2次元グリッドが与えられている。タイルを並べ替えてワイヤーが閉路を構成するようにする。ただし同じ色が隣接しないように配置する。できるだけ閉路を長く…

概要 Aliceはa個のb面ダイス、Bobはc個のd面ダイスを投げる。このとき、ダイスの目の合計が大きい方を勝ちとする(引き分けはどちらの勝ちでもない)。Aliceが勝つことがありえないときは-1を出力しろ。そうでないときはAliceが勝った条件下でAliceのダイスの…

概要 2次元グリッド上で亀が左上のセルから右下のセルに右か下への移動を繰り返して移動する。グリッド上には障害物があり亀は通ることができない。このグリッドを用いて2人でゲームを行う。各プレイヤーはそれぞれの手番でグリッド上に障害物を配置する。こ…

概要 英アルファベットから成る文字列Sが与えられる。文字列Sは同じ種類の文字を2個ずつ含んでいる。この文字列Sを同じ種類の文字が1個ずつになるように文字を消去する。辞書順最小になるときに文字を消去したとき、文字列の最初の文字を出力しろ。 解法 辞…

問題ページ A - 1D Matching 考えたこと とりあえずNが小さいパターンを実験してみる。PCと電源をつなぐのをPCから電源への有向辺で表すとする。 下の図でオレンジ色のつなぎ方は最短なつなげ方ではない。最短なつなげ方にならないパターンを他にも試してみ…

技術的なことは書けないのでポエムを書きます。ferinという名前で競プロをやっていてAtcoderとcodeforcesで青の下の方、topcoderで緑の人です。 2016年11月 ミーハーなので流行りのディープラーニングに手を出してみる。どうやらPythonという言語がメジャー…

問題ページ Restrictive Filesystem | Aizu Online Judge 考えたこと 10^9の配列確保して1つずつ記録していくのはメモリ的にも計算量的にも不可能なので座圧は必須そう dp[i] = (j, k) (位置iからjまでkが記録されている)としてunordered_mapを使ってメモリ…

問題ページ E - Prefix-free Game 考えたこと ゲームと言われたのでサンプルについてWin-Loseの探索木を書いてみるがよくわからない 01文字列なのでtrie木を書いてみると葉を通らないような位置に頂点を追加する問題に言い換えられることがわかった 木上のゲ…

問題ページ Median Tree | Aizu Online Judge 考えたこと コストが小さい辺をなるべく使っていきたい 最小全域木を思い浮かべるけどコストが1の辺を使わずに2と3の辺を繋いだほうがいい場合があるのではみたいな気持ちになって捨てる（は？） 謎の貪欲を投げ…

問題ページ ICPC Calculator | Aizu Online Judge 解法 +か*が来たらその演算子で計算する範囲の数式を全部計算して返すような関数をつくってその関数を再帰的に呼び出していくことで計算する。ある演算子で計算する対象はその演算子より高さが1段高いものな…

問題ページ 6/2(1+2) | Aizu Online Judge 解法 構文解析をする。取りうる数字が一意には定まらないので候補全部をsetで持っておき、next_permutationで全通りを試す。括弧ごとに演算子と数字を全部列挙したあと、演算子の取りうる順番を全通り試してその括…

問題ページ Broken Cipher Generator | Aizu Online Judge 考えたこと 明らかに構文解析でBNFまで書いてあるので実装をしようとする。 BNFをよく見るとが左再帰なのでそのままは書けない。 ググって左再帰の除去を調べると = | empty とすればよさそう。 emp…

問題ページ D - Non-decreasing 考えたこと 各時点で数列の最大値と最小値をもっておく。a[i-1]とa[i]で減少してたら条件を満たすまでa[i-1]に最小値を足す or a[i]に最大値を足すでよさそうな方をするを繰り返す。 → a[i]に最大値を足した後で最小値を足し…

解説 Advent Calendar 2017の12/11の記事です。水色の頃にdiv2Cが解けないし解説がわからなくてつらかった覚えがあるのでその辺の問題を書きました。 ferin-tech.hatenablog.com ferin-tech.hatenablog.com ferin-tech.hatenablog.com ferin-tech.hatenablog…

問題ページ D - すぬけそだて――トレーニング―― このブログは解説ではなくクソポエムです 感想 解説を実装しただけ 実装に無駄に時間をかけてしまったので反省 lower_boundとかupper_boundでいまだに混乱するのをやめたい monge性とかスライド最小値、セグ木…

問題ページ C - すぬけそだて――ごはん―― この記事は解説ではなくクソポエムです。 考えたこと 互いに素とか言われたのでgcdとかlcmとかが頭に浮かぶ 制約が見たこと無い形をしている グラフを書いて互いに素じゃない頂点の間に辺を張ると最大独立集合みたい…

問題ページ E: 木と整数 / Integers on a Tree - AtCoder Regular Contest 063 | AtCoder 考えたこと 距離の偶奇と数字の差の偶奇が一致するのは必須 適当に何点か決め打ちすれば他の点も自然に決まっていく…？ 空いている各頂点について入りうる数字を2分探…

0日目 前日泊で来る人達とボドゲをする会に参加した。not my fault とインサイダーゲーム をやった。その後、東京物価高い！夕飯安いところがない！と探した結果ロイヤルホテルホストが見つかったので夕飯を食べた。オムライスおいしかった。前泊ホテル組が…

問題ページ H - Union Sets thanksのHを複数の解法で解いてみた話 解法1 公式で解説されていたLCAを使った解法 t回目のクエリではじめて頂点p, qがつながれたとき、頂点p, qを重みtの辺でつないだ森をつくる。これはunionfindを用いて、頂点p, qがすでにつな…

問題ページ F - Limited Xor Subset 考えたこと 数列の順番はどうでもいいのでsortできるし何なら個数だけ持ってもよさそう sumの制約の使い方がわからなくて永遠と実験していた 実験すると規則を見つけた気になったけど試してたケースが偏ってただけだった …