問題 Problem - C - Codeforces 問題概要 のグリッドがある。上から行目、左から列目のセルをと表す()。各グリッドには、条件に従って数字が書き込まれている。その条件とは、 に書き込むのは、このマスより左側一直線()と上側一直線()の中に現れていない正…
問題 Problem - E - Codeforces 問題概要 長さの数列と整数が与えられる。次のようなクエリが個与えられるので、それに答えよ： クエリ : 区間 について、同じ値は個までしか選べない時に、最大で何個まで選べるか (問題を読んでもらうと分かるが、オンライ…
問題 Problem - E - Codeforces 問題概要 個のカジノが一列に並んでいる(左から番目のカジノをカジノと呼ぶ)。カジノで遊んだ時に、勝つと1つ右に移動する。このときに勝つ確率はである。負けると1つ左に移動する(勝率は)。番目の左側と番目の右側は出口であ…
問題 Problem - E - Codeforces 問題概要 のグリッドがあり、各セルに数字がかかれている。グリッドの美しさを、連結成分の個数と定義する(同じ数字かつ上下左右のいずれかで触れていれば連結とする)。 クエリ: グリッドの左端を、右端をで切った時に残る部…
問題 Problem - F - Codeforces 問題概要 頂点辺の無向グラフが与えられる。辺は頂点とを結ぶ長さの辺である。 このグラフのinconvenienceを、「全ての頂点対の最短路のmax」と定義することにする。 このグラフから連結性を保ちつつ1つだけ辺を取り除く時の…
2/1 imulan.hatenablog.jp 2/2 CF 894 A - QAQ CF 894 B - Ralph And His Magic Field よくわからなかったけど、実験してみると規則性があったのでそれを実装した。 考え方としては、まず全てのセルには1か-1しか置くことが出来ない。その上で、k=-1のとき、…
問題 Problem - F - Codeforces 問題概要 長さの数列と整数が与えられる。クエリ:「閉区間内の連続部分列で、その和がになるものの個数を答える」が個与えられるのでそれぞれに答えよ。 アイデア prefix sumを使えば、ある区間の和はで取ることが出来る。以…
問題 Problem - D - Codeforces 問題概要 数列について、かつを満たすような数列が何種類存在するか、で割った余りを求めよ。 アイデア まず、数列の全てのgcdがであるということは、数列の全ての要素はの倍数であるということになる。よってその和もの倍数…
1/17 ARC 083 C - Sugar Water 水の量と砂糖の量を全探索する。砂糖の量は、bool配列などにその量が作れるかを持っておけば計算量的にOK(submission)。 ARC 083 D - Restoring Road Network Warshall-Floyd法によって、最短距離を計算して、入力と一致するか…
問題 Problem - F - Codeforces 問題概要 長さの順列がそれぞれあるかどうかを判定し、ある場合はその具体例を1つ示せ。 全てのについて、かつであるような順列 全てのについて、かつであるような順列 (ANDはbitwise and(C++でいう&演算子)) アイデア pにつ…
問題 Contest Page | CodeChef 問題概要 モンスターが体いて、それぞれにからまでのIDが振られている。のIDを振られているモンスターは、はじめ体力がある。次のようなクエリが個来る： クエリ : k & x = kを満たすについて、のIDを振られているモンスターの…
問題 Problem - L - Codeforces 問題概要 台のルータがあり、何台かはコードで繋がれており、ネットワークを構成している。ルータの構造は木である。次のような情報が与えられるので、元のネットワークの構造を復元せよ： それぞれのコードとと直接繋がって…
一昨年やってたのを復活させます。去年は「これあんまり意味ないかもなあ、もっとちゃんと解説書く問題を増やしたほうがいいでしょ」と思ったが、辞めた結果そもそも解説書く問題が減った(ダメ)。他人に読んでもらうことは特に意識せず書きます。 1/1 AOJ 20…
問題 No.584 赤、緑、青の色塗り - yukicoder 問題概要 一直線にNマスが並んでいる。各マスを赤、緑、青いずれかの色で塗ることが出来る。塗らないマスがあっても良い。マスを塗る条件として、 同じ色は隣接してはいけない 異なる色であれば連続する2マスを…
問題 Problem - J - Codeforces 問題概要 頂点辺の無向グラフが与えられる。この各辺について、どちらかに向きを付けなければならない。その時に各頂点からの出次数の最大値が最小になるような割り当て方を答えよ。 多重辺や自己ループはない アイデア 各辺…
問題 Contest Page | CodeChef 問題概要 長さの数列が与えられる。xy平面を考えて、数列に対して番目の要素について、とを端点とする線分を引く。以下の2種類のクエリが合計で個与えられるのでそれを処理せよ： + i X : ? i L R : x軸に平行な光が、個発射さ…
問題 Contest Page | CodeChef 問題概要 根付き木の美しさを、good subsets of leavesの個数で定義する。 どういうものがgood subsets of leavesになるかというと、根からdfsをしていき、訪れた順番に、そのノードが葉であればその頂点番号をリストに追加す…
ACM-ICPC 2017 Asia Tsukuba Regional | 国際大学対抗プログラミングコンテスト2017アジア地区つくば大会 ACM-ICPCというプログラミングコンテストの国内予選を通過したので、アジア予選に参加してきました。 私はSyntaxSatoというチームのメンバーとして参…
問題 Traffic Tree | Aizu Online Judge 問題概要 頂点数の木が与えられる(番目の辺は頂点とを結ぶ)。 隣接する頂点に移動するコストを1であるとすると、各頂点について、その頂点をスタート地点とした時に全ての頂点を訪れるための最小コストを求めよ。 ア…
問題 CS Academy 問題概要 のバイナリ行列がある。はじめ、行列の全要素は0である。この行列に対して、以下の操作を回行う： 行列のセル()を1つ指定し、行目の全要素をバイナリ反転し、列目の全要素を全要素をバイナリ反転する(よって、セルは2回反転される…
問題 CS Academy 問題概要 xy平面に点が個与えられる。4点を選んで、それによって長方形を構成したいが、長方形のそれぞれの辺がx軸とy軸にそれぞれ平行になるようにしなければならない。 そのような4点の選び方は何通りあるか。 アイデア 1つ目の方針として…
問題 Problem - D - Codeforces 問題概要 サッカーチームが個ある。それぞれのサッカーチームにはチーム名があり、2単語から構成されている。 各チームの省略形を3文字で決定したい。各チームに対して、省略形の候補は2種類ある： 1単語目のprefix3文字を取…
問題 Problem - C - Codeforces 問題概要 2次元平面上に点が個ある。番目の点の座標はである。各点に対して、x軸に平行な線を描く、y軸に平行な線を描く、何も描かないのどれかの操作を選ぶことが出来る。 この個の点から描かれた線を平面上に描かれた画像と…
9/18~9/20の2泊3日で、これに行ってきました atnd.org 競プロオンサイトイベントはCODE FESTIVALしか行ったことなかったので、とてもワクワクしながらオンサイト行きました。 会津大学に初めて行ったんですが、自分が通っている大学と比べてかなり景観が良く…
問題 Dashboard - Round 1A 2017 - Google Code Jam 問題概要 究極のラタテュイユのレシピが完成した。レシピにはどの原料をどれほど使うべきか、が記されている。ラタテュイユには種類の原料が必要であり、1人前を作るのに番目の原料がグラム必要である。 …
問題 CS Academy 問題概要 長さの配列と長さの配列が与えられる。これらから、の行列を作る。で行列の各項を与える。 この中で部分行列を取り出し、その部分行列の要素の全てのXORを取る時に、得られる値の最大値を求めよ。 アイデア 部分行列の左上隅のinde…
問題 CS Academy 問題概要 要素数の配列が与えられる。いま、配列のindexを1つ指しているポインタがあり(はじめは)、そのポインタに対して以下の3つの操作ができる： を1増やす を1減らす が指している位置の要素を削除し、は1つ前の要素か1つ後の要素を指す…
問題 CS Academy 問題概要 本のろうそくがある。番目のろうそくの長さはである。一晩ろうそくを使用すると長さは1だけ減る。 これから、回の夜を過ごそうとしている。日目の夜には、本のろうそくを灯そうと考えている。最大で過ごせる夜の回数を求めよ。 ア…
問題 CS Academy 問題概要 頂点数の完全グラフの各辺に対して向きを付ける(トーナメント)。この時、経路長が3である閉路の個数が最大になるように向きを付け、その向きの付け方と、その結果経路長が3である閉路はいくつになるか答えよ。 アイデア まず、問題…
問題 CS Academy 問題概要 頂点数の木が与えられる。長さの順列を考え、それを頂点に対応させる時、との間にいずれも辺がないような順列の中で辞書順最小のものを求めよ。 テストケース数 : テストケース全体でのの和はを超えない アイデア 同じラウンドに(E…
