fuu32のブログ

精進記録

ICPC国内予選2019 参加記

竸プロ 参加記

はじめに

今年もICPC国内予選に参加しました。国内予選の参加記はこれが初めて。
チーム名はReturn 0で僕、やたかくん(@math_kpro)、りゅうせいくん(@ryu_ishika)の全員AtCoder緑といったメンバーでした。

結果は3完で121/458位。
これ以降ポエムになりますが、出来ればあとがきを読んでもらいたいかな。

当日以前

チーム練は模擬国内に参加しただけで普段の活動では個人でAOJ-ICPCの過去問を埋めていくことをしていました。もう少し真面目にチーム練をしてもよかったかも。

開始n時間前

ちょうど学内の書店で大判印刷ができる日だったので、ICPCのポスターを印刷していました。 印刷したはいいけど、画質が荒いし小さかったので悲しかったが...

3限は授業だったけど、ポスターを印刷していたら授業に少し遅れる。
真面目なので4限も受けてからチームの部屋に向かい準備したりリラックスしたり。

弊大学からは5チームが出場しており、個人的には3完はして学内2位にはなりたいなと思っていました。

競技開始

始まる前からAをりゅうせいくん、Bを僕、Cをやたかくんが担当しようと決めておいたので、各自それぞれの問題を見ていった。

Bははじめ文字間の最短経路かと思ったけど、複数のマスに同じ文字を含むことはないので、座標持ってマンハッタン距離やろと考え紙コーディングをしていた。去年のBが実装重め系で辛かった記憶があったので少し安堵。

Aをりゅうせいくんに任せていたけど、人の環境&US配列に慣れてないっぽい感じで大変そうだった。(本来はここでさりげなくサポートするのが上回生の役目だと思うんですがまぁ多少はね...)

