現時点で正しいと思う理解の仕方を書いたので、間違いや気になるところがあればぜひ教えてください。 問題 C: Shorten Diameter - AtCoder Grand Contest 001 | AtCoder 頂点の木がある。この木の直径を 以下にするために削除する必要のある最小の頂点数を求…

強連結成分分解のライブラリ。 今のところsame(2つの頂点が同じ強連結成分に属するか)しかつけてないけど、いろいろ拡張すると便利そう。 gist.github.com

問題タイトルが英語で、世界を感じた。 問題 B: Mysterious Light - AtCoder Grand Contest 001 | AtCoder (問題文の図を参照) ざっくり言うと、正三角形の中で光を反射させたとき、最初の点に戻ってくるまでの軌跡の長さを求めよ、という問題。ただし光は正…

"木上のimos法"というテク。 問題 No.399 動的な領主 - yukicoder N頂点の無向木がある。Q人の人が u_i から v_i へ最短経路で移動する。人が頂点を通過するとき、(自分より前にその頂点を通った人の人数) + 1 のコストがかかる。Q人の移動コストの総和を求…

なんとか時間内に通せてよかった。 問題 No.398 ハーフパイプ(2) - yukicoder 6人の審査員がいる。審査員は1人ごとに、0点以上から100点以下の整数の得点を提示する。提示された6つの得点のうち、最大値と最小値を除いた4人分の平均はXであった。このような6…

受験記です。 僕が受験したのは秋入学の回ですが、特に秋入学だからと言って変わるところはないようです。 以下の受験記もオススメです。 kujira16.hateblo.jp 準備編 小論文 研究室見学に伺った際に聞いたお話が面白かったので、テーマはそれを元に考えまし…

難しかった。 問題 B: 高橋君ゲーム - AtCoder Regular Contest 057 | AtCoder 高橋君はN日間ゲームを行う。i日目にはa_i回のゲームをする。ゲームの結果は勝つか負けるかのどちらかである。 高橋君のi日目の機嫌は勝率によって決まる。i-1日目までの勝率よ…

学び。 問題 竹が2本ある。長さはそれぞれ である。 人の客がいる。 番目の客は長さがちょうど の竹が欲しいと言っている。 あなたは2本の竹のいずれかから一部を切り出すことで客の注文に応えることができる。ただし異なる竹から切り出した部分どうしをつな…