やっぱりチーム固定でやっていく人々は環境を統一した方がいいね(それはそう
US配列はいいぞ！みんなUS配列を使おうな！！！(エディタはまぁご自由にどうぞ

少ししてりゅうせいくんがAをAC。
紙コーディングしていたので、僕がBを書く。AC。

その後はCを考えていたやたかくんに僕が合流して、Dをりゅうせいくんが考えることに。

Cは二人とも似たようなことを考えていて、mが小さいので各 w_{i} に対して、 -1、0、1倍して使う組合せを考えていい感じにしようみたいなことになり適当に書く。 サンプルケースの最後が合わない。デバッグしてみると、どこか重複してるんやろなと感じ取って、だいぶ時間がかかったが修正。

計算量が怪しかったが1分ぐらい回したら答えが出たので提出してAC。 これが噂に聞くICPC特有のあれかと思い少し感動した。

他にはEもみたけどこの実装を時間内にはムリ！と思いDに合流。

Dはりゅうせいくんが考察してくれていて、僕らがCを考えている間にサンプルが合ったので投げてみたけどWA。合流後に３人で考えてみたけど結局5WAで時間が来て終了。

3完できて学内2位、Dが解ければよかったけど、個人的には満足した。 その後Twitterをみたり、部内の他チームとどんな感じだったか少し話して片ずけをして懇親会に向かう。

懇親会

(珍しく?)国内予選お疲れ様と新入部員歓迎会を兼ねた懇親会をしました。

こういうサークルっぽいこともっとやっていきたいね。

あとがき

僕個人としては最近、配属先の研究室が決まり、今後も競プロとは趣味としての関係が続いていくと思います。来年の国内予選は参加するかな。あとは万年緑なのでレートあげたいけど、競技人口も増えてきて今以上に精進しないと厳しい状態ですね...

最後にこれは完全に個人のお気持ちなんですが、読んでもらえたら。
僕はRiPProという団体で競技プログラミングをしてるんですが、今年度で強い先輩方が卒業し部員が減ってしまうのがかなり寂しい状況です。新入部員も残ってくれていますがそれにしてもそんなに部員が多いという状況にないといういことに変わりありません。他大学の競プロサークルがどのような状況なのか僕はあまり知らないので比較できませんが、弊サークルのことを少しでも知ってもらいたので個人的な所感を書きます。

弊サークルの良いところ　　

  1. いわゆる学内選抜のハードルが低い
    ICPC国内予選ではルール上、出場チームの多い大学には通称学内選抜なるものが存在します。が、幸か不幸か弊学から出場するチーム数が少ないので他の強豪校と比較するとハードルは低いと思います。

  2. 学部が活動を支援してくれている(?)
    弊サークルは学部のプロジェクト団体なので学内の他団体に比べると応援されているのを感じます。もちろん毎年学内の助成金にも出願しておりACPC、RUPC、(JAG夏合宿やもちろんICPCアジア地区も1)などの交通費、宿泊費も助成金から賄われています(現時点では)。

  3. ACPC(会津合宿)、RUPC(立命合宿)に主催者側で参加できる
    ACPC、RUPCは面白い参加記がたくさん書かれているのでそれを参照してください。合宿では問題セットを提供して参加者の人々に解いてもらっています。

  4. 2021年3月までは僕がいます(順調にいけば)
    これはいいところか???とりあえず部員1人はいるのが確定ですね。

他にもたくさんいいところはあるかも。RiPProを宣伝するためにいいことばっかり言ってるのであれだけど、受験生とかは8月にあるオープンキャンパスでRiPProのブースにきて詳しい話を聞くといいと思うよ。

JOIやパソコン甲子園に挑戦している中高生競プロerは東大京大などを目指している人が多いと思うけど、選択肢の一つに弊サークル引いては弊学を考えてもらえたら嬉しいです。弊大は入試制度が謎に多いのでね。

もちろん競プロ未経験、さらにはプログラミング未経験でも大歓迎ですよ。僕もここスタートですし、 サークルで競プロするのは楽しいのでおすすめです。

あと弊学ではCTF(Capture The Flag)に取り組む団体もあるんですって！(すごい)

RiPProもRiSTも随時新入部員を求めているので、興味がある人がきてくれると嬉しいな。

文才がないのに深夜テンションでつらつらとポエムを書いてしまった。
この辺でおやすみなさい。

  1. 思い出したので追記 7/14 0:27 ↩

CSA Round #85 Strange Transformation

竸プロ CSA

問題概要

CS Academy
二つの整数A,BとN個の数字が与えられる。以下の二つの操作をそれぞ れ0回以上行い、条件を満たしつつAをBにしたい。
操作1.Aを3倍する
操作2.Aを2で割る(ただしAが偶数の時に限る)

条件:A からBにする過程でAがN個の数字全てになる。

AからBにする過程を出力。不可能なら-1を出力。

制約

0≤N≤50
1 ≤ A ≤ 10^{9}
1≤B≤10^{9}​​
A≠B

N個の数字について
1≤X​i​​≤10​^{9}
​​ A≠X_i,B≠X_i
​​ X_i≠X_j,i≠j

考えたこと

サンプルをみると何がしたいのかよくわかる。
A=24、B=81、N個の数字の集合をSとするとS=\{18,6\}の時出力は24,12,6,18,54,27,81のようになる。正しい操作と条件を満たしていればAは変化する過程でどのような値になってもいい。

まず、二つの操作では3を掛けるか2で割るかの操作しかしないので、A,Bを素因数分解した際、2,3以外の素因数とその指数は一致していなければならない。

このことは与えられるN個の数字についても同じことが言える。

次にN個の数字をどのような順番で経由していけばいいだろうか？もちろん、すべての組合せを考えるのは時間がかかりすぎる。例えば操作1のみが行える場合、Aは増加する一方であるからN個の数字は昇順に並んでいることが望ましい。また、操作2のみが行える場合、Aは減少する一方であるかからN個の数字は降順に並んでいることが望ましい。

では操作1,2が行える状況ではN個の数字はどのように並んでいればいいかを考えると、集合Sに含まれるすべてのX_i で2の指数については降順に、3の指数については昇順にソートされていればいい。

こんな感じに\{2^{6}\cdot3^{2},2^{4}\cdot3^{3},2^{2}\cdot3^{4}\}

ソートされた結果\{2^{7}\cdot3^{4},2^{6}\cdot3^{3},2^{5}\cdot3^{2}\}のようになってしまう可能性があるのでソート後に正しくソートされているかのチェックを行なっている。

X_iの並び順が決まったら、あとは\{A,ソートされたX_i,B\}となっている配列を先頭から隣り合う要素を見てその指数の差を埋め合わせるように3を掛けるか2で割るかの操作を行い値を出力していけば良い。

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string>
#include <utility>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define loop(i, x, n) for (int i = (x); i < (n); i++)
#define all(v) (v).begin(), (v).end()
#define int long long
using namespace std;
const int MOD = 1e9 + 7;
const int INF = 1e9;
template<typename T> void cmax(T &a, T b) { a = max(a, b); }
template<typename T> void cmin(T &a, T b) { a = min(a, b); }

//素因数分解＜素因数、指数＞
map<int, int> prime_fac(int n) {
  map<int, int> ret;
  for (int i = 2; i * i <= n; i++) {
    while (n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if (n != 1) ret[n] = 1;
  return ret;
}

struct primeFac {
  //X_i,２の指数、３の指数
  int num = 0, two = 0, three = 0;
  bool operator<(primeFac x) const { return two >= x.two && three <= x.three; }
};
int n, a, b;
vector<primeFac> p(n + 2);

//２、３以外の素因数の積を計算
int cal(map<int, int> m, int x, int pos) {
  int res = x;
  for (auto &z : m) {
    if (z.first == 2) {
      int q = z.second;
      while (q--) res /= 2;
      p[pos].num = x;
      p[pos].two = z.second;
    } else if (z.first == 3) {
      int q = z.second;
      while (q--) res /= 3;
      p[pos].num = x;
      p[pos].three = z.second;
    }
  }
  return res;
}

signed main() {
  cin >> n >> a >> b;
  p.resize(n + 2);

  vector<int> x(n);
  rep(i, n) cin >> x[i];

  map<int, int> m;
  m = prime_fac(a);
  int res = cal(m, a, 0);
  m = prime_fac(b);

  if (res != cal(m, b, n + 1)) {
    cout << -1 << endl;
    return 0;
  }
  
  rep(i, n) {
    m = prime_fac(x[i]);
    if (res != cal(m, x[i], i + 1)) {
      cout << -1 << endl;
      return 0;
    }
  }
  
  sort(p.begin() + 1, p.end() - 1);
  
  rep(i, n + 1) {
    if (!(p[i] < p[i + 1])) {
      cout << -1 << endl;
      return 0;
    }
  }

  rep(i, n + 1) {
    cout << p[i].num << ' ';
    int l = p[i].num, r = p[i + 1].num;

    rep(j, abs(p[i + 1].two - p[i].two)) {
      l /= 2;
      if (l == r) break;
      cout << l << ' ';
    }
    rep(j, p[i + 1].three - p[i].three) {
      l *= 3;
      if (l == r) break;
      cout << l << ' ';
    }

    if (i == n) {
      cout << p[i + 1].num << endl;
    }
  }
  return 0;
}

感想

コードに関してはもっと綺麗に書けそう。こういう問題をすらっと解けるようになりたいね。

OtterCTF writeup

CTF network

ちょうどwireshark/tsharkの使い方を練習していたのでnetworkの問題だけ解きました。
Otterとはカワウソのことらしい(ちなみにsea otterはラッコ(へー

目次

Birdman's Data

問題文
「We recorded some of BirdMan's networking, but a part of it (the important part) got scrambled.」
pcapファイルが与えられるのでwiresharkを用いてみていく。 まずはProtocol Hierarchyをみてどのような通信かを大雑把に把握する。 次に、HTTPが使われているので、HTTPでフィルターをかけてHTTP streamを覗いてみる。

クライアントがwww.txtwizard/net/cryptoに対してGETのリクエストし、レスポンスとしてページの情報が返されている。f:id:fuu32:20181211210422p:plain このサイトは暗号化や復号をしてくれるサイトらしい。

HTTP streamの最後の2つのやり取りではクライアントが平文を送って、それが暗号化されて返ってきている。クライアントのリクエストがPOST /crypto/AES/encrypt/CBC/PKCS5 とあり暗号の種類と使用されたモードまで分かった。

AES暗号の説明は(詳しくないので)割愛するがCBCモードなのでkeyとIV(初期化ベクトル)があれば復号できそう。 HTMLの中に以下の記述があったのでどこを見ればいいのか判別がついた。 (目grepしても分かるけど疲れそう)

        function onEncrypt(token) {
            var target = $('#encryptTarget').val();
            var key = $('#encryptKey').val();
            var iv = $('#encryptIv').val();
            var result = $('#encryptResult');
            var divAlert = $('#encryptAlert');
            var algorithm = $('#encryptAlgorithm').val();
            var mode = $('#encryptMode').val();
            var padding = $('#encryptPadding').val();

            $.ajax({
                type: 'POST',
                cache: false,
                url: '/crypto/' + algorithm + '/encrypt/' + mode + '/' + padding,
                data: { plainText: target, key: key, iv: iv, token: token },
                dataType: 'json',
                async: true,
                beforeSend: function(jqXHR, settings) {
                    divAlert.text("").hide();
                    result.text('');
                },
                success: function (data, textStatus, jqXHR) {
                    result.text(data.cipherText);
                    return;
                },
                error: function (jqXHR, textStatus, errorThrown) {
                    divAlert.text(jqXHR.responseText).show();
                    return;
                }
            });
        }

暗号文とkey,IVが手に入ったので、先ほどのサイトで復号してみると以下のような平文が手に入る。

Chance Something's wrong, I can feel it (Six minutes, Slim Shady, you're on) Just a feeling I've got, like something's about
To happen, but I don't know what If that means, what I think it means, we're in trouble, big trouble, And if he is as bananas as you say, I'm not taking any chances You were just what the doctor ordered I'm beginning to
Feel like a Rap God, Rap God All my people from the front to the back nod, back nod Now who thinks their arms are long
{
Enough to slap box, slap box? They said I rap like a robot, so call
me Rapbot But for me to rap like a computer must be
in my genes I got a laptop in my back pocket My pen'll go off when I half-c*** it Got a fat knot from that rap profit Made a living and a killing off it Ever since Bill Clinton was still in office With Monica Lewinsky feeling on his
Nut-sack I'm an MC still as honest But as rude and indecent as all hell syllables, killaholic (Kill 'em all with) This slickety, gibbedy, hibbedy hip hop You don't really wanna get into a pissing match with this rappidy rap Packing a Mac in the back of the Ac, pack backpack rap, yep, yackidy-yac The
exact same time I attempt these lyrical acrobat stunts while I'm practicing That I'll still be able to break a
Motherf***in' table Over the back of a couple of
_
Faggots and crack it in half
Only
Realized it was ironic I was signed to Aftermath after the fact How could I not blow? All I do is drop F-bombs, feel my wrath of attack Rappers are having a rough time period, here's a Maxipad It's actually disastrously bad For the wack while I'm masterfully constructing this masterpiece as I'm beginning to feel
_
Like a Rap God, Rap God All my people from the front to the back nod, back nod Now who thinks their arms are long enough to slap box, slap box? Let me show you maintaining this s*** ain't that hard, that hard Everybody want the key and the secret to rap
immortality like I have got Well, to be truthful the blueprint's simply rage and youthful exuberance Everybody loves to root
for a nuisance Hit the
Earth like an asteroid, did nothing but shoot for the moon since MC's
_
get taken to school with this music Cause I use it as a vehicle to bust a rhyme Now I lead a new school full of students Me? I'm a product of Rakim, Lakim Shabazz, 2Pac N- -W.A, Cube, hey, Doc, Ren, Yella,
Eazy, thank you, they got Slim Inspired
enough to one day grow up, blow up and be in a position To meet Run DMC and induct them into the motherf***in' Rock n' Roll Hall of Fame Even though I walk in the church and burst in a ball of flames Only Hall of Fame I be inducted in is the alcohol of fame On the wall of shame You fags think it's all a game 'til I walk a flock of flames Off of planking, tell me what in the f*** are you thinking? Little gay looking boy So gay I can barely say it with a straight face looking boy You witnessing a massacre Like you watching a church gathering take place looking boy Oy vey, that boy's gay, that's all they say looking boy You get a thumbs up, pat on the back And a way to go from your label everyday looking boy Hey, looking boy, what you say looking boy? I got a "hell yeah" from Dre looking boy I'mma work for everything I have Never ask nobody for s***, get outta my face looking boy Basically boy you're never gonna be capable To keep up with the same pace looking boy 'Cause I'm beginning to feel like a Rap God, Rap God All my people from the front to the back nod, back nod The way I'm racing around the track, call me Nascar, Nascar Dale Earnhardt of the trailer park, the White Trash God Kneel before General
zorb
}

明らかに改行がおかしいのでいい感じに幅を変えてエスパーすると文頭を縦読みしたのがFlagだと分かる。 CTF{EmiNeM_FOR_LifE_gEez} （ちなみにこの平文はEminemの歌詞らしい。)

Look At Me

問題文
「My otter played with my PC while I was recording...」

pcapファイルが与えられる。wiresharkで開くとUSBの通信の記録みたいだ。 どこかのwriteup記事でマウスの軌道を記録していて、それを復元するそうなものを見たことがあったのでこの問題もその類だと思った。 まずは、どのようなディバイスなのか知りたい。 それにはこのサイトが役に立つと思う。 CTF Series : Forensics — tech.bitvijays.com

GET SEDCRIPTOR Response DEVICパケットを見るとベンダーと製品が判明する。f:id:fuu32:20181211212519p:plain

どうやらWacomのタブレットのようだ。過去のwriteupを漁ると同じことをしている記事があったのでここからはそちらを参考にして解いている。

BITSCTF – Tom and Jerry (50 points) – tunelko.

まず、不要と思われるデータをフィルタ機能で排除。

((usb.transfer_type==0x01)&&(frame.len==37))

ここではLengthが37のパケットが多かったのでそれを残す形をとった。 次にleftover capture dataについて、これは実際のデータでありそれ以上でもそれ以下でもない(らしい Analysing USB traffic - Wireshark Q&A) なのでleftover capture dataからタブレットのどの位置に書かれたのかが分かりそう。 このタブレットの場合、leftover capture dataは全体で10bytesあり以下のフォーマットをとる。

header X Y Pressure suffix
02:f0 b4:0f b6:17 00:00 20:00

このX,Y,Pressureの値を抽出して、描画すればFlagがわかるだろう。 ここからはtshark(wiresharkのCUI版)を用いてデータを加工していく。 tsharkのオプションは tshark - The Wireshark Network Analyzer 2.6.5を参照。

tshark -r new.pcapng -T fields -e usb.capdata -Y usb.capdata > extracted.txt

これでleftover capture dataの部分がテキストファイルに書き込まれている。 -r で読み出すファイルを指定し、-T で出力するテキストのフォーマットを指定し、-eは-T でfieldsを指定した時に出力したいフィールドを指定している。-Yは指定したフィールドで絞り込みを行うオプションである。 次に以下のコマンドを実行する。 参考にしたサイトには

First tries were frustrated because little endian representation. We need to extract positions 3,4 for X and 5,6 for Y but first we must somehow swap those bytes. So first, filter with awk magic interesting data:

って書いてあるけれど、リトルエンディアンだから順番をいい感じにしなければいけないみたい？

awk -F: '{x=$3$4;y=$5$6}{z=$7}$1=="02"{print x,y,z}' extracted.txt > hex

ここでは':'区切りで3,4番目のフィールドをXに、5,6番目のフィールドをYに7番目のフィールドをZに代入し、$1(headerの値)が"02"なら出力する形をとっている。

X,Y,Pressureのデータが得られたので、以下のようなスクリプトを書いて実行する。

#!/usr/bin/python
from pwn import *

for i in open('hex').readlines():
    ii = i.strip().split(' ')
    x = int(ii[0],16)
    y = int(ii[1],16)
    z = int(ii[2],16)

    if z > 0:
        print u16(struct.pack(">H",x)),u16(struct.pack(">H",y))
$ python solver2.py > output.txt
$ gnuplot 
gnuplot> plot "output.txt"
gnuplot>

そうすると期待通りタブレットに書かれた文字を復元することができた。
f:id:fuu32:20181211225758p:plain
pngでダウンロードして convert -flip output.png output.png をすれば見やすくなる。 f:id:fuu32:20181211225941p:plain CTF{0TR_U58}

Otter Leak

問題文
「We found out that one of the Otters been leaking information from our network! Find the leaked data. Format: CTF{flag all uppercase}」

pcapファイルが与えられる。wiresharkで開いてprotocal Hierarchyをみるとこんな感じ。f:id:fuu32:20181211231824p:plain ん〜smb2が怪しそう。smbはwindowsネットワークでのファイル共有プロトコルらしいが、詳細や仕様などは他の記事に任せるとしてとりあえずオブジェクトをエクスポートしてみる。File->Export Objects->SMBでいくつかのファイルが保存できるだろう。

fileコマンドで調べるとほとんどのファイルは very short file (no magic)が返ってきて、実際に中身を見ることができるのでそれらすべての中身を表示させると下のようになる。

$ cat * 
LS0gLS0tLS0gLi0uIC4uLi4uIC4gLS0tIC0gLS0uLi4gLi4uLS0gLi0uIC4uIC0uIC0uLi4gLS4uLi4gLi4uLi0=

どう見てもbase64でエンコードされてそうなのでデコードしてみる。

$ echo "LS0gLS0tLS0gLi0uIC4uLi4uIC4gLS0tIC0gLS0uLi4gLi4uLS0gLi0uIC4uIC0uIC0uLi4gLS4uLi4gLi4uLi0=" | base64 -d 
-- ----- .-. ..... . --- - --... ...-- .-. .. -. -... -.... ....-

この溢れ出るトンツー感、モールス信号だと思ったので復号した。(https://morsecode.scphillips.com/translator.html) CTF{M0R5EOT73RINB64}

感想

あと一問残っていたけれど、時間内にときれなくて残念。個人的には2問目が面白かった。 色々遠回りして解いたので必要そうな部分を選んで書いたけれど、writeup書くの疲れて後半にかけて雑になってしまった。文章作成能力を上げていきたい。間違いや疑問があったらご指摘ください。

CSA Round #82 Restricted Arrays

竸プロ CSA

問題概要

CS Academy
長さNの数列AとKが与えられる。以下の条件を満たす数列Bはいくつあるか求める。
条件1. max(B_i) is minimum
条件2. B_i ＞ 0
条件3. | i - j | ＜ K を満たす i,jについて、A_i=A_jならばB_i=B_j,A_i \neq A_jならばB_i \neq B_jが成り立つ。

制約

1 \leq K \leq N \leq 10^{5}
1 \leq A_i \leq N

考えたこと

まず条件1.なんですが、数列Bの最大値が最小のものになっているという感じだと考えられます(いい感じに訳せません)。2つ目のテストケースを見てみると、数列A=\{2,1,2,2\}では条件1.を無視すると以下のような候補が考えられます。

\{1,2,1,1\} max(B_i)=2
\{2,1,2,2\} max(B_i)=2
\{2,3,2,2\} max(B_i)=3
\{4,3,4,4\} max(B_i)=4

下2つも条件2,3を満たすがmax(B_i)の値がとることのできる最小値ではないので全ての条件を満たすのは上2つのみとなります。

問題文の理解はできましたが、なかなか考察は進みません。
こういう考えやすいケースから考え始めるのが良さそうです。 まず、K=1の時これは1つ目のテストケースですが、この場合条件3は考慮しなくていいので、全てに1を使うことで条件1,2を満たしmax(B_i)=1になります。

次にK=Nの時を考えてみます。この場合は条件3の与える範囲が数列A全体なので、数列Aに含まれる数字の種類の数だけ用いれば数列Bを構成できそうです。つまり　max(B_i) = A_1からA_Nの範囲に現れる数字の種類　になります。

ではK=N-1の場合はどうでしょうか。この時、A_1からA_{N-1}の範囲とA_2からA_Nの範囲についてK=Nの時と同様に考えればいいと思います。それぞれの区間で必要な種類数のmaxをとれば全体としてのmax(B_i)が求まります。

なので与えられたKについて、幅Kの(N-K+1)個の区間に対してその区間に何種類の数字が使われているのかを調べるといいです。 実装では、幅Kの区間についてしゃくとりのように先頭から見ていくような感じにしました。

ここまでで、使える数字の種類(max(B_i))が求まったので、B_iに何通りの候補があるかを調べていきます。

B_1は自明にmax(B_i)通り。B_iに何通りあるを決める時、A_iとその直前のK-1個を見て、A_iと同じ数字が直前のK-1個の中にあるならばB_i=1、そうでないならばB_i= max(B_i)-直前K-1個にある数字の種類　となるはず。

全てのB_iを求め終わったら、 \prod_{i=1}^N B_iを mod ( 10^{9}+7)を取りながら計算することで答えが出ます。

提出コード

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string>
#include <utility>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define loop(i, x, n) for (int i = (x); i < (n); i++)
#define all(v) (v).begin(), (v).end()
#define int long long
using namespace std;
const int MOD = 1e9 + 7;
const int INF = 1e9;
template<typename T> void cmax(T &a, T b) { a = max(a, b); }
template<typename T> void cmin(T &a, T b) { a = min(a, b); }

signed main() {
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  rep(i, n) cin >> a[i];

  int maxB = 0;
  map<int, int> mp;
  rep(i, k) mp[a[i]]++;
  cmax(maxB, (int)mp.size());

  loop(i, k, n) {
    mp[a[i]]++;
    mp[a[i - k]]--;
    if (mp[a[i - k]] == 0) mp.erase(a[i - k]);
    cmax(maxB, (int)mp.size());
  }

  int ans = 1;
  map<int, int> m;
  vector<int> b(n);
  b[0] = maxB;
  m[a[0]] = 1;
  loop(i, 1, k) {
    if (m.count(a[i])) {
      m[a[i]]++;
      b[i] = 1;
    } else {
      b[i] = maxB - (int)m.size();
      m[a[i]]++;
    }
  }
  loop(i, k, n) {
    m[a[i - k]]--;
    if (m[a[i - k]] == 0) m.erase(a[i - k]);
    if (m.count(a[i])) {
      b[i] = 1;
    } else {
      b[i] = maxB - (int)m.size();
    }
    m[a[i]]++;
  }
  rep(i, n) {
    ans *= b[i];
    ans %= MOD;
  }
  cout << ans << endl;
  return 0;
}

感想

こういう問題は苦手ですが、あるケースを考えてその一つ小さい/大きいケースを考えていくのは有効なんだと感じる。言語化の能力が低いので、こんな説明で伝わるかが不安。

第5回　ドワンゴからの挑戦状　予選　B - Sum AND Subarrays

竸プロ greedy AtCoder

問題概要

B - Sum AND Subarrays

数列aの空でない連続する部分列の美しさは \sum_{i=l}^r a_i で決まり、 N(N+1)/2 個存在するすべての部分列から K個取ってきてそれらの美しさのビット毎の論理積を取った時の最大値を求める。

制約

2\leq N \leq 10^{3}
1\leq a_i \leq10^{9}
1\leq K \leq N(N+1)/2
入力はすべて整数

考えたこと

最大値を求めたいのでできるだけ上位のビットを残したいという気持ちにはなる。 なので上位のビットからみていき、部分列の美しさのうち今注目しているビットが立っている部分列の美しさがK個以上あるならばそれらを新たな集合とみなし、次一つ下のビットを見るときには新しい集合に属する値のみについて同じように調べていけばいい。
サンプル１を例に挙げる。部分列全体の集合をSとするとS=\{2,2,5,5,7,7,7,9,12,14\}でありそれぞれ二進数にすると以下のようになる。

美しさ　 ビット列　
14 0000001110
12 0000001100
9 0000001001
7 0000000111
7 0000000111
7 0000000111
5 0000000101
5 0000000101
2 0000000010
2 0000000010

今下から4ビット目について調べているとすると、4ビット目のビットが立っているのは\{14,12,9\}でありこれをS'とする。 S'は3つの要素からなり、 K \leq |S'| が成り立つので変数ansの下から4ビット目を1にし、次に下から3ビット目を調べるときは集合S'の要素についてのみ調べればいいことがわかる。

こんなことを上位ビットから下位ビットにかけてやっていけば良い。 最終的に残った集合の要素数がK個以上の場合もありうるがそのうちK個どの組み合わせで選んでも、最大値は変わらないので問題ない。

部分列の美しさの最大値は10^{3} \cdot 10^{9} = 10^{12} < 1099511627776 = 2^{40}なので下から40ビット目からみていけばいい。

提出コード：Submission #3660941 - Dwango Programming Contest V / 第5回 ドワンゴからの挑戦状 予選

解くべき問題を解いてレートを上げたいです。

Codeforces Round #523 C - Multiplicity

DP 竸プロ Codeforces

問題概要

Problem - C - Codeforces

数列aが与えられ、数列aから0個以上の要素を取り除いた数列を数列bという。
数列bの要素が1つ以上あり各b_iがi ( 1 \leq i \leq |b| ) で割り切れる時、数列bを数列aの良い部分列と呼ぶ。
数列aの良い部分列の総数を109+7で割った余りを求める。

制約

1 \leq N \leq105
1 \leq a_i \leq106

考えたこと

解説ACをしたのでこれCodeforces Round #523 Editorial - Codeforcesと同じことをしました。

まず、「 dp[ i ][ j ] ：＝ a_iまで見たときにj個で構成される良い部分列の数」というDPを考える。 遷移は以下のようになり、 \sum_{i=1}^n dp[ n ][ i ] が答えになるが制約的に二次元配列ではもてない。

{} $$ dp[ i ][ j ]= \left\{ \begin{array}{} dp[ i-1 ][ j ] + dp[ i-1 ][ j-1 ] & ( a_i が j で割り切れる時) \\ dp[ i-1 ][ j ] & (上以外の時) \end{array} \right. $$

Editorialには dp[i]は dp[i-1]にのみ依存するから1次元でもうまくいくよ！みたいに書いてあったがこれでは納得ができなかった。
参加者のコメントを参考に考えた結果、 「 dp[ i ]：＝ i個で構成される良い部分列の数」というDPを考えるとする。 例えばa_i=6の時、6の約数は{1,2,3,6}なのでa_iは数列bの1番目、2番目、3番目、6番目に置くことができるのはわかる。 なのでa_iの約数x_iを降順に dp[x_j]+=dp[x_j-1]のように更新していけばいいことになる。 昇順に更新していった場合、a_i=6の例で言えば1番目にa_iを使ったのに2番目でもa_iを使うといったことが起きてしまうため正しくないことがわかる。

i=1からi=Nまでのa_iに対して順に上の操作を行い、適宜109+7でmodをとれば\sum_{i=1}^n dp[i]が答えになる。
提出コード:Submission #46102628 - Codeforces

第3回ドワンゴからの挑戦状　予選　B-ニコニコレベル

竸プロ DP AtCoder

解きました。最近は良くも悪くも問題の点数に惑わされないようにしたい日々です。

問題概要

'25'を0回以上繰り返した文字列をニコニコ文字列という。
与えられる文字列Tは0~9の数字と?からなる。
?を0~9の好きな数字に置き換える時、与えられた文字列Tの中の最長のニコニコ文字列を求めたい。

制約

1≦|T|≦105

考えたこと

ニコニコ文字列では先頭が必ず2から始まるので文字列の中の25を別の文字の置き換えて、?の部分は2と5の繰り返しになり先頭は2か5の2通りなのでなんとかなるかなと考えていましたが考察に詰まりました。

先輩からアドバイスをもらったところ

1 ?がなく0~9の数字だけの場合をまず考えて見たらどうか
2 文字列のある位置までのニコニコ文字列の長さがわかった時、次の2文字が25だったらニコニコ文字列の長さは2増えるよね

要はDPで解くことができるのではないかということですね。
「dp[ i ] : =i-1文字目までのニコニコ文字列の長さ」といった感じの式です。
?が含まれている場合でも適切に条件分岐をすれば大丈夫です。
文字列のi文字目が2の時、i+1文字目が5または?の時に遷移。
文字列のi文字目が?の時、i+1文字目が5または?の時に遷移。

この条件は一つにまとめられますが僕はACした後に気がつきました。
後はdp配列の中で最大の値を求めればそれが答えとなります。
提出コード:Submission #2947865 - 第3回 ドワンゴからの挑戦状 予選

学んだこと

与えられた問題設定より条件が少ない場合を考えてみる。(今回の場合では文字列の中に?が含まれていない場合)
貪欲法が採用できないならDPを考えよう。