問題 人の人と 個の問題がある。次の制約をすべて満たす、人→問題の割り当て方の数を で求めよ。 1人はただ1つの問題に取り組む すべての問題について、取り組む人が1人以上いる 制約 解法 前提として、人は区別されるということに注意(これをわかっていなく…

問題 N個の正の整数からなる集合 S = {x_1, x_2, ..., x_N} がある。 SからM個の要素を選んで適切に並び替えた数列を (a_1, a_2, ..., a_M) とするとき、aが単調増加かつ隣り合うすべての要素に対してa_iがa_i+1の約数となるような数列を「良い」数列と呼ぶ…

問題 M個のマスが1直線状に並んでいる。K個のヒントがあり、k番目のヒントは連続するH_k個のマスを塗れというものである。ただし異なるヒントによって塗られるマスどうしは隣接してはならない。このような塗り方は何通りあるか。mod 109 + 7 で答えよ。ただ…

問題 N 人の人が 1 番目から順に駐車場にやってくる。駐車場は N 個の駐車スペースが無向辺で結ばれたグラフで表され、入り口は頂点 S である。i 番目の人は i 番目の駐車スペースに車を停めるか、停められないならば停めずに帰る。 駐車できる人の番号をす…

問題 N匹のうさぎ(1..N)が徒競走をした。 M人の観客から、x_iはy_iより先にゴールしたという情報がわかっている。 同着はいないとするとき、着順は何通り考えられるか？ 制約 2 <= N <= 16 1 <= M <= N(N - 1) / 2 解法 着順は最大で N! 通りある。いくら制…

クラスにしたのでとりあえず。 日本語コメント保存用 Verify: Lowest Common Ancestor | Aizu Online Judge #include <bits/stdc++.h> using namespace std; #define int long long // <-----!!!!!!!!!!!!!!!!!!! #define rep(i,n) for (int i=0;i<(n);i++) #define rep2(i,</bits/stdc++.h>…

問題 N頂点の無向木で表される国がある。各頂点を通るには1人当たり税金Uiがかかる。 今からQ個のクエリが与えられる。i番目のクエリは頂点Aiから頂点BiにCi人が移動することを表す。 この国で支払われる税金の合計額を求めよ。 制約 2 <= N <= 100000 0 < U…

問題 M円の所持金がある。 N種類のカップ麺がある。i番目のカップ麺はCi円である。カップ麺は好きなものを好きなだけ購入できる。 カップ麺を購入したとき、もし残り所持金が素数となれば所持金をM円に戻すことができる(これを"金欠チャンス"と呼ぶ)。ただし…

問題 H行W列のマス目がある。 1番目からN番目までの人が順番に、空いているマスのある1行or1列を選び、その行or列のすべてのマスを埋める。N番目まで回ったら1番目の人に戻る。 最後のマスを埋めた人の負けである。 それぞれの人が自分が負けないように行動…

メモ：直線の交点のパラメータの求め方について。 問題 黒い線分と赤い線分が合わせて n 本フィールドに散らばっている。フィールドには地上･地下の2つのレイヤーがあり、どの線分も地上または地下にある。今から青い線分を与えられた点A, B間に1本引く。青…

問題 グラフの全域木の中で、辺の重みの最大値 と最小値 の差 が最小となるようなものの を求めよ。また、全域木が構築できないならばその旨を答えよ。 Slim Span | Aizu Online Judge 制約 頂点数: 辺の本数: 辺 の重み: グラフは無向単純連結グラフ 解法 …

問題 n個の球がある。球iは中心(x_i, y_i, z_i), 半径r_iである。これらの球の間に必要であれば橋を架けることで、すべての球の間を連結にしたい。ただし最初から共有点を持つ球どうしや、片方がもう片方を内包するような球どうしは既に連結であるとみなす。…

問題 N個の都市がM本の道路でつながれている。i本目の道路は都市a_iとb_iを結び、y_i年に造られたものである。 Q人の国民がいる。国民jは都市v_jに住んでおり、作られた都市がw_jより大きな道路しか使わない。 各国民について、自身が住んでいる都市から条件…

チームMusyoku(ソロ)で参加し，4完で全チーム中24位でした． 模擬国内Aのときは自力では2完だったので，少しは解けるようになったかな． A. カレー作り 式変形して，実行可能な最小の解xをループで求める． (コードについて)本当はyの符号だけわかればよいの…

問題 i 個の数の組 (w_i, h_i) が与えられる。これらから自由に選んで並べてw, hともに狭義単調増加な列を作るとき、その最大の長さは？ 制約 1 <= N <= 105 1 <= w_i <= 105 1 <= h_i <= 105 解法1: LIS まず、入力をwの昇順にソートします。すると、以下の…

結果 1完でひどい。 Aが落ちてたり、他にもデバッグ出力を消し忘れてWAしたりTLE解を気づかずに出してたりと非常に頭が悪い。 大反省。。。 ただ、問題は面白かったです。 A. Infinite Sequence 問題 Problem - A - Codeforces 初項a, 公差cの等差数列にbが…

BITの使い方を勉強しなおした。 問題 1, 2, ..., Nの順列がある。この順列の隣り合う2つの要素を並び替えるという操作により数字を山型に並び替えるには最小何回の操作が必要か。 制約 1 <= N <= 105 解法 Nをどこに持ってくるかの全通りに対して、左側の反…

問題 H: Counting 1's - square869120Contest #2 | AtCoder N個の0が並んでいる。 以下のクエリを処理せよ。 クエリ1: 区間[l, r)のビットを反転させる。 クエリ2: 区間[l, r)内の1の数を答える。 解法 遅延セグメント木。区間の問題なのでセグ木という発想…

結果 pretest通したやつは全部通ってた。 今回は初めてCオープンしてみましたが、いい感じ。A, Bは落とさないように気を付けても結局落ちたりして費用対効果が薄いので…だったら高い得点を取れるうちにCを解いてしまった方がよさそうという考え。 レーティン…

Twitterに流したものをこちらにも残しておきます。 【No.365 ジェンガソート】 最初の2問はコンテストが決まってから「★1, 2がない！」ということで作った問題です。「ちょっと考える★1」を狙って作りました（が、結局★2になってしまいすみません。）テスタ…

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

